When the law of large numbers fails for increasing subsequences of random permutations. (English) Zbl 1124.60033

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.\)


60F99 Limit theorems in probability theory
60C05 Combinatorial probability


Zbl 1111.60006
Full Text: DOI arXiv


[1] Aldous, D. and Diaconis, P. (1999). Longest increasing subsequences: From patience sorting to the Baik–Deift–Johansson theorem. Bull. Amer. Math. Soc. (N.S.) 36 413–432. · Zbl 0937.60001 · doi:10.1090/S0273-0979-99-00796-X
[2] Baik, J., Deift, P. and Johansson, K. (1999). On the distribution of the length of the longest increasing subsequence of random permutations. J. Amer. Math. Soc. 12 1119–1178. JSTOR: · Zbl 0932.05001 · doi:10.1090/S0894-0347-99-00307-0
[3] Logan, B. F. and Shepp, L. A. (1977). A variational problem for random Young tableaux. Adv. Math. 26 206–222. · Zbl 0363.62068 · doi:10.1016/0001-8708(77)90030-5
[4] Pinsky, R. (2006). Law of large numbers for increasing subsequences of random permutations. Random Structures Algorithms 29 277–295. · Zbl 1111.60006 · doi:10.1002/rsa.20113
[5] Vershik, A. M. and Kerov, S. V. (1985). Asymptotic behavior of the maximum and generic dimensions of irreducible representations of the symmetric group. Funct. Anal. Appl. 19 21–31. · Zbl 0592.20015 · doi:10.1007/BF01086021
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.