How many long cycles?

HardProbability Combinatorics~10m

Let $C_n$ be the number of cycles of length greater than $n$ in a uniformly random permutation of $\{1, 2, \dots, 2n\}$ . Compute $\displaystyle\lim_{n \to \infty} \mathbb{E}[C_n]$ .

Show hints (2)+

In a random permutation of $m$ items, $\mathbb{E}[\#\text{ cycles of length }k]=\tfrac1k$ for $k\le m$ .
Sum over $k=n+1,\dots,2n$ : that's $H_{2n}-H_n\to\ln 2$ .

Answer

Reveal answer →

0.6931 (± 0.005)

Want the full step-by-step worked solution? It's part of Premium - along with a worked solution for every question in the bank.

Practise free Unlock solutions

Asked at: Jane Street, Two Sigma

How many long cycles?

Answer

Related questions