0479-1992 东大工 数学 WEB

概率统计 古典概型 数学期望 信封收集问题

区別可能な $N$ 個のボールが入っている壺がある。この壺からボール1個を取り出し、また壺へ戻すという操作を繰り返す。ただし、個々のボールが選択される確率は等しいものとする。このとき以下の問に答えよ。

(1) $N=3$ のとき、$r$ 回目 ($r\ge 3$) の操作で初めて3個のボールすべてが少なくとも1回は選択される確率を求めよ。

(2) $N=3$ のとき、(1)の結果を利用して、3個のボールすべてが少なくとも1回選択されるまでに要する操作の回数の期待値を求めよ。

(3) ボールの個数が一般に $N$ の場合、$N$ 個のボールすべてが少なくとも1回選択されるまでに要する操作の回数の期待値を求めよ。

---

解答：

(1)
$r$ 回目で初めて3個のボールすべてが選択されるためには、以下の条件を両方満たす必要がある。

• $r-1$ 回目までの操作で、ちょうど2種類のボールが選択される。
• $r$ 回目の操作で、まだ選択されていない残り1種類のボールが選択される。

$r-1$ 回目までに選ばれる2種類のボールの選び方は $\left(\genfrac{}{}{0ex}{}{3}{2}\right)=3$ 通り。
選ばれた2種類のボールで $r-1$ 回の列を作る方法は $2^{r-1}$ 通り。ただし、1種類しか選ばれない2通りの場合を除くため、$2^{r-1}-2$ 通り。
各列が発生する確率は ${\left(\frac{1}{3}\right)}^{r-1}$。
したがって、$r-1$ 回目までにちょうど2種類のボールが選ばれる確率は

$$3\times \frac{2^{r-1}-2}{3^{r-1}}$$
$r$ 回目に残り1種類のボールを引く確率は $\frac{1}{3}$ である。求める確率 $P_r$ は、
$$P_r=3\times \frac{2^{r-1}-2}{3^{r-1}}\times \frac{1}{3}=\frac{2^{r-1}-2}{3^{r-1}}$$

$$\boxed{\frac{2^{r-1}-2}{3^{r-1}}}$$

(2)
求める期待値 $E_3$ は、(1)で求めた確率を用いて次のように表される。

$$E_3=\sum _{r=3}^{\infty }r{P}_r=\sum _{r=3}^{\infty }r\frac{2^{r-1}-2}{3^{r-1}}=\sum _{r=3}^{\infty }r\left({\left(\frac{2}{3}\right)}^{r-1}-2{\left(\frac{1}{3}\right)}^{r-1}\right)$$
ここで、級数の公式 $\sum _{k=1}^{\infty }k{x}^{k-1}=\frac{1}{(1-x{)}^2}(|x|<1)$ を用いる。$k=1,2$ の項を引くことで、$k\ge 3$ の和を得る。
$$\sum _{r=3}^{\infty }r{x}^{r-1}=\frac{1}{(1-x{)}^2}-1-2x$$
$x=\frac{2}{3}$ のとき：
$$\sum _{r=3}^{\infty }r{\left(\frac{2}{3}\right)}^{r-1}=\frac{1}{(1-2/3{)}^2}-1-2\left(\frac{2}{3}\right)=9-1-\frac{4}{3}=\frac{20}{3}$$
$x=\frac{1}{3}$ のとき：
$$\sum _{r=3}^{\infty }r{\left(\frac{1}{3}\right)}^{r-1}=\frac{1}{(1-1/3{)}^2}-1-2\left(\frac{1}{3}\right)=\frac{9}{4}-1-\frac{2}{3}=\frac{7}{12}$$
これらを代入して期待値を計算する。
$$E_3=\frac{20}{3}-2\times \frac{7}{12}=\frac{20}{3}-\frac{7}{6}=\frac{33}{6}=\frac{11}{2}$$

$$\boxed{\frac{11}{2}}$$

(3)
$i-1$ 種類のボールがすでに選択された状態から、新しい $i$ 種類目のボールが選択されるまでの操作回数を $X_i$ とする。
全体の操作回数 $X$ は $X=X_1+X_2+\cdots +X_N$ と表せる。
$X_i$ は、毎回の試行における成功確率 $p_i$ が

$$p_i=\frac{N-(i-1)}{N}$$
である幾何分布に従う。
幾何分布の期待値は $E[X_i]=\frac{1}{p_i}$ であるため、
$$E[X_i]=\frac{N}{N-i+1}$$
期待値の線形性より、求める期待値 $E[X]$ は
$$E[X]=\sum _{i=1}^{N}E[X_i]=\sum _{i=1}^N\frac{N}{N-i+1}$$
和の順序を逆にして $k=N-i+1$ とおくと、
$$E[X]=N\sum _{k=1}^N\frac{1}{k}$$

$$\boxed{N\sum _{k=1}^N\frac{1}{k}}$$

---

本题考查了概率论中著名的“信封收集问题”（Coupon Collector’s Problem）的推导与计算。
第一问和第二问要求通过穷举特定组合并构造无穷级数求和的方式来直接计算。对于恰好在第r次完成收集的概率，需利用乘法原理分步计算：前r-1次必须恰好出现N-1种结果，而最后一次必须是未出现过的那1种。求期望时涉及了形如等差乘等比的幂级数求和，通过对等比数列求导（或者错位相减法）可以得到标准公式。注意本题中求和的下限是从3开始的，需要从总和中剔除前两项。
第三问则展示了处理此类问题更加巧妙和通用的方法：将复杂的总操作次数分解为多个独立的几何分布随机变量之和。因为每次寻找“新球”的过程都是一次独立的伯努利试验，直至成功为止，这完美契合几何分布的定义。利用期望的线性性质（即和的期望等于期望的和），直接将所有阶段的期望值相加，避免了N次多项式展开的复杂极限计算，从而得出含有调和级数的优美结论。