4種のカードをそろえるまでの回数の期待値(期待値と調和数)

方針

解答

⓪ 発想 — どう考え始めるか。 「全部そろうまで」を一気に考えると手が出ない。“何種類そろったか”という段階に刻むのが鍵だ。

すでに $j$ 種そろっているとき、次の1枚が新種である確率は $\frac{4-j}{4}$。毎回確率 $p$ で当たる独立な試行では、初当たりまでの回数の期待値は $\frac{1}{p}$(幾何分布)。

だから各段階の“待ち時間”の期待値を出して、$0\to 1\to 2\to 3\to 4$ 種と進む分を全部足せばよい。この分割を許すのが期待値の線形性だ。

① 各段階の待ち回数の期待値。 $j$ 種そろった状態から $j+1$ 種目が出る確率は $p_j=\frac{4-j}{4}$。その待ち回数の期待値は $\frac{1}{p_j}=\frac{4}{4-j}$。

② 段階を足し合わせる。 $j=0,1,2,3$ の合計が、そろうまでの総回数の期待値(期待値の線形性)。 $$E=\sum _{j=0}^3\frac{4}{4-j}=\frac{4}{4}+\frac{4}{3}+\frac{4}{2}+\frac{4}{1}=4\left(1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}\right).$$ ③ 計算する。 $1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}=\frac{12+6+4+3}{12}=\frac{25}{12}$ だから $$E=4\cdot \frac{25}{12}=\frac{25}{3}.$$

まとめ “全部そろう”時間は、“新種が出るたびに1段上がる”と刻めば、各段が幾何分布の平均 $\frac{1}{p}$。それを足すと調和数 $1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}$ が現れる。確率(期待値)と数列(調和和)の融合。一般に $n$ 種なら $n\left(1+\frac{1}{2}+\cdots +\frac{1}{n}\right)$。

発展 — 一歩先へ。 $n$ 種なら期待値は $n\left(1+\frac{1}{2}+\cdots +\frac{1}{n}\right)$。かっこの中(調和数)はおよそ $\log n$ の速さでしか増えないが、それでも $50$ 種のカードなら約 $225$ 回かかる。“最後の $1$ 種”ほど待ちが長い — 集め物の後半がつらい理由が式に出ている。

別解

別解 — 「まだそろっていない確率」を足し上げる(得意な人向けの高い視点)。 回数 $T$ の期待値は、$E[T]=\sum _{t\ge 0}P(T>t)$ という“しっぽの和”でも計算できる($t$ 回目以降まで続く分が $1$ 回ずつ寄与する)。

$P(T>t)$ は「$t$ 回引いてもどれかの種類が欠けている確率」。どの種類が欠けるかで包除原理を使うと、$t\ge 1$ で

$$P(T>t)=4{\left(\frac{3}{4}\right)}^t-6{\left(\frac{1}{2}\right)}^t+4{\left(\frac{1}{4}\right)}^t,P(T>0)=1.$$

$t\ge 1$ の部分を足すと、それぞれ無限等比級数で $3$、$1$、$\frac{1}{3}$。よって

$$E[T]=1+4\cdot 3-6\cdot 1+4\cdot \frac{1}{3}=1+12-6+\frac{4}{3}=\frac{25}{3}.$$

段階に刻む本解と、包除で一気に書くこの解が同じ $\frac{25}{3}$ に着地する。包除原理と無限等比級数まで動員する分、こちらは視界が広い。