Law of large numbers for increasing subsequences of random permutations and an approximation result for the uniform measure
| dc.creator | Pinsky, Ross | |
| dc.date | 2004-07-21 | |
| dc.date | 2005-07-25 | |
| dc.date.accessioned | 2026-07-07T05:10:31Z | |
| dc.date.available | 2026-07-07T05:10:31Z | |
| dc.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. | |
| dc.identifier | https://arxiv.org/abs/math/0407353 | |
| dc.identifier | http://arxiv.org/abs/math/0407353 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/71951 | |
| dc.subject | Probability | |
| dc.title | Law of large numbers for increasing subsequences of random permutations and an approximation result for the uniform measure | |
| dc.type | text |