When the law of large numbers fails for increasing subsequences of random permutations
成果类型：
Article
署名作者：
Pinsky, Ross G.
署名单位：
Technion Israel Institute of Technology
刊物名称：
ANNALS OF PROBABILITY
ISSN/ISSBN：
0091-1798
DOI：
10.1214/009117906000000728
发表日期：
2007
页码：
758-772
关键词：
摘要：
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,kn,) if k(n) = o(n(2/5)); that is, lim(n ->infinity) Z (n,kn)/EZ(n,kn) = 1 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) >= 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 l < l(0), and does not hold if sup(n ->infinity) 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 lim sup(n ->infinity) kn/n(4/9) = infinity. Thus, the critical exponent, if it exists, must satisfy l(0) is an element of [2/5,4/9].