初ビット列がでるまでの期待時間

kinabaさんのブログの 「無限ビット列を作ったときに最初に "001" が並ぶインデックスの期待値は 8。では、"000" なら？」という問題に対して、マルチンゲールを使った解説をしてみます。

いま無限に生成されるビット列に対して次に何がでるかを賭けるギャンブルを考えます。配当はフェアな賭けで賭け金の2倍返しとします。ここで000が出現したら賭けは終了するとします。
このとき毎時刻ギャンブラーが1$持ってきてつぎのように賭けます。

1. はじめに0が出ることに賭けて、勝ったら次へ、そうでなければ終了
2. 再び0が出ることに前の儲け2$を全額賭ける、勝ったら次へ、そうでなければ終了
3. 再び0が出ることに前の儲け4$を全額賭ける、勝ったら000が出てるので賭け自体が終了、そうでなければ終了

この話はたとえば010がでる期待値を考えるときは2.のところで0にではなく1に賭けることになります。

たとえばビット列が1011000と出た場合

時刻	0	1	2	3	4	5	6
出現ビット	1	0	1	1	0	0	0
個々の時刻に入ったギャンブラーの支払い	1	1	1	1	1	1	1
個々の時刻に入ったギャンブラーの儲け	0	0	0	0	8	4	2

この場合すべてのギャンブラーが支払った額は7であり、儲けの総額は14になります。

ここで儲けの総額というのは000で停止という条件の元では終了時には常に14になります。一方で支払いは毎時刻1ずつ支払うので000が出現するまでの時刻Tだった場合支払いもTになります。

ここですべてのギャンブラーの収支を考えると-T + 14となります。このため収支の合計の期待値は

14 - E[T]

となります。ここで求めたかった値であるE[T]がでてきました。ではこの値がいくつかですが、基本的にn$払えば半分の確率で2n$当たるという賭けなのでマイナスになることはなさそうです。一方でプラスにもなることはなさそうです(なるのならこんなブログとか書いてないでラスベガスにいってルーレットでぼろ儲けしてます)。確率論ではこの期待値が0になりますというのを保証しており、それがOptional stopping theorem(任意抽出定理)です。簡単にいうと公平な賭けの期待値はいつやめても0になるということを意味してます。
これにより

14 - E[T] = 0 => E[T] = 14

となります。

この辺のことを詳しく知りたい方は以下の本が参考になるかと思います

マルチンゲールによる確率論

確率と計算 ―乱択アルゴリズムと確率的解析―