趣题: 好点个数的期望值

趣题: 好点个数的期望值 #

题目 #

在区间 $[0,1]$ 上按均匀分布独立地画 $n$ 个点 ($n\geq 3$). 定义一个点 $P$ 的邻居为最靠近 $P$ 的点. 若一个点的邻居的邻居是它本身, 那么我们称这个点是好点. 求好点个数的数学期望.

Solution 1 #

由好点的定义, 如果 $A$ 是好点, 它的邻居是 $B$ , 那么 $B$ 也满足好点的性质, 故好点是成对出现的. 记 $\epsilon_{i, j}$ 为点 $i, j$ 是否为一对好点 (以取值 $1$ 或 $0$ 表示) , 则好点个数 $$Y = \sum_{1\leq i<{j}\leq n}{2\epsilon_{i, j}}$$ 有 $$E[Y] = \sum_{1\leq i<{j}\leq n}{2E[\epsilon_{i, j}]} = n(n - 1)E[\epsilon_{1, 2}]$$ $E[\epsilon_{1,2}]$ 即为 $X_1, X_2$ 互为邻居的概率. 假设 $X_1 \leq X_2$ , 我们计算 $X_1, X_2$ 互为邻居的概率($E[\epsilon_{1, 2}]$ 是这个概率的两倍). 有以下三种可能的情况:

• $X_1, X_2$ 在区间中间;
• $X_1, X_2$ 在区间最左侧;
• $X_1, X_2$ 在区间最右侧;

以第一种情况为例, 计算 $$P(X_2 - X_1 \leq X_1, \X_2 - X_1 \leq 1 - X_2,
\X_3\in[0, X_1 - (X_2 -1)]\cup[X_2 + (X_2 - X_1), 1], \…, \X_n\in[0, X_1 - (X_2 -1)]\cup[X_2 + (X_2 - X_1), 1])
$$ 这是一个略烦琐的二重积分, 计算结果为 $\frac{1}{3n}$ . 第二、三种情况的计算结果均为 $\frac{1}{6n(n - 1)}$ . 所以 $$E[Y] = n(n - 1)E[\epsilon_{1,2}] \= n(n - 1)\times 2(\frac{1}{3n} + \frac{1}{6n(n - 1)} + \frac{1}{6n(n - 1)}) \= \frac{2n}{3}$$

Solution 2 #

记目标期望为 $f(n)$ . 假设 $X_1 \leq X_2 \leq …\leq X_n$ , 记 $Y_1 = X_2 - X_1 , …, Y_{n - 1} = X_n - X_{n - 1}$ , 则 $Y_i$ 独立同分布. 因为 $X_1$ 的邻居只可能是 $X_2$ , 如果 $Y_1 \leq Y_2$ , 则 $X_1, X_2$ 是一对好点, 且 $X_3$ 的邻居只可能是 $X_4$ , 这时问题化归为 $n - 2$ 个点的情况; 如果 $Y_1 > Y_2$ , 则 $X_2$ 的邻居只可能是 $X_3$, 化归到了 $n - 1$ 个点的情况. 显然 $Y_1 \leq Y_2$ 与 $Y_1 > Y_2$ 概率相等, 故有递推式 $f(n) = \frac{1}{2}[f(n-1) + 2] + \frac{1}{2}f(n - 2)$ . 不难得到 $f(n) = \frac{2n}{3}$ .