Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Let $(X_1,X_2,\ldots)$ be a sequence of i.i.d. random variables. It is known that if these random variables are distributed uniformly on the unit interval, then applying the RSK algorithm to this sequence (and looking at the recording tableau) gives the (infinite) Plancheral measure on Young Tableaux. Restricting the above sequence to length $n$ to give the Plancheral measure on partitions of $n$. The proof is straightforward as the sequence of $X_i$ induce uniformly random permutations and RSK follows through.

Here's my question: what is known in the case of other distributions for the $X_i$? I suppose one can equivalently say what is known for non uniformly random permutations but I'd like to stick to the former.

In particular, is anything known about the resulting limit shape of the tableau like the result of Logan-Shepp-Vershik-Kerov? I did some simulations with other distributions and it seems the limit shape is the same! Here's a picture of the usual Plancheral limit shape:

alt text

share|improve this question
If the distribution is absolutely continuous w.r.t. Lebesgue on the unit interval then there is a monotone measure isomorphism to the uniform distribution so everything is the same. –  John Wiltshire-Gordon Jun 12 '13 at 0:31
What $n$ do you use in your simulations? –  Daniel Parry Jun 12 '13 at 6:46
@Daniel Parry: I've tried up to $n=10,000$. –  Alex R. Jun 12 '13 at 16:54

2 Answers 2

up vote 4 down vote accepted

You might find useful the $q$-Plancherel measure, which is a result of RSK applied to a probability distribution on $S_n$, where each permutation $\sigma$ is weighted with $q^{maj(\sigma)}/(n!)_q$, where $maj(\sigma)$ is the sum of all $~i$, such that $\sigma(i)>\sigma(i+1)$, $1\le i < n$. See V. Feray and P.-L. Méliot, Asymptotics of q-Plancherel measures.

share|improve this answer

Another interesting example is when each $X_i$ is uniformly distributed on the set $\{1, 2, \dots, d\}$. The resulting "Schur-Weyl" distribution on Young diagrams also has limit distributions that look like the Plancherel distribution if $d$ is sufficiently large compared to $n$. I recommend here the thesis of Méliot: http://www.math.u-psud.fr/~meliot/PLMs_web_page/Works_files/thesis.pdf

On the other hand, if the $X_i$'s are iid with some discrete distribution on $\{1, 2, \dots, d\}$ and $n$ is large compared to $d$ then the scaled version of the tableau will converge to the (sorted) histogram of the $X_i$s' common distribution. See, e.g., Hua Xu's thesis: https://smartech.gatech.edu/bitstream/handle/1853/26637/xu_hua_200812_phd.pdf

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.