サイコロの目が6つとも出るまでにかかる回数の確率分布

買って通勤時に4日で読んだけど、とにかく重い。持ち運ぶときはそんなに感じなかったけど、持って読んでいるとすぐに腕が疲れてくる。だんだん分厚くなってきているよね。

アルゴリズム解析というと、前に古い本を読んだことがある。細かいところにこだわっているところが古さを感じさせるなあと思ったけど、少し触発されてここを何回通るかって数えたっけ。

この本の中でサイコロの目が6つとも出るまでにかかる回数の期待値を求める問題が出ていた。じゃあちょっと考えてみようかと思って本を閉じた瞬間に思いついた。こういう解き方だよね、ふつうは。でも高校生のときでは思いつかなかったよなあ。

主人公はこうではなく正攻法で期待値を求めようとする。すなわち、確率を求めてそこから期待値を求める。しかし、ちょっとしか考えが進まずに砕け散っている。えー、そこはもうちょっとがんばれないか？

「お兄ちゃんは粘りがないにゃー」

仕方がないので代わりに考えてあげよう。

p_nをn回目に初めてサイコロの目が6つとも出る確率とします。これを求めればいいわけです。しかし、これを直接求めるのは難しそうですよね。こういうときは次のように考えるのが定石です。すなわち、q_nをn回目にサイコロの目が6つとも出ている確率とすれば、

p_n = q_n - q_n-1 (n > 1)

となります。q_nはn回目の状態だけ考えればいいのでわかりやすいです。
n回目にm種類の目が出ている場合の数をS(m, n)としてこれを求めましょう。まず、S(1, n)は、1から6の同じ目が常に出ているということだから、

S(1, n) = 6 (n >= 1)

です。S(2, n)は、6つの目の中から2つを選んで、その2つの目が出続けるので、₆C₂2ⁿ。どちらか一方の目が出続けるのは排除しなければならないので、

S(2, n) = ₆C₂(2ⁿ - 2) (n >= 1)

です。S(3, n)は、6つの目の中から3つを選んで、その3つの目が出続けるので、₆C₃3ⁿ。3つのどれか2つが出続けるのは排除しなければならないので、₃C₂2³を引かなければならないです。しかし、これだと1つの目が出る場合を重複して排除しているので、その分を考慮して、

S(3, n) = ₆C₃(3ⁿ - ₃C₂2ⁿ + ₃C₁)

これは包除原理ですね。kの目が出ている場合をS_kとすると、

｜S₁∩S₂∩S₃｜ = ｜S₁∪S₂∪S₃｜ - ｜S₁∪S₂｜ - ｜S₁∪S₃｜ - ｜S₂∪S₃｜ + ｜S₁｜ + ｜S₂｜ + ｜S₃｜

m = 6なら、

$S(6, n) = \sum_{k = 1}^6{_6C_kk^n}(-1)^k$

q_nは、

$q_n = \sum_{k = 1}^6{_6C_k(\frac{k}{6})^n(-1)^k}$

p_nは、

$p_n = \sum_{k = 1}^6{_5C_k(\frac{k}{6})^{n-1}(-1)^{k-1}}$

ですね。n > 1で成り立つことに注意して計算すると期待値が計算できます。

11回目に6つともの目が出るのが最も確率が高いんですね。