Law of large numbers for increasing subsequences of random permutations and an approximation result for the uniform measure
Abstract
Description
Let the random variable $Z_{n,k}$ denote the number of increasing subsequences of length $k$ in a random permutation from $S_n$, the symmetric group of permutations of $\{1,...,n\}$. We show that $Var(Z_{n,k_n})=o((EZ_{n,k_n})^2)$ as $ n\to\infty$ if and only if $k_n=o(n^\frac25)$. In particular then, the weak law of large numbers holds for $Z_{n,k_n}$ if $k_n=o(n^\frac25)$. We also show the following approximation result for the uniform measure $U_n$ on $S_n$. Define the probability measure $μ_{n;k_n}$ on $S_n$ as follows: Consider $n$ cards, numbered from 1 to $n$, and laid out on a table from left to right in increasing order. Place a mark on $k_n$ of the cards, chosen at random. Then pick up all the unmarked cards and randomly insert them between the $k_n$ marked cards that remained on the table. Denote the resulting distribution on $S_n$ by $μ_{n;k_n}$. The weak law of large numbers holds for $Z_{n,k_n}$ if and only if the total variation distance between $μ_{n;k_n}$ and $U_n$ converges to 0 as $n\to\infty$.
In order to evaluate the asymptotic behavior of the second moment, we need to analyze certain occupation times of certain conditioned two-dimensional random walks.