Two elements in the long cycle

A permutation of {1,2,…,2n}\{1, 2, \dots, 2n\} is chosen uniformly at random. Let pnp_n be the probability that elements 11 and 22 lie in the same cycle and that this cycle has length greater than nn. Compute lim⁡n→∞pn\displaystyle\lim_{n\to\infty} p_n.

Show hints (2)+
  1. The length of the cycle containing element 1 is uniform on {1,…,2n}\{1, \dots, 2n\}.
  2. Given that length is kk, element 2 is in the cycle with probability k−12n−1\tfrac{k-1}{2n-1}. Sum over k>nk > n.

Answer

Reveal answer →

0.375 (± 0.005)

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

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

Related questions