When the law of large numbers fails for increasing subsequences of random permutations

DOI10.1214/009117906000000728MaRDI QIDQ2371955zbMATH OpenOpenAlexFDO

Authors Ross G. Pinsky

Publication date 9 July 2007

Published in The Annals of Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0604067

Mathematics Subject Classification ID

Combinatorial probability (60C05) Limit theorems in probability theory (60F99)

Abstract: 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,\mathrm{...},n$. In a recent paper [Random Structures Algorithms 29 (2006) 277--295] we showed that the weak law of large numbers holds for $Z_{n,k_n}$ if $k_n=o(n^{2/5})$; that is, [lim_{n oinfty}frac{Z_{n,k_n}}{EZ_{n,k_n}}=1qquad in probability.] The method of proof employed there used the second moment method and demonstrated that this method cannot work if the condition $k_n=o(n^{2/5})$ does not hold. It follows from results concerning the longest increasing subsequence of a random permutation that the law of large numbers cannot hold for $Z_{n,k_n}$ if $k_{n}gec{n}^{1/2}$, with $c>2$. Presumably there is a critical exponent $l_0$ such that the law of large numbers holds if $k_n=O(n^l)$, with $l<l_0$, and does not hold if $limsu{p}_{noinfty}frac{k}_n{n}^l>0$, for some $l>l_0$. Several phase transitions concerning increasing subsequences occur at $l=1/2$, and these would suggest that $l_0=1/2$. However, in this paper, we show that the law of large numbers fails for $Z_{n,k_n}$ if $limsu{p}_{noinfty}frac{k}_n{n}^{4/9}=infty$. Thus, the critical exponent, if it exists, must satisfy $l_{0}in[2/5,4/9]$.

Review text

Let \(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,\dots,n\}.\) The author proved earlier that the weak law of large numbers holds for the sequence \(Z_{n,k_n}\) if \(k_n= o(n^{2/5})\) [cf. Random Struct. Algorithms 29, No. 3, 277--295 (2006; Zbl 1111.60006)]. The author now shows that the law of large numbers fails for \(Z_{n,k_n}\) if \(\limsup_{n\rightarrow \infty}(k_n/n^{4/9})= \infty.\)

Recommendations

• Law of large numbers for increasing subsequences of random permutations
• On increasing subsequences of random permutations
• scientific article; zbMATH DE number 1047715
• Dominated Permutations of Subsequences of Random Variables
• On the distribution of the length of the longest increasing subsequence of random permutations

Cites work

• A variational problem for random Young tableaux
• Asymptotics of maximal and typical dimensions of irreducible representations of a symmetric group
• Law of large numbers for increasing subsequences of random permutations
• Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem
• On the distribution of the length of the longest increasing subsequence of random permutations

Cited in

(2)

• Asymptotic results on weakly increasing subsequences in random words
• Law of large numbers for increasing subsequences of random permutations

This page was built for publication: When the law of large numbers fails for increasing subsequences of random permutations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2371955)