Posted by: JBL | July 9, 2011

PSA: “RandomTableau” on Mathematica is broken (but Sage works fine)

This post is just a public service announcement: the function RandomTableau[p] in Mathematica is meant to give a random standard Young tableau of shape p. Though the documentation isn’t actually so helpful as to tell you explicitly what probability distribution it is allegedly generating, the only natural option is uniform over all tableaux of that shape. However, the function RandomTableau[p] does not generate tableaux uniformly. The rest of this post quickly outlines the evidence for this claim.

Given a standard Young tableau T, we can define the JDT path on T, as follows: starting from the (1, 1) entry of T (which happens always to be filled with the number 1), move to the smaller of the entry directly below (1, 1) and the entry directly to the right of (1, 1). (Here we work in English notation.) Then repeat this process: always move down or to the right, to whichever box has the smaller entry, until you reach the boundary of the shape.

It’s possible to ask a variety of probabilistic questions related to this path, but I’m going to narrow in very quickly on the particular case of interest: given the shape p, we can choose a tableau T of shape p at random. We may then ask which boxes of p lie on the JDT path of T. For example, with the shape p = (4, 3, 2, 1), it’s easy to show (e.g., by exhaustive enumeration; there are 768 tableaux of this shape) that it is equally likely that the (1, 3), (2, 2) and (3, 1) entries lie on the JDT path of a random tableau of shape p. (Incidentally, the fact that these three cells are equally likely is just a convenient freak coincidence for this shape.) However, after running 75,000 trials on Mathematica, I find that the command RandomTableau[{4,3,2,1}] generates a tableau in which the JDT path contains (2, 2) about 31.5% of the time. For reference, the probability of a given side coming up only 31.5% of the time when flipping a fair three-sided coin 10,000 times is only about 0.00005, and this happened 7 times in a row.

After that (fairly conclusive) experiment, I also tried keeping track of which tableaux are most favored and which are least favored by Mathematica. Running through about 150,000 random tableaux suggests that tableaux that look like

1 5 8 10
2 6 9
3 7
4

are favored (appearing roughly 50% more often than expected) while those like

1 3 5 10
2 4 8
6 9
7

are disfavored (appearing roughly 30% less often than expected).

I submitted a short description of the problem to the Mathematica support desk in February, got an e-mail back saying they’d look into it and let me know if they wanted to hear more, and haven’t heard anything since.

For those who are curious, the equivalent command in Sage works like a charm.

About these ads

Responses

  1. Lol give the writer of the code some credit ;)

  2. Yes, credit where credit is due: Yan was instrumental in finding this problem, as he did the coding that allowed for quickly testing this in both Sage and Mathematica.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Categories

Follow

Get every new post delivered to your Inbox.

Join 78 other followers

%d bloggers like this: