Law of large numbers for increasing subsequences of random permutations
Ross G. Pinsky · Random Structures and Algorithms · 2005
Abstract Let the random variable Zn,k denote the number of increasing subsequences of length k in a random permutation from Sn, the symmetric group of permutations of {1,…,n}. We show that Var(Z ) = o((EZ )2) as n → ∞ if and only if $k_n=o(n^{{2\over 5}})$ . In particular then, the weak law of large numbers holds for Z if $k_n=o(n^{{2\over 5}})$ ; that is, We also show the following approximation result for the uniform measure Un on Sn. Define the probability measure μ on Sn by where U denotes the uniform measure on the subset of permutations that contain the increasing subsequence {x1,x2,…,x }. Then the weak law of large numbers holds for Z if and only if where ∣∣˙∣∣ denotes the total variation norm. In particular then, (*) holds if $k_n=o(n^{{2\over 5}})$ . In order to evaluate the asymptotic behavior of the second moment, we need to analyze occupation times of certain conditioned two‐dimensional random walks. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006