Past exam of the graph Theory and Probabilistic Combinatorics course of the University of Oxford / 2009 / B / 4

Chebyshev's inequality states that if $X$ has finite mean $\mu$ and variance ${\sigma }^2$, then for $t>0$,Indeed $(X-\mu {)}^2\ge t^2{1}_{\{|X-\mu |\ge t\}}$ pointwise. Taking expectations proves the result, including the zero-variance case.

The assumptions implyEventually ${\mu }_n>0$, and $X_n=0$ implies $|X_n-{\mu }_n|\ge {\mu }_n$. Thus Chebyshev's inequality givesNo independence between the different $X_n$ is needed; this is a second moment method.

For each cyclic starting position let $I_i$ indicate that its length-$k$ block is increasing. All $k!$ relative orders of its distinct entries are equally likely, so $\mathbb{E}{I}_i=1/k!$. By linearity of expectation,The indicators need not be independent for this calculation.

Write $X_k={\sum }_i{I}_i$. For two disjoint blocks, their relative orders are independent and each is increasing with probability $1/k!$, giving joint probability $1/(k!{)}^2$. If their cyclic starting positions differ by $s$, with $1\le s<k$, and $k\le n/2$, they overlap in just one interval. Both blocks increasing is then equivalent to their entire length-$k+s$ union increasing, so the joint probability is $1/(k+s)!$.

For each $s$ there are $2n$ ordered overlapping pairs, while there are $n(n-2k+1)$ ordered disjoint pairs and $n$ diagonal pairs. Thus for $k\ge 2$,The tail is bounded using $(k+s)!\ge k!(k+1{)}^s$:Dropping the negative correction in the disjoint term provesFor $k=1$, $X_1=n$ deterministically and the same bound is immediate.

Take $k=k_0=\min \{j:j!\ge n\}$. Then $k\to \infty$ and $(k-1)!<n\le k!$. Also $k=O(\log n)$, because $j!\ge 2^{j-1}$, so the needed block lengths are below $n/2$ for large $n$.

If $L\ge k+1$, then $X_{k+1}\ge 1$. Markov's inequality givesFor $j=k-2$, the expected count satisfies $\mu =n/j!>k-1\to \infty$. Part (ii) bounds its variance by $2\mu$, so Chebyshev's inequality givesCombining the tails provesThe blocks are consecutive in the cyclic order throughout; this is not the longest increasing subsequence with arbitrary omitted positions.

This establishes the longest increasing cyclic run of a random permutation concentration bound.