Long cycles in a random permutation

HardCombinatorics Expected Value~10m

Let $C_n$ be the number of cycles longer than $n$ (i.e. of length $> n$ ) in a uniformly random permutation of $\{1, 2, \dots, 2n\}$ . Compute $\displaystyle\lim_{n\to\infty}\mathbb{E}[C_n]$ . The limit has the form $\ln(q)$ for a rational $q$ ; find $q$ .

Show hints (2)+

The expected number of cycles of a given length $\ell$ in a random permutation is $1/\ell$ . Sum over $\ell = n+1,\dots,2n$ .
That sum is $H_{2n}-H_n$ , which tends to $\ln 2$ .

Answer

Reveal answer →

Create a free account to see the full worked solution and track your progress.

Create a free account

Interview format: Market Maker, Systematic & Data-Driven Trading

Long cycles in a random permutation

Answer

Related questions