Law of large numbers for increasing subsequences of random permutations and an approximation result for the uniform measure

Details Law of large numbers for increasing subsequences of random permutations and an approximation result for the uniform measure Law of large numbers for increasing subsequences of random permutations and an approximation result for the uniform measure

2004-07-21

arxiv.org/abs/math/0407353v2

Mathematics

Probability

Scientific paper

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_{n,k_n})=o((EZ_{n,k_n})^2)$ as $ n\to\infty$ if and only if $k_n=o(n^\frac25)$. In particular then, the weak law of large numbers holds for $Z_{n,k_n}$ if $k_n=o(n^\frac25)$. We also show the following approximation result for the uniform measure $U_n$ on $S_n$. Define the probability measure $\mu_{n;k_n}$ on $S_n$ as follows: Consider $n$ cards, numbered from 1 to $n$, and laid out on a table from left to right in increasing order. Place a mark on $k_n$ of the cards, chosen at random. Then pick up all the unmarked cards and randomly insert them between the $k_n$ marked cards that remained on the table. Denote the resulting distribution on $S_n$ by $\mu_{n;k_n}$. The weak law of large numbers holds for $Z_{n,k_n}$ if and only if the total variation distance between $\mu_{n;k_n}$ and $U_n$ converges to 0 as $n\to\infty$. In order to evaluate the asymptotic behavior of the second moment, we need to analyze certain occupation times of certain conditioned two-dimensional random walks.

Affiliated with

Also associated with

No associations

Rating

Law of large numbers for increasing subsequences of random permutations and an approximation result for the uniform measure 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 Law of large numbers for increasing subsequences of random permutations and an approximation result for the uniform measure, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Law of large numbers for increasing subsequences of random permutations and an approximation result for the uniform measure will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-1012