Plancherel measure

Let ${\displaystyle L(\sigma )}$ denote the length of a longest increasing subsequence of a random permutation ${\displaystyle \sigma }$ in ${\displaystyle S_{n}}$ chosen according to the uniform distribution. Let ${\displaystyle \lambda }$ denote the shape of the corresponding Young tableaux related to ${\displaystyle \sigma }$ by the Robinson–Schensted correspondence. Then the following identity holds:

${\displaystyle L(\sigma )=\lambda _{1},}$

where ${\displaystyle \lambda _{1}}$ denotes the length of the first row of ${\displaystyle \lambda }$. Furthermore, from the fact that the Robinson–Schensted correspondence is bijective it follows that the distribution of ${\displaystyle \lambda }$ is exactly the Plancherel measure on ${\displaystyle S_{n}}$. So, to understand the behavior of ${\displaystyle L(\sigma )}$, it is natural to look at ${\displaystyle \lambda _{1}}$ with ${\displaystyle \lambda }$ chosen according to the Plancherel measure in ${\displaystyle S_{n}}$, since these two random variables have the same probability distribution. [3]

Plancherel measure is defined on ${\displaystyle S_{n}}$ for each integer ${\displaystyle n}$. In various studies of the asymptotic behavior of ${\displaystyle L(\sigma )}$ as ${\displaystyle n\rightarrow \infty }$, it has proved useful [4] to extend the measure to a measure, called the Poissonized Plancherel measure, on the set ${\displaystyle {\mathcal {P}}^{*}}$ of all integer partitions. For any ${\displaystyle \theta >0}$, the Poissonized Plancherel measure with parameter ${\displaystyle \theta }$ on the set ${\displaystyle {\mathcal {P}}^{*}}$ is defined by

${\displaystyle \mu _{\theta }(\lambda )=e^{-\theta }{\frac {\theta ^{|\lambda |}(f^{\lambda })^{2}}{(|\lambda |!)^{2}}},}$

for all ${\displaystyle \lambda \in {\mathcal {P}}^{*}}$. [2]

The Plancherel growth process is a random sequence of Young diagrams ${\displaystyle \lambda ^{(1)}=(1),~\lambda ^{(2)},~\lambda ^{(3)},~\ldots ,}$ such that each ${\displaystyle \lambda ^{(n)}}$ is a random Young diagram of order ${\displaystyle n}$ whose probability distribution is the nth Plancherel measure, and each successive ${\displaystyle \lambda ^{(n)}}$ is obtained from its predecessor ${\displaystyle \lambda ^{(n-1)}}$ by the addition of a single box, according to the transition probability

${\displaystyle p(\nu ,\lambda )=\mathbb {P} (\lambda ^{(n)}=\lambda ~|~\lambda ^{(n-1)}=\nu )={\frac {f^{\lambda }}{nf^{\nu }}},}$

for any given Young diagrams ${\displaystyle \nu }$ and ${\displaystyle \lambda }$ of sizes n − 1 and n, respectively. [5]

So, the Plancherel growth process can be viewed as a natural coupling of the different Plancherel measures of all the symmetric groups, or alternatively as a random walk on Young's lattice. It is not difficult to show that the probability distribution of ${\displaystyle \lambda ^{(n)}}$ in this walk coincides with the Plancherel measure on ${\displaystyle S_{n}}$. [6]