# Generating Random Young Tableaux: A peculiar probability identity

In the paper by Greene, Nijenhuis and Wilf, an algorithm is proposed for generating uniformly random Young tableaux of shape $\lambda$. The algorithm is to uniformly randomly pick a starting cell, and then do a hook walk algorithm until it terminates at one of the edges of the tableau. Another way of looking at this is to fix a starting cell $(a,b)$, and then start a random hook walk, so that one gets a path

$$(a,b)=(a_1,b_1)\rightarrow(a_2,b_2)\rightarrow\cdots\rightarrow (a_k,b_k)=(\alpha,\beta)$$

where $(\alpha,\beta)$ is the terminal cell. This defines a probability of hitting terminal cell $(\alpha,\beta)$ given starting cell $(a,b)$.

A peculiar observation is made on page 108, that:

$$P(\ (\alpha,\beta) \ |\ (a, b)\ ) = P(\ (\alpha,\beta) \ | \ (\alpha, b)\ ) \cdot P(\ (\alpha,\beta)\ |\ (a,\beta) \ )$$

In other words the probability of reaching the terminal point is the product of probabilities of starting in the row and column of the terminal point, which amounts to perpetually staying within the respective hooks. The authors point out that they have no obvious direct explanation of this fact.

Has anyone come up with an explanation more recently?

-

This is a technical question for those very familiar with the proof. Basically, GNW show by induction that the quantity on the l.h.s. has a product formula, with some hook numbers inside. Since the probabilities add up to 1, this gives a recurrence relation for the number of standard Young tableaux (SYT), mimicking the branching rule. This in turn allows one to prove the hook-length formula (HLF).

Now, why does the probability $P( (α,β) | (a,b) )$ has a product formula is a bit of a miracle. The way I see it, GNW aimed to prove HLF by induction, the summations were getting complicated, and they engineered the hook-walk to help keeping track of all paths they were counting. Arguably, the miracle of the product formula is exactly the same as the miracle of the HLF. The latter is a classical mysterious result, about which I can (but won't) go at length, but one thing is clear: there is no known philosophical reason why the ratio $n!/|SYT(\lambda)|$ has to be a product of $n$ "nice" integers, other than the fact that it's true.

To finish on a positive note, let me mention that while there is no formal procedure how to obtain a hook-walk from a HLF, the idea of constructing it is extremely robust. Roughly speaking, a variation on the HLF often enough can be derived via a hook-walk style proof (see a probably incomplete list below). In each case we get the a miraculous product formula for the probability of a hook walk stopping at a given corner.

1) in the shifted case (Sagan, 1980)
2) in the complementary case (GNW, 1984)
3) in the tree case (Sagan, Yeh, 1989)
4) in the q-case (Kerov, 1993)
5) in the q,t-case (Garsia, Haiman, 1998)
6) in the Han's tree formula case (Sagan, 2009)
7) in the weighted case (Ciocan-Fontanine, Konvalinka, Pak, 2011)
8) in the weighted complementary case (Konvalinka, 2011)
9) in the weighted shifted case (Konvalinka, 2011)

-
Thank you for your answer and links. I'm glad I'm not alone in my bewilderment as to why one gets such a nice identity. I was wondering if you happen to know any other algorithms for generating uniformly random Young Tableaux of a fixed shape $\lambda$? I'm aware that you were able to construct an algorithm akin to bubble-sorting. Do you happen to know of others? – Alex R. Apr 26 '13 at 2:39
Well, there are several more constructions coming from different combinatorial proofs of HLF, but really GNW and NPS algorithms are really the only constructions people tend to use. One example I like is to use RSK to get a random rpp, and then project onto a "random" syt, as in math.ucla.edu/~pak/papers/hl7.pdf You would have to be careful about equalities in the rpp if you want truly uniform distribution (use rejection sampling or something like that). See eg igm.univ-mlv.fr/~pivoteau/gascom06.pdf for a related work. Eplaining others would take more space than allowed here. – Igor Pak Apr 26 '13 at 5:11