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

[←]　[↑]　[→]

---

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

前項ではHのランの最大長R_nがk以上である確率を考えたが、代わりにHのランの最大長R_nがk以下である確率Pr(R_n≦k)を考える。まずk<nのとき、先頭のパターンで場合分けすると

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

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

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

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

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

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

プログラム(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

◇

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

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

において、nとkを1つ下げて両辺を2で割ると

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

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

右辺の第k項を分けると

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

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

整理して

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

---

[←]　[↑]　[→]