Random RSK and Plancherel Measure

Question

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:

(source)

Answer 1

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.

Answer 2

Another large family of distributions that contains both $U[0,1]$ inputs (leading to the usual Plancherel measure) and $U\{1,2,\ldots,d\}$ (as in Ryan O'Donnell's answer) as special cases is the following. Let $(\alpha, \beta, \gamma)$ be an element of the Thoma simplex, i.e., a triple where $\gamma\in [0,1]$ and $\alpha$ and $\beta$ are vectors $$ \alpha = (\alpha_1, \alpha_2, \ldots) \ \ \textrm{ with }\alpha_1\ge\alpha_2\ge \ldots \ge 0, $$ $$ \beta = (\beta_1, \beta_2, \ldots) \ \ \textrm{ with }\beta_1\ge\beta_2\ge \ldots \ge 0, $$ and such that $$ \sum_n \alpha_n + \sum_n \beta_n + \gamma = 1. $$ We can associate with $(\alpha, \beta, \gamma)$ a probability distribution of a random variable $X$ that is supported on $(0,1) \cup \{1,2,3,\ldots\} \cup \{-1,-2,-3,\ldots\}$, defined by $$ \mathbb{P}(X \in (a,b)) = \gamma (b-a) \qquad (0<a<b<1), $$ $$ \mathbb{P}(X = n) = \alpha_n \qquad (n=1,2,\ldots), $$ $$ \mathbb{P}(X = -n) = \beta_n \qquad (n=1,2,\ldots). $$ If we now take a sequence of i.i.d. random variables $X_1,X_2,\ldots$ with the same distribution as $X$ and apply the RSK algorithm to them, the resulting random infinite Young tableau has a very natural probability distribution studied by Vershik and Kerov, and supposedly related to the representation theory of the infinite symmetric group (a subject I know nothing about).

Note, however, that requires a modified version of RSK in which the rules for the insertion tableau are different: the rows and the columns of the insertion tableau are weakly increasing, but it is not allowed to have the same negative integer twice in the same row and it is not allowed to have the same positive integer twice in the same column.

This result was proved by Sergei V. Kerov and Anatol M. Vershik (SIAM J. Algebraic Discrete Methods, 7(1):116–124, 1986; available here)

Some additional consequences are discussed in the paper "Robinson-Schensted-Knuth algorithm, jeu de taquin, and Kerov-Vershik measures on infinite tableaux" by Piotr Śniady (SIAM J. Discrete Math. 28 (2014), 598–630; available at these links: journal version, arXiv version.)

Answer 3

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 If $d$ is fixed and $n$ tends to infinity, the distribution of the rows (after some simple rescaling) behaves asymptotically in the same as the joint distribution of the eigenvalues of a traceless GUE matrix Kurt Johansson, Discrete Orthogonal Polynomial Ensembles and the Plancherel Measure, Annals of Mathematics Second Series, Vol. 153, No. 1 (Jan., 2001), pp. 259-296

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 This happens if the probabilities of the atoms are all different.