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

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

2006-04-04

arxiv.org/abs/math/0604067v3

Annals of Probability 2007, Vol. 35, No. 2, 758-772

Mathematics

Probability

Published at http://dx.doi.org/10.1214/009117906000000728 in the Annals of Probability (http://www.imstat.org/aop/) by the Ins

Scientific paper

10.1214/009117906000000728

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\}$. 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\to\infty}\frac{Z_{n,k_n}}{EZ_{n,k_n}}=1\qquad 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\ge cn^{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 $l0$, 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 $\limsup_{n\to\infty}\frac{k_n}{n^{4/9}}=\infty$. Thus, the critical exponent, if it exists, must satisfy $l_0\in[{2/5},{4/9}]$.

Affiliated with

Also associated with

No associations

Rating

When the law of large numbers fails for increasing subsequences of random permutations does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with When the law of large numbers fails for increasing subsequences of random permutations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and When the law of large numbers fails for increasing subsequences of random permutations will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-501212