コイントスで表が連続して出る確率 (漸化式その2

[] [] []


「世界でもっとも奇妙な数学パズル」(ジュリアン・ハヴィル)で紹介されている参考文献 "The Longest Run of Heads"(Schilling) には、別の漸化式が載っている。

前項ではHのランの最大長Rnk以上である確率を考えたが、代わりにHのランの最大長Rnk以下である確率を考える。

k<nのとき、先頭のパターンで場合分けすると

 Tのとき、残りn-1回のラン長がk以下であればよいのでPr(Rn-1k) *(1/2)

 HTのとき、残りn-2回のラン長がk以下であればよいのでPr(Rn-2k) *(1/2)2

 HHTのとき、残りn-3回のラン長がk以下であればよいのでPr(Rn-3k) *(1/2)3

以下同様で、これらを足して次の漸化式が得られる。

またk=nのときは明らかに

この確率を使ってHのランの最大長Rnkある確率が計算できる。

プログラ(VisualBasic)で計算すると、結果は前項と同じになる。

For k = 0 To nMax

    For n = 0 To k

        B(n, k) = 1

    Next n

    For n = k + 1 To nMax

        Sum = 0

        For j = 0 To k

            Sum = Sum + B(n-1-j, k) / 2^(j+1)

        Next j

        B(n, k) = Sum

    Next n

Next k

 

For n = 0 To nMax

    P(n, 0) = B(n, 0)

    For k = 1 To nMax

        P(n, k) = B(n, k) - B(n, k - 1)

    Next k

Next n

本項の漸化式から前項の漸化式が導けるはずであるが、試しに恒等式

に2つに漸化式を代入してみたら成立していたので、その計算過程を逆にたどると次のようになる。まず本項の漸化式

において、nk1つ下げて両辺を2割ると

Pr(Rn-1k-1)/2を両辺に足すと

右辺のインデックスをふりなおして

右辺のkを分けると

右辺の第1項に対して漸化式を使うと

ここRnk-1以下である確率とk以上である確率の和は1であることを使うと

整理して

と前項の漸化式が得られた。


[] [] []