Abstract: Let S_n be the symmetric group of permutations on n elements and let U_n denote the uniform measure on S_n so that \sigma\in S_n may be thought of as a random permutation. For k <= n, let Z_{n,k}=Z_{n,k)(\sigma) denote the number of increasing subsequences of length k in a random permutation \sigma in S_n. In this talk we will be interested in the behavior of Z_{n,k_n}, where typically k_n=n^l.

Let EZ_{n,k} denote the expected value of Z_{n,k}. We say that the weak law of large numbers (WLLN) holds for Z_{n,k_n) if

Presumably, there exists a critical exponent l_0 such that WLLN holds for Z_{n,n^1} if l < l_0 and does not hold if l > l_0. We prove that WLLN holds for l < 2/5 and does not hold for l > 4/9. The proof of the second part uses in a crucial way the recent celebrated result of Baik, Dieft and Johansson (1999) on the statistics of the longest increasing subsequence in a random permutation.

We also show that the above problem is equivalent to a more tangible one concerning the possibility of detecting a certain tampering in a deck of cards.