返回题库

随机排列中“长循环”的期望个数极限

Half Cycle

专题
Discrete Math / 离散数学
难度
L6

题目详情

令 CnC_n 表示对集合 {1,2,…,2n}\{1,2,\dots,2n\} 的随机排列（均匀随机）中，“长度大于 nn 的循环（cycle）”的个数。求

lim⁡n→∞E[Cn].\lim_{n\to\infty}\mathbb{E}[C_n].

已知答案形如 ln⁡(q)\ln(q)，其中 qq 为有理数。求 qq。

Let CnC_n count the number of cycles in a random permutation of {1,2,…,2n}\{1,2,\dots, 2n\} that are larger than nn in length. Compute lim⁡n→∞E[Cn]\displaystyle \lim_{n \rightarrow \infty} \mathbb{E}[C_n]. The answer is in the form ln⁡(q)\ln(q) for some rational number qq. Find qq.

解析

随机排列中长度为 kk 的循环的期望个数为 1/k1/k。

因此

E[Cn]=∑k=n+12n1k→n→∞∫121x dx=ln⁡2.\mathbb{E}[C_n]=\sum_{k=n+1}^{2n}\frac{1}{k} \xrightarrow[n\to\infty]{} \int_1^2\frac{1}{x}\,dx=\ln 2.

所以 q=2q=2。

Original Explanation

First, we need to find the expected number of k−k-cycles in our permutation for k>nk > n. Then, we can sum those up from n+1n+1 to 2n2n to get E[Cn]\mathbb{E}[C_n].

First, let's fix some n+1≤k≤2nn+1 \leq k \leq 2n. Let XiX_i be the indicator of whether or not the value ii belongs to a cycle of length kk. Then we have that

T=∑i=12nXikT = \dfrac{\displaystyle \sum_{i=1}^{2n}X_i}{k}

gives the total number of k−k-cycles, as we need to remove rotations (kk such rotations per k−k-cycle). Using linearity of expectation, we have that

E[T]=1k∑i=12nE[Xi]=2nkE[X1]\mathbb{E}[T] = \dfrac{1}{k}\displaystyle \sum_{i=1}^{2n} \mathbb{E}[X_i] = \dfrac{2n}{k}\mathbb{E}[X_1]

E[X1]\mathbb{E}[X_1] is just the probability 11 belongs to a k−k-cycle. There are (2n)!(2n)! permutations of {1,2,…,2n}\{1,2,\dots, 2n\}. There are (2n−1k−1)\displaystyle \binom{2n-1}{k-1} ways to pick k−1k-1 more elements to belong to the k−k-cycle. Now that we have selected the elements, there are (k−1)!(k-1)! ways to arrange those elements. Then, there are (2n−k)!(2n-k)! ways to arrange the other 2n−k2n-k elements. This yields that our probability that 11 belongs to a cycle is

(2n−1k−1)(k−1)!(2n−k)!(2n)!=12n\dfrac{\binom{2n-1}{k-1}(k-1)!(2n-k)!}{(2n)!} = \dfrac{1}{2n}

Therefore, E[T]=1k\mathbb{E}[T] = \dfrac{1}{k} after substituting in.

The above tells us that the expected number of k−k-cycles for 1≤k≤2n1 \leq k \leq 2n is 1k\dfrac{1}{k}. Therefore, E[Cn]\mathbb{E}[C_n] is just the sum of the terms above from n+1n+1 to 2n2n. Namely,

E[Cn]=∑k=n+12n1k=∑k=n+12n1kn⋅1n\mathbb{E}[C_n] = \displaystyle \sum_{k = n+1}^{2n} \dfrac{1}{k} = \displaystyle \sum_{k = n+1}^{2n} \dfrac{1}{\frac{k}{n}} \cdot \dfrac{1}{n}

This is starting to look like a Riemann Integral. Let x=knx = \dfrac{k}{n} so that dx=1ndx = \dfrac{1}{n} (this is a discrete sum currently, so dxdx is just change between terms). The lower bound of our integral is xL=n+1n→1x_L = \dfrac{n+1}{n} \rightarrow 1, while the upper bound is xU=2nn=2x_U = \dfrac{2n}{n} = 2. As n→∞n \rightarrow \infty, this sum converges to the Riemann Integral

∫121xdx=ln⁡(2)\displaystyle \int_1^2 \dfrac{1}{x}dx = \ln(2)

Therefore, q=2q = 2.