Running the Greene-Nijenhuis Algorithm Backwards

Question

This question is crossposted from math.stackexchange.com, where it remains unanswered.

Let $Y$ be a Young tableau of shape $\lambda:=(\lambda_1,\ldots,\lambda_n)$, where $\lambda_1\geq\lambda_2\geq\ldots\geq\lambda_n$ and $N:=|\lambda|:=\sum_i\lambda_i$. I'll be using the English notation for Young tableaux. Then the hook of a box $(i,j)$ is every box straight below and straight to the right of $(i,j)$, including $(i,j)$ itself.

The Greene-Nijenhuis algorithm generates a uniformly random Young tableau of the above shape as follows:

1) Set $k=N$.

2) Uniformly pick a random unoccupied cell in $Y$.

3) Do a hook walk algorithm till you reach the edge, and place $k$ there.

4) $k\leftarrow k-1$. Repeat steps 2-4 until $k=0$.

I'm wondering if you can generate a uniformly random Young tableau by running the Greene-Nijenhuis algorithm backwards? So set $k=1$, uniformly pick an unnocupied cell, and now perform a hook walk algorithm, except now the hooks are oriented left and up: the hook of $(i,j)$ is now $(i,j)$ and every box straight above and straight to the left. Obviously 1 ends up in the top-left corner. Now do the same for $k=2$, etc.

The product of the reverse hooks does not equal the product of the usual hooks, so it seems that a modification is required, some sort of re-weighting perhaps.

Answer 1

With no modification this procedure indeed does not give a uniform distribution, the minimal example is $\lambda=(3,2)$, as can be easily verified.

As for modified procedures, there are too many possibilities. With no restrictions there are trivial algorithms that work. If you insist on preserving some aspects of the method then it is indeed less clear.

One difficulty is that the distribution of cell $k$ given the first $k-1$ cells depends on the number of skew tableaux of certain shapes, and these numbers are much less well behaved then for Young tableaux. For example in the case of a diagonal strip of width 2, there are formulae (see e.g. arXiv:0709.0498) but the probabilities these give do not suggest that there is any simple modification that will work.