クーポンコレクター問題

f:id:tkenichi:20120821102635j:plain

クーポンコレクター問題とは、n種類のクーポンがランダムに入っている商品について、全部そろえるにはどれくらい買えばよいか、という問題である。キャラクターグッズのおまけをそろえたりする場合を考えればわかりやすいだろう。

n種類のクーポンがすべて同じ確率 $p = \frac{1}{n}$ であらわれるとする。よくある解法では、k個そろっている状態からk+1個そろっている状態へ遷移する確率が $1-kp = 1 - \frac{k}{n}$ であることに着目する。k 個から k+1 個へ遷移するためには、平均 $\frac{n}{n-k}$ 回かかる。よって、0個の状態からn個の状態に遷移するにはこれらを全部足して

$\sum_{k=0}^{n-1} \frac{n}{n-k}$

である。

さて、この問題をちょっと拡張して考えてみた。n種類のクーポンがそれぞれ異なる確率で現れる場合はどうなるだろうか？その確率を $p_1, p_2, \cdots, p_n$ とする。クーポンが現れる順番で分岐していくので、その枝ごとに確率を求めてみる。まず、 $1, 2, \cdots, n$ の順番の場合を考える。k 個そろっている状態から k+1 個そろっている状態へ遷移する確率は $p_{k+1} + \cdots + p_n$ であり、k 個そろっている状態にとどまっている確率は $p_{1}+\cdots+p_{k}$ である。k 個から k+1 個へ n 回で遷移する確率は

$(p_1 + \cdots + p_k)^{n-1}(p_{k+1} + \cdots + p_n)$

であるから、その平均回数は

$\frac{1}{p_{k+1} + \cdots + p_n}$

である。ここでは k+1 番目にどの枝に分岐するかは問わないことに注意する。 $1, 2, \cdots, n$ の順に遷移する枝の確率は

$p(1,2,..,n) := \frac{p_1}{p_1 + \cdots + p_{n}} \times \frac{p_2}{p_2 + \cdots + p_n} \times \cdots \times \frac{p_{n-1}}{p_{n-1} + p_n} \times \frac{p_n}{p_n}$

である。従って、すべてそろえるための平均回数は

$\sum p(1,2,..,n) \sum_{k=1}^n ( \frac{1}{p_{k} + \cdots + p_n} )$

である。最初の和はすべての枝についての和をあらわす。すなわち、1からnまでのクーポン番号の並び替えである。和の中身は1,2,3,...,n の順に現れた場合を記述している。

例として、n=3ですべて 1/3 のときと、(1/2,1/4,1/4) の場合で計算してみよう（前者の計算は検算のため）。
前者の場合は、すべての枝について和の中身は同じで、枝の本数は6本あるので

$6 \times \frac{1}{3} \times \frac{1}{2} \times \frac{1}{1} \times ( \frac{3}{3} + \frac{3}{2} + \frac{3}{1} ) = \frac{11}{2}$

となる。後者の場合は (1/2,1/4,1/4) の順で現れる場合の枝の本数は2本

$2 \times \frac{1}{2} \times \frac{1}{2} \times \frac{1}{1} \times ( 1 + 2 + 4 ) = \frac{7}{2}$

(1/4,1/2,1/4) の順で現れる場合の枝の本数は2本

$2 \times \frac{1}{4} \times \frac{2}{3} \times \frac{1}{1} \times ( 1 + \frac{4}{3} + 4 ) = \frac{19}{9}$

(1/4,1/4,1/2) の順で現れる場合の枝の本数は2本

$2 \times \frac{1}{4} \times \frac{1}{3} \times \frac{1}{1} \times ( 1 + \frac{4}{3} + 2 ) = \frac{13}{18}$

となるので、平均値はこれらを足して $\frac{57}{9}$ となる。

また面白い練習問題として、クーポンが3種類で (2/3, 1/6, 1/6) の確率のときと、4種類ですべて 1/4 の確率のときでは、前者のほうがそろえる平均の回数は大きくなる。

tkenichi の日記

毒舌皮肉系恥さらし日記

クーポンコレクター問題