转盘重复数问题

题目描述

设有一个转盘被均分为 $n$ 个区域，分别标号为 $\{1, 2, \dots, n\}$。每次旋转转盘，各数字出现的概率均为 $\frac{1}{n}$。重复旋转，记录出现的数字序列 $X_1, X_2, \dots$。实验在首次出现重复数字时停止。令随机变量 $S = X_1 + X_2 + \dots + X_T$，其中 $T+1$ 是首次出现重复数字的时刻。求 $E[S]$。

解题思路

记样本空间为 $\Omega = \{1, 2, \dots, n\}$，记录的数字集合为 $A = \{X_1, X_2, \dots, X_T\}$。

根据期望的线性性质，$E[S] = E\left[\sum_{i=1}^{n} i \cdot \mathbf{1}_{\{i \in A\}}\right] = \sum_{i=1}^{n} i \cdot P(i \in A)$。（其中 $\mathbf{1}_{\{i \in A\}}$ 是指示函数，当 $i \in A$ 时取值为 1，否则为 0。）

考虑任意数字 $i, j \in \Omega$，由对称性可知，任意两个数字被记录的概率相同，即 $P(i \in A) = P(j \in A)$。因此，设 $P(i \in A) = p$，则有：

$$E[S] = \sum_{i=1}^{n} i \cdot p = \frac{n(n+1)}{2} \cdot p$$

计算 $p$。根据期望的线性性质，$E[T] = \sum_{i=1}^{n} E[\mathbf{1}_{\{i \in A\}}] = \sum_{i=1}^{n} P(i \in A) = n \cdot p$。

则 $E[S] = \frac{n(n+1)}{2} \cdot \frac{E[T]}{n} = \frac{n+1}{2} E[T]$。

计算 $E[T]$。$T$ 是在出现重复前选出的不同元素个数。$P(E \geq k)$ 表示前 $k$ 个元素都不重复的概率，即：

$$P(E \geq k) = \frac{n}{n} \cdot \frac{n-1}{n} \cdot \frac{n-2}{n} \cdots \frac{n-k+1}{n} = \frac{n!}{(n-k)! n^k}$$

由期望的定义，$E[T] = \sum_{k=1}^{n} P(E \geq k) = \sum_{k=1}^{n} \frac{n!}{(n-k)! n^k}$。

因此，最终结果为：

$$\boxed{E[S] = \frac{n+1}{2} \sum_{k=1}^{n} \frac{n!}{(n-k)! n^k}}$$

变体问题

变体一：转盘被均分为 $n+1$ 个区域，其中一个区域为空白，其余规则不变。

解答：

空白区域既不计入 $S$ 的求和，也不会导致实验提前停止。因此，空白区域对数字序列没有影响；换言之，考虑转盘得到的数字序列 $X_1, X_2, \dots$，在忽略空白后，与原问题完全相同。

因此，变体一的期望值与原问题相同。

变体二：转盘被均分为 $n+1$ 个区域，其中一个区域为空白，且当转到空白区域或者已经出现过的数字时，实验停止。

解答：

以数字 0 表示空白区域，新的停止条件变为了出现 0 或者出现重复数字。

$P(E \geq k)$ 表示前 $k$ 个元素都不重复且不为 0 的概率，即：

$$P(E \geq k) = \frac{n}{n+1} \cdot \frac{n-1}{n+1} \cdot \frac{n-2}{n+1} \cdots \frac{n-k+1}{n+1} = \frac{n!}{(n-k)! (n+1)^k}$$

除此之外，$E[T]$ 的计算方法与原问题相同。代入 $E[S] = \frac{n+1}{2} E[T]$，

最终结果为：

$$\boxed{E[S] = \frac{n+1}{2} \sum_{k=1}^{n} \frac{n!}{(n-k)! (n+1)^k}}$$