Long cycles in a random permutation

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

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

Answer

Reveal answer →

2

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

Asked at: Jane Street, Two Sigma

Related questions