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

DOI10.1002/RSA.20113arXivmath/0407353WikidataQ115150373 ScholiaQ115150373MaRDI QIDQ6474271FDOQ6474271

Publication date: 21 July 2004

Abstract: 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

V a r (Z_{n, k_{n}}) = o ((E Z_{n, k_{n}})^{2})

as

n o i n f t y

if and only if

k_{n} = o (n^{f} r a c 25)

. In particular then, the weak law of large numbers holds for

Z_{n, k_{n}}

if

k_{n} = o (n^{f} r a c 25)

. We also show the following approximation result for the uniform measure

U_{n}

on

S_{n}

. Define the probability measure

m u_{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

m u_{n; k_{n}}

. The weak law of large numbers holds for

Z_{n, k_{n}}

if and only if the total variation distance between

m u_{n; k_{n}}

and

U_{n}

converges to 0 as

n o i n f t y

. 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.

Mathematics Subject Classification ID

Central limit and other weak theorems (60F05) Combinatorial probability (60C05)

This page was built for publication: Law of large numbers for increasing subsequences of random permutations and an approximation result for the uniform measure

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6474271)