3

さいころを何回振れば6つの目がそろうのか?(クーポンコレクター問題)

1997
1
$$\newcommand{bekutoru}[1]{\displaystyle\overrightarrow{\mbox{#1}\phantom{A}\hspace{-1em}}} \newcommand{bm}[1]{\boldsymbol{#1}} \newcommand{bs}[1]{\bm{\sf \color{red}{#1}}} \newcommand{bunsuu}[2]{\dfrac{\,#1\,}{\,#2\,}} \newcommand{Deg}[0]{^{\circ}} \newcommand{dsqrt}[1]{\displaystyle\sqrt{\,#1\,}} \newcommand{foo}[1]{\ifnum#12\text{それは2だよ!}\else\text{それは2じゃないよ!}\fi} \newcommand{gauss}[1]{\left[\mkern1mu {#1}\mkern1mu\right]} \newcommand{kaku}[1]{\angle\mbox{#1}} \newcommand{kumiawase}[2]{\mathord{{}_{#1}\kern-.12em{}\text{C}_{#2}}} \newcommand{mdot}[0]{\!\cdot\!} \newcommand{sankaku}[1]{\triangle \mbox{#1}} \newcommand{suuretu}[1]{\left\{#1\right\}} \newcommand{tsqrt}[1]{\textstyle\sqrt{\,#1\,}} \newcommand{zyunretu}[2]{\mathord{{}_{#1}\kern-.12em{}\text{P}_{#2}}} $$

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

この記事でやること

次の問題を考えます。なお,この記事における「さいころ」とは,$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. $1$個の目が出ていて,そのあとに初めて$2$個めの目が出る回数の期待値を求める
  3. $2$個の目が出ていて,そのあとに初めて$3$個めの目が出る回数の期待値を求める
  4. $3$個の目が出ていて,そのあとに初めて$4$個めの目が出る回数の期待値を求める
  5. $4$個の目が出ていて,そのあとに初めて$5$個めの目が出る回数の期待値を求める
  6. $5$個の目が出ていて,そのあとに初めて$6$個めの目が出る回数の期待値を求める
  7. 和の期待値は期待値の和であることを用いて,求めたい期待値を出す。

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

和の期待値は期待値の和

$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. $1$個の目が出ていて,そのあとに初めて$2$個めの目が出る期待値は$\bunsuu65$
  3. $2$個の目が出ていて,そのあとに初めて$3$個めの目が出る期待値は$\bunsuu32$
  4. $3$個の目が出ていて,そのあとに初めて$4$個めの目が出る期待値は$2$
  5. $4$個の目が出ていて,そのあとに初めて$5$個めの目が出る期待値は$3$
  6. $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$という数字と一致していますね。

まとめ

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

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

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

追記

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

投稿日:20201119
OptHub AI Competition

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

投稿者

ぱるち
ぱるち
133
23492
数学屋さんをしています。代数,数論系に興味があり,今は楕円曲線と戯れています。Mathlogは現実逃避用という噂もあります。@f_d00123

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中