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

この記事でやること

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

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

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

和の期待値と期待値の和

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

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

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

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

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

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

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

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

1. 初めて$1$個目の目が出る期待値は$1$
2. $1$個の目が出ていて，そのあとに初めて$2$個めの目が出る期待値は${\displaystyle \frac{6}{5}}$
3. $2$個の目が出ていて，そのあとに初めて$3$個めの目が出る期待値は${\displaystyle \frac{3}{2}}$
4. $3$個の目が出ていて，そのあとに初めて$4$個めの目が出る期待値は$2$
5. $4$個の目が出ていて，そのあとに初めて$5$個めの目が出る期待値は$3$
6. $5$個の目が出ていて，そのあとに初めて$6$個めの目が出る期待値は$6$

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

$$1+{\displaystyle \frac{6}{5}}+{\displaystyle \frac{3}{2}}+2+3+6=\mathbf{14.7}$$

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

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

直接計算したい！

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

さいころを$n$回投げて$n+1$回目に初めて$6$種類の目がそろう確率を$p_n$としますと，$n\geqq 1$のとき，$$p_n={\displaystyle \frac{{}_5{\text{C}}_5\cdot 5^n-({}_5{\text{C}}_4\cdot 4^n-({}_5{\text{C}}_3\cdot 3^n-({}_5{\text{C}}_2\cdot 2^n-({}_5{\text{C}}_1\cdot 1^n))))}{6^n}}$$
です。ちなみに代入すれば$p_1=p_2=p_3=p_4=0,p_5={\displaystyle \frac{5}{324}}={\displaystyle \frac{6!}{6^6}}$ですね。

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

これを使えば，$$\begin{array}{rl}E& =\sum _{n=1}^{\mathrm{\infty }}(n+1)p_n\\ & =\sum _{n=1}^{\mathrm{\infty }}(n+1)\{{\left({\displaystyle \frac{5}{6}}\right)}^n-5{\left({\displaystyle \frac{2}{3}}\right)}^n+10{\left({\displaystyle \frac{1}{2}}\right)}^n-10{\left({\displaystyle \frac{1}{3}}\right)}^n+5{\left({\displaystyle \frac{1}{6}}\right)}^n\}\\ & =(36-1)-5(9-1)+10(4-1)-10({\displaystyle \frac{9}{4}}-1)+5({\displaystyle \frac{36}{25}}-1)\\ & =\mathbf{14.7}\end{array}$$
と計算でき，確かに先ほど求めた$14.7$という数字と一致していますね。

まとめ

クーポンコレクター問題の具体的な状況について考えていきました。

直接計算の節では，場合の数から“真面目に”攻めるという方法を取りましたが，この方法でクーポンコレクター問題を解いている解説記事が（僕の検索力では）見つからなかったため，１つの解法として実用性があるかどうかはともかく，面白いのではないかと感じています。

ここまでご覧いただきありがとうございます。

追記

コメントにおける とが さんから面白い解法をいただきました。そちらの議論も合わせてご覧ください！