コイントスで表が連続して出る確率(漸化式その1)
・100回コイントスして表が最大5回連続して出る確率は26% ・100回コイントスすると、表が最大6回ぐらい連続して出る (逆に6回連続して表を出すには100回コイントスすればよい) ・100回コイントスすると、表または裏が最大7回ぐらい連続して出る (表だけの連続回数より1回多くなる) |
次の図は150x150の画素を赤と青で半々に塗りつぶしたもので、左は交互に(均一に)、右は乱数で塗った例である。
これを見ると、ランダムに塗っているのに意外と均一でなく斑模様になる。乱数で塗るとは、例えばコイン投げをして表なら赤、裏なら青を塗っていくのと同じなので、斑の大きさは連続して表や裏がでる長さである。もちろん長いものほど出現確率は小さいのだが、同じ面が連続して出る確率は意外と高いようである。
◇
では、コイントスで表か裏が連続する長さはどれくらいだろうか?
この計算が「世界でもっとも奇妙な数学パズル」(ジュリアン・ハヴィル)という本にのっていた。以下では
・表(Head)をH, 裏(Tail)をT
・n回コイントスして出るH,Tの列を、長さnの系列(sequence)
・連続k回Hが出ることを、長さkのHのラン(run)
と呼ぶことにする。
求めたいのは長さnの系列の中でHのランの最大長Rnがkである確率Pr(Rn=k)である。この問題のポイントは、いきなり最大長がkである確率を考えるのでなく、k以上である確率Pr(Rn≧k)を考えることである。
まず、n回目までに長さk以上のHのランが現れる場合は2つに分けられる
(i) n-1回目までに長さk以上のHのランが現れる場合の確率は
(ii) n回目でちょうど長さkのHのランになる場合は、n-k-1回目までには現れず、n-k回目にTがでてその後k回連続してHが出る確率だから
これらを足して次の漸化式が得られる。
(注:私が持っている本の第1版では漸化式が間違っていて、Rn-k-1のところがRn-kになっている)
またk=nのときは明らかに
n<kのときは
と見なす。
この確率を使ってHのランの最大長Rnがkに等しい確率が計算できる。
プログラム(VisualBasic)で計算すると
For n = 0 To nMax For k = n+1 To nMax A(n,k) = 0 Next k A(n,n) = (1/2) ^ n A(n,0) = 1 Next n For n = 1 To nMax For k = 1 To n-1 A(n,k) = A(n-1,k) + (1 - A(n-k-1,k)) / 2^(k+1) Next k Next n
For n = 0 To nMax P(n,nMax) = A(n,nMax) For k = 0 To nMax-1 P(n,k) = A(n,k) - A(n,k+1) Next k Next n |
P(n,k) |
k=0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
ERn |
n=3 |
13% |
50% |
25% |
13% |
|
|
|
|
|
|
|
1.4 |
n=5 |
3% |
38% |
34% |
16% |
6% |
3% |
|
|
|
|
|
1.9 |
n=10 |
0% |
14% |
35% |
26% |
14% |
6% |
3% |
1% |
0% |
0% |
0% |
2.8 |
n=25 |
0% |
1% |
13% |
29% |
25% |
15% |
8% |
4% |
2% |
1% |
0% |
4.0 |
n=50 |
0% |
0% |
2% |
16% |
28% |
24% |
15% |
8% |
4% |
2% |
1% |
5.0 |
n=100 |
0% |
0% |
0% |
3% |
16% |
26% |
23% |
15% |
8% |
4% |
2% |
6.0 |
n=200 |
0% |
0% |
0% |
0% |
3% |
16% |
26% |
22% |
15% |
8% |
4% |
7.0 |
この結果によると100回のコイントスでHのランの最大値は5回がもっとも起こりやすく確率は26%である。100回中、Hが5回も連続して出るのは不自然に感じるが、実はよくあることなのである。ちなみにRnの期待値は分布のピークより少し大きく6.0回である。
◇◇
さて、Hのランだけでなく、HかTどちらかのランを数えるには、つぎのように考えればよい。
長さnのH,Tの系列は、長さn-1の「前と同じ(Same)」か「前と違う(Different)」の系列と見なせる。
T H T T T H T T H H
D D S S D D S D S
したがってHかTどちらかの長さkのランが起きる場合の数は、1回目はH,Tどちらかで、その後n-1回のS,Dの系列において長さk-1のSのランが起きる場合の数と考えられる。すなわち、n回のコイントスでHかTどちらかの長さkのランが起きる確率は、n-1回のコイントスで長さk-1のHのランの出る確率と同じである。確率はn回とn-1回ではほとんど変わらないので、HかTどちらかのランの長さは、Hだけのランの長さより大体1回多いということになる。