有放回抽取n个编号球至出现重复时的抽取次数期望值求解

嘿，这个问题其实是经典「生日问题」的期望版本，咱们一步步拆解清楚，保证你能看明白～

首先明确问题场景：有n个编号1到n的球，每次有放回随机抽一个并记录编号，**直到第一次抽到某个已经抽过的球（也就是出现重复）**时停止，求总共抽取次数的期望值。

核心思路：递推法 #

我们用状态递推的方式来计算期望，先定义一个状态变量：

• 设E_k表示当前已经抽到了k个不同的球时，还需要抽取的次数的期望值。

接下来分情况讨论状态转移：

1. 当k = n时：所有球都已经被抽到过，下一次抽必然会抽到重复的球，所以再抽1次就停止，即 E_n = 1。
2. 当1 ≤ k < n时：此时有两种可能：
   • 概率k/n抽到已经见过的球，直接停止，这部分对期望的贡献为0；
   • 概率(n - k)/n抽到新的球，进入k+1个不同球的状态，需要继续抽取，贡献为E_{k+1}。
     由此得到递推式：E_k = 1 + (n - k)/n * E_{k+1}
3. 当k = 0时：还没开始抽，第一次抽肯定是新球，抽完后进入k=1的状态，所以 E_0 = 1 + E_1（这里的E_0就是我们最终要求的总抽取次数期望值）。

递推展开与最终表达式 #

从E_n = 1开始倒推，把每个E_k依次展开后，最终能得到一个求和形式的表达式：

E[X] = Σ_{k=0}^n P(n, k) / n^k

这里的P(n, k)是排列数，指从n个球中选k个的有序排列数，计算方式为P(n, k) = n * (n-1) * ... * (n - k + 1)（当k=0时，P(n,0)=1）。

把求和式展开写更直观：

E[X] = 1 + n/n + n(n-1)/n² + n(n-1)(n-2)/n³ + ... + n!/n^n

举个例子验证 #

比如n=2时：

• 按公式计算期望 = 1 + 2/2 + 2!/2² = 1 + 1 + 0.5 = 2.5
• 实际验证：X的可能取值为2（概率0.5）或3（概率0.5），期望=20.5 +30.5=2.5，完全一致。

再比如n=3时：

• 按公式计算期望=1 +3/3 +32/9 +32*1/27=1+1+2/3+2/9=26/9≈2.888
• 实际验证：X=2（概率1/3）、X=3（概率4/9）、X=4（概率2/9），期望=2*(1/3)+3*(4/9)+4*(2/9)=26/9，结果正确。

补充说明 #

对于较大的n，还可以用近似公式简化计算，比如经典的生日问题近似：期望值大约是√(πn/2) + 2/3，不过这个近似适合n很大的场景，小n直接用精确求和式更准确。

备注：内容来源于stack exchange，提问作者Peter Mulder