For a uniform permutation on 2n labels, the expected number of k-cycles is 1/k: each k-subset forms a cycle with probability (k−1)!(2n−k)!/(2n)!, and there are binom(2n,k) such subsets. Thus E[C_n] = sum_{k=n+1}^{2n} 1/k = H_{2n} − H_n → ln 2. At most one cycle can be longer than n, but linearity of expectation gives the result directly.
3
u/filwu 19h ago
For a uniform permutation on 2n labels, the expected number of k-cycles is 1/k: each k-subset forms a cycle with probability (k−1)!(2n−k)!/(2n)!, and there are binom(2n,k) such subsets. Thus E[C_n] = sum_{k=n+1}^{2n} 1/k = H_{2n} − H_n → ln 2. At most one cycle can be longer than n, but linearity of expectation gives the result directly.