Skip to content

Expected number of long cycles in a random permutation

Question

For a uniformly random permutation of {1,2,…,2n}\{1,2,\dots,2n\}, let CnC_n be the number of its cycles whose length exceeds nn. The limit lim⁡n→∞E[Cn]\lim_{n\to\infty}\mathbb{E}[C_n] equals ln⁡q\ln q for a rational qq. Find qq.

Short answer

q=2q=2. The expected number of kk-cycles in a random permutation of size mm is 1k\tfrac1k for every k≤mk\le m. So E[Cn]=∑k=n+12n1k=H2n−Hn→ln⁡2\mathbb{E}[C_n]=\sum_{k=n+1}^{2n}\tfrac1k=H_{2n}-H_n\to\ln2.

Adapted from QuantQuestions.io; question and answer rewritten by SelfMadeQuant.com.

See the hint and the full worked solution in the question bank (free account).

Open the worked solution

Lessons behind this question

Start with a free lesson: Expectation, Variance and Covariance is part of a free topic. Create a free account, no card needed, to read it in full with worked solutions.

Read it free