Generating Random Young Tableaux: A peculiar probability identity

Question

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?

Answer 1

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)