大学数学基礎解説

さいころを何回振れば６つの目がそろうのか？（クーポンコレクター問題）

期待値,クーポンコレクター問題,確率

2050

長い数式が出てきます。スマホで閲覧の場合は横向きにすることを推奨します。

この記事でやること

次の問題を考えます。なお，この記事における「さいころ」とは，$1$から$6$の目が等確率で出力される装置のことをいいます。

クーポンコレクター問題；n=6

$1$つのさいころを繰り返し投げ，$6$つの目がすべて出るまでこの試行を続けるとき，投げた回数の期待値はいくつか？

例えば適当にさいころを繰り返し投げてみました。（正確にはPythonで，$1$から$6$までの整数値を取る疑似乱数をとっています。）$$ \boxed{\bs 5,5,\bs 1,\bs 2,2,\bs 3,2,\bs 6,\bs 4}\quad (\text{9 times}) $$ $$ \boxed{\bs1,\bs3,\bs6,6,6,\bs5,\bs4,6,5,5,5,6,1,3,6,5,5,5,5,\bs2}\quad (\text{20 times}) $$
運が良い人は$6$回で終わり，運が悪ければ$100$回投げても終わらないかもしれません。

この期待値の導出を，幾何分布に頼らずに$2$通りの計算をしてみました。

和の期待値と期待値の和

まずは$1$つ目の視点です。次のように考えます。

初めて$1$個目の目が出る回数の期待値を求める
$1$個の目が出ていて，そのあとに初めて$2$個めの目が出る回数の期待値を求める
$2$個の目が出ていて，そのあとに初めて$3$個めの目が出る回数の期待値を求める
$3$個の目が出ていて，そのあとに初めて$4$個めの目が出る回数の期待値を求める
$4$個の目が出ていて，そのあとに初めて$5$個めの目が出る回数の期待値を求める
$5$個の目が出ていて，そのあとに初めて$6$個めの目が出る回数の期待値を求める
和の期待値は期待値の和であることを用いて，求めたい期待値を出す。

赤字の部分については，次の通りです。

和の期待値は期待値の和

$2$つの確率変数$X$と$Y$について，確率変数$(X+Y)$の期待値$E[X+Y]$について，
$E[X+Y]=E[X]+E[Y]$が成り立つ。

つまり，1.から6.までで出した期待値の和を取ればよいですね。

まず，初めて$1$個の目が出る期待値は$1$回ですね。自明です。

次に，「$1$個の目が出ていて，そのあとに初めて$2$個めの目が出る期待値」を求めましょう。この期待値は，

$$ 1\cdot\bunsuu56+2\cdot\bunsuu56\cdot\bunsuu16+3\cdot\bunsuu56\cdot\left(\bunsuu16\right)^2+4\cdot\bunsuu56\cdot\left(\bunsuu16\right)^3+\dots+k\cdot\bunsuu56\cdot\left(\bunsuu16\right)^{k-1}+\dots $$
と書き表せます。つまり，次の部分和$S_n$の極限値です。$$ S_n=1\cdot\bunsuu56+2\cdot\bunsuu56\cdot\bunsuu16+3\cdot\bunsuu56\cdot\left(\bunsuu16\right)^2+4\cdot\bunsuu56\cdot\left(\bunsuu16\right)^3+\dots+n\cdot\bunsuu56\cdot\left(\bunsuu16\right)^{n-1} $$
これは，目を凝らせば“等差×等比”の形ですので，なんだかんだで$$ S_n=\bunsuu65\left\{1-\left(\bunsuu16\right)^{n}\right\}-\bunsuu{n}{6^n} $$
と計算できます。従って$\displaystyle\lim_{n\to\infty}S_n=\bunsuu65$です。

同様の計算を，他の場合でも続けていくと，以下のようにまとまります。

初めて$1$個目の目が出る期待値は$1$
$1$個の目が出ていて，そのあとに初めて$2$個めの目が出る期待値は$\bunsuu65$
$2$個の目が出ていて，そのあとに初めて$3$個めの目が出る期待値は$\bunsuu32$
$3$個の目が出ていて，そのあとに初めて$4$個めの目が出る期待値は$2$
$4$個の目が出ていて，そのあとに初めて$5$個めの目が出る期待値は$3$
$5$個の目が出ていて，そのあとに初めて$6$個めの目が出る期待値は$6$

というわけでこれらを足せば望みの解答が出せ，

$$ 1+\bunsuu65+\bunsuu32+2+3+6=\bm{14.7} $$

となり，問題の答えは$14.7$回であることが言えました。

ちなみにこの解答の類似は，数学ガール/乱択アルゴリズム (数学ガールシリーズ 4)(Amazon) の第5章にもあります。【幸せの階段】を昇っており，明快かつ軽やかな進行で問題を解いています。（宣伝）

直接計算したい！

“和の期待値は期待値の和”なんて使いたくないよ！という場合は，次のようにしてゴリゴリ計算しましょう。

さいころを$n$回投げて$n+1$回目に初めて$6$種類の目がそろう確率を$p_n$としますと，$n\geqq 1$のとき，$$ p_n=\bunsuu{\kumiawase{5}{5}\cdot5^n-(\kumiawase{5}{4}\cdot4^n-(\kumiawase{5}{3}\cdot3^n-(\kumiawase{5}{2}\cdot2^n-(\kumiawase{5}{1}\cdot1^n))))}{6^n} $$
です。ちなみに代入すれば$p_1=p_2=p_3=p_4=0,\ p_5=\bunsuu{5}{324}=\bunsuu{6!}{6^6}$ですね。

$p_n$を変形すれば，$$ p_n=\left(\bunsuu56\right)^n-5\left(\bunsuu23\right)^n+10\left(\bunsuu12\right)^n-10\left(\bunsuu13\right)^n+5\left(\bunsuu16\right)^n $$
です。このとき求める期待値$E$は，$$ E=\sum_{n=1}^{\infty}(n+1)p_n $$
です。後はこれを直接計算してやればよいですね。以下の計算結果を使います。

計算を楽に行うために

$0< r<1$のとき，$\displaystyle\sum_{n=1}^\infty (n+1)r^n=\bunsuu{1}{(1-r)^2}-1$

これを使えば，$$ \begin{align} E&=\sum_{n=1}^\infty (n+1)p_n\\ &=\sum_{n=1}^\infty (n+1)\left\{\left(\bunsuu56\right)^n-5\left(\bunsuu23\right)^n+10\left(\bunsuu12\right)^n-10\left(\bunsuu13\right)^n+5\left(\bunsuu16\right)^n\right\}\\ &=(36-1)-5(9-1)+10(4-1)-10\left(\bunsuu94-1\right)+5\left(\bunsuu{36}{25}-1\right)\\ &=\bm{14.7} \end{align} $$
と計算でき，確かに先ほど求めた$14.7$という数字と一致していますね。