Law of large numbers for increasing subsequences of random permutations

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}. We show that Var(Z) = o((EZ)²) as n → ∞ if and only if . In particular then, the weak law of large numbers holds for Z if ; that is, We also show the following approximation result for the uniform measure U_n on S_n. Define the probability measure μ on S_n by where U denotes the uniform measure on the subset of permutations that contain the increasing subsequence {x₁,x₂,…,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 . 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