複雑な確率の計算(1000回の勝負をしてどこかで15回以上連続して勝つ確率は？)

次の問題にかなり悩まされています。

「勝つ確率が1/2, 負ける確率が1/2 であるような勝負を1000回
やって、1000回のうち、どこかで15回以上連続して勝つ確率は
いくらか？」

これはYAHOO知恵袋で見つけた問題です。
http://detail.chiebukuro.yahoo.co.jp/qa/question …
回答者のひとりは、
「15回の勝ちをひとまとめにすると、それは985+1回目のどこかで
実現するはず。残り985回は勝ちでも負けでもよい。よって組み合
わせは986*2^985通りで、総数2^1000のうちそれが実現する確率は、
(1/2)^1000*986*2^985=986/2^15」
という回答をしていますが、この回答では15連勝する場合の数を
重複して数え上げていると思います。
もう少し単純な問題を考えてみます。
(問題)
「勝つ確率が1/2, 負ける確率が1/2 であるような勝負を5回やって、
どこかで2回以上連続して勝つ確率はいくらか？」
この問題を先の回答者の方法で解いてみると、
「2回の勝ちをひとまとめにすると、それは3+1回目のどこかで
実現するはず。残り3回は勝ちでも負けでもよい。よって組み合
わせは4*2^3通りで、総数2^5のうちそれが実現する確率は、
(1/2)^5*4*2^3=1」
となりますが、これは明らかにおかしいです。
(この解法では、確率が1になってしまいます。)
5回の勝負のうち、どこかで2回以上連続して勝つ場合をすべて
書いてみると次のように19通りしかないことがわかります。
(勝ちを○で、負けを×で表しています)
したがってこの問題の解は (1/2)^5*19=19/32 です。

1 ○○○○○
2 ○○○○×
3 ○○○×○
4 ○○×○○
5 ○×○○○
6 ×○○○○
7 ○○○××
8 ○○×○×
9 ○○××○
10○×○○×
11○××○○
12×○○○×
13×○○×○
14×○×○○
15××○○○
16○○×××
17×○○××
18××○○×
19×××○○

最初の問題
「勝つ確率が1/2, 負ける確率が1/2 であるような勝負を1000回やって、
1000回のうち、どこかで15回以上連続して勝つ確率はいくらか？」
に対して、パソコンによるシミュレーションをやってみた結果
0.0149 という値を得ました。
しかし私はシミュレーションによる値ではなく、正確な確率の値を
知りたいと思っています。もちろん2^1000通りの勝負のつきかたを
すべて調べ上げることができれば答えは得られますが、この方法は
私には無理です。
正確な確率の値を得るためには、どのように考えて行けばよいのでしょうか？
よろしくお願いします。

No.12 回答者： jaspachate 回答日時： 2009/01/08 07:46

明けましておめでとうございます。

本年も頭を鍛えましょう。
さて、No.11で回答した漸化式ですが調べてみると、r個の初期値、
A(k) = (k-r)2^(k-r-3) (r+2≦k≦2r+2)
を持った周期性のある数列の構造をしており、この一般項を表すには複雑な多重和とするか、変形して斉次漸化式の形にし r+1次の多項式の解を求めてそのべき乗の和を取るしかないようです。多重和の方は結局漸化式を式なりに計算していくのと同じことになり、多項式の解は楕円関数などを用いた初等的でない求め方がありますが、結局は数値積分するか、どこかで作られた関数表や近似級数を使わざるを得ず、計算量と手間を考えると決して簡単とはいえません。
つまり、No.11の漸化式をそのまま計算していくのが最も簡単で速い方法です。よってNo.11をもって最終回答とさせていただきます。

式を変形していくと、slg-120nw さんの回答にあるような漸化式と同等なものに到達します。計算機で計算するうえではそちらの方がシンプルですね。その漸化式の考え方はやはり２分木で考察するとわかりやすいでしょう。

No.11 回答者： jaspachate 回答日時： 2008/12/29 16:57

負になること、確認しました。

連勝開始点の重複を数えるとき誤って数えすぎになっていました。いや大変申し訳ない（ただ、いい訳ですが、その部分はn=1000、r=15では他に比べて効かない（非常に小さい）ので、正確ではないですが良い近似にはなっています)。

さて、考え直して差し引く部分を求めましたが、今ちょっと時間がないのでまだ最終式は出していません（計算機に入れれば計算は簡単ですが）。

(2) 5.でいう3.から除かれるべき開始点の数
k=r+2 : A(r+2) = 2^0
k=r+3 : A(r+3) = 2^1 + 2^0・2^0
k = k : A( k ) = 2^(k-r-2) + 2^0・2^(k-r-3) + ．．．+ 2^(r-1)・2^(k-2r-2) + (2^r-A(r+2))2^(k-2r-3) + (2^(r+1)-A(r+3))2^(k-2r-4) + ．．．+ (2^(k-r-3)-A(k-r-1))2^0

ただし、r+2≦k≦n-r+1 とし、A(k)の各項の和は2のべきのカッコ内が0になったところで打ち切るものとします。またこれは r=1 でも成り立ちます。

N(n,r) = N1 + N2 + N3 (1≦r≦n)

N1 = 2^(n-r) [r≦n]
N2 = 0 [n=r]
または Σ[k=2、n-r+1]2^(k-2)2^(n-k-r+1) = (n-r)2^(n-r-1) [r+1≦n<2r]
または Σ[k=2、r+1]2^(k-2)2^(n-k-r+1) = r2^(n-r-1) [2r≦n]
N3 = 0 [n<2r+1]
または Σ[k=r+2、n-r+1](2^(k-2)-A(k))2^(n-k-r+1) [2r+1≦n]

タイプミスがなければこれでOKだと思います。たびたび申し訳ない。

No.10 回答者： jaspachate 回答日時： 2008/12/28 15:41

No.9の訂正

誤：
「この訂正なしでN(6,2)=43になったのは、2^(6-2・2-1)=1のためです。」
正：
「．．．、2^(6-2・2-2)=1のためです。」

この回答への補足

jaspachateさん、回答ありがとうございます。
今回jaspachateさんが訂正なさったN4の式を用いて、いくつかの
N(n,r)の値を求めてみたのですが、やはりおかしな値がでてきます。
以下にいくつか例を挙げます。
間違っているところがあれば指摘してください。

今回のjaspachateさんの訂正回答によれば、2r+2≦n のとき、
N(n,r)は次のように書けると思います。

N(n,r)=2^(n-r)+r*2^(n-r-1)+(n-2r)(2^r-1)*2^(n-2r-1)
+((r+2)(r+3)/2-(n-r+1)(n-r+2)/2+(r+2)(n-2r-1))*2^(n-2r-2)

このN(n,r)の式を用いて、N(10,2),N(20,3),N(22,2),N(40,3)の値を
それぞれ求めてみると次のようになりました。

N(10,2)=848,
N(20,3)=757760,
N(22,2)=-851968,
N(40,3)=-21474836480.

N(20,3)の値に関してはjaspachateさんのものと一致しましたが、
N(10,2)に関しては違っています。
また、N(22,2)とN(40,3)の値に関してはどちらも負の整数になって
しまいました。
(私はこれらの値の計算を2種類の数式処理ソフト DERIVE, Risa/Asir
の両方で計算し、両者の値が一致していることを確認しました。)

補足日時：2008/12/28 17:05

No.9 回答者： jaspachate 回答日時： 2008/12/28 14:30

まず、前回回答にちょっとした書き落としがありました。

次に、r=1 は特別な場合になります。連勝を問題にしたので、r=1は特別に考慮しませんでしたし、また、r=1は別の考察で簡単に求まるからです。

書き落としについて、前回回答の、

N4 = - Σ[k=r+3、n-r+1](k-r-2)2^(k-r-3)2^(n-k-r+1)
= 0 [n<2r+2]
または { (r+2)(r+3)/2 -(n-r+1)(n-r+2)/2 +(r+2)(n-2r-1) } [2r+2≦n]

で、最初の２行は正しいですが、最後の行で 2^(n-2r-2) の掛け算を書き落としています。つまり、
{ (r+2)(r+3)/2 -(n-r+1)(n-r+2)/2 +(r+2)(n-2r-1) }・2^(n-2r-2) [2r+2≦n]
が正しい。

この訂正なしでN(6,2)=43になったのは、2^(6-2・2-1)=1のためです。
N(10,2)=864、N(20,3)=757760 になります。計算機の方、点検してみてください。

r=1 の場合ですが、No.7の回答中で、数えた連勝開始点の数の中で重複するものを勘定していますが、r=1の場合は別途考える必要があります。結果は次のようです。

(2) 5.でいう3.から除かれるべき開始点の数 (r=1)
k=3 ; 2^0
k=4 ; 2^1 + 2^0
k=5 ; 2^2 + 2^1 + 2^0
k=6 ; 2^3 + 2^2 + 2^1 + 2^0
k = k ; 2^(k-2)-1 [3≦k≦n]

これを用いて、
N(n,1) = N1 + N2 + N3 + N4
N1 = 2^(n-1) (1≦n)
N2 = 2^(n-2) (2≦n)
N3+N4 = 2^(n-2) - 1 (3≦n)
なので、まとめて、
N(n,1) = 2^n - 1 (1≦n)
と書けます。
これは必ず１勝以上あげる場合の数ですから、全数2^nから全部負ける一つしかない場合を引いたものに等しい、として簡単に求まり、たしかにそのとおりになっています。
N(10,1)= 2^10-1 = 1023

No.8 回答者： jaspachate 回答日時： 2008/12/26 19:58

考え方そのものに誤りはありませんが、n=1000,r=15 への回答を念頭においたので、必要な和の取り方の範囲について示しませんでした。

またちょっとしたミスプリントがありました。

考え方は示したので出題者様への宿題にしても良いのですが、一応完全な形での解を記しておきます。

N(n、r) = N1+ N2 + N3 + N4
N1 = 2^(n-r) [r≦n]
N2 = 0 [n=r]
または Σ[k=2、n-r+1]2^(k-2)2^(n-k-r+1) = (n-r)2^(n-r-1) [r+1≦n<2r]
または Σ[k=2、r+1]2^(k-2)2^(n-k-r+1) = r2^(n-r-1) [2r≦n]
N3 = Σ[k=r+2、n-r+1](2^(k-2)-2^(k-r-2))2^(n-k-r+1)
= 0 [ｎ<2r+1]
または (n-2r)(2^r-1)2^(n-2r-1) [2r+1≦n]
N4 = - Σ[k=r+3、n-r+1](k-r-2)2^(k-r-3)2^(n-k-r+1)
= 0 [n<2r+2]
または { (r+2)(r+3)/2 -(n-r+1)(n-r+2)/2 +(r+2)(n-2r-1) } [2r+2≦n]

N(5,3)=8、N(6,2)=43 はOK。
考え方そのものを理解しないと計算機を駆使しても真に正しいかどうかの判断はできません。疑問点があればどうぞ。

この回答への補足

回答ありがとうございます。
jaspachateさんの示された式にもとづいて、いくつかのN(n,r)の値
を計算してみました。やはりおかしな値がでてきて困っています。
以下、いくつかのN(n,r)の値を計算してみます。
間違いがあれば指摘してください。
2r+2≦n のときを考えます。
jaspachateさんの回答によれば、2r+2≦n のとき、
N1=2^(n-r),
N2=r*2^(n-r-1),
N3=(n-2r)(2^r-1)*2^(n-2r-1),
N4=(r+2)(r+3)/2-(n-r+1)(n-r+2)/2+(r+2)(n-2r-1)
となります。よって、
N(n,r)
=N1+N2+N3+N4
=2^(n-r)+r*2^(n-r-1)+(n-2r)(2^r-1)*2^(n-2r-1)+(r+2)(r+3)/2-(n-r+1)(n-r+2)/2+(r+2)(n-2r-1).
この式を用いてN(6,2)を計算すると、確かにN(6,2)=43となります。
しかしN(10,2)の値を計算すると、N(10,2)=1073となります。
本来、N(10,2)の値は2^10=1024よりも小さいはずですから、N(10,2)=1073という結果は
おかしいです。( N(10,2)の正しい値は880だと思います。この値は計算機で
しらみつぶしに数えた結果です。100％合っている自信があるわけではありません。)
また、この式を用いてN(10,1)の値を計算するとN(10,1)=1764となりますが、
これもおかしな値です。
さらに、この式を用いてN(20,3)を計算すると、N(20,3)=1130405となりますが、
これもやはりおかしな値です。
(1130405は2^20=1048576よりも大きな値になってしまっています。)

補足日時：2008/12/27 11:36

No.7 回答者： jaspachate 回答日時： 2008/12/26 03:12

訂正です。

前のNo.6の回答中、「初めの一段目を仮想的に×と考えると」との文章は、「初めの一段目の上のゼロ段目を仮想的に×と考えると」の誤りです。失礼しました。一段目は○および×の二つの頂点から始まりますが、仮想的にその親の頂点を考える、と言う意味です。こうしても計算結果に変わりはなく、考えるのが楽になります。

ついでに、no.6の回答の考え方をもう少し詳しく補足しておきます。

問題：「1回の試行でそれぞれ1/2の確率で○と×が出るとき、n回の試行結果を1～n回の順番で一列に並べる。並び方の重複しない列の中で、○がr個以上連続して連なる(r連勝する)場合を含む列の数N(n,r)を求めよ。」

0.No.6で述べたように、2分木を作り、頂点を0段目、下の2分岐の先に1段目の○と×、さらにそれぞれの下の2分岐に○と×をおき、n段目まで配置する。
1.2分木を一段目から最終段までたどるすべての経路の数は、最終段の○×の数に等しく、2^nである。一つの経路上にある分岐点（頂点）上の○×を上から順番に並べれば、それがすなわちn回の試行で○×の列ができる一つの場合を表し、全ての経路を数えれば全ての重複しない場合の数を数え尽くしている。
2.第k段目にある任意の分岐点を山の頂点とした、その下のk+r段目における○×の数(=経路の数)は2^rで、全ての経路の数は2^(n-k)。

3.全ての r連勝以上(○がr個以上連続する)の開始点は、1段目からn-r+1段目までの各段にある○のうち、その親(上段の分岐上にある)が×のものである。一段目の○に対しては仮想的な0段目に×があるとする。
4.r連勝したr番目の○を頂点としたその下の全ての経路の数(=場合の数)を数える。これはr連勝してしまえばその後の試行結果は任意でよいことを表す。これをr連勝の子の山に含まれる場合の数とする。
5.3.に属する連勝開始点の中で、4.の経路に含まれるものは除く。これは開始点の数を数えるとき、重複を除くため。
6.1～n-r+1段目にある3.＆5.で数えた開始点それぞれについて4.の場合の数を求めて、足し合わせる。

以上に従って計算します。
(1) 3,を満たす開始点の数
1段目 1、
k段目 2^(k-2) (2≦k≦n-r+1)
(2) 5.でいう3.から除かれるべき開始点の数
k=r+2 ; 2^0
k=r+3 ; 2^1 + 2^0
k=r+4 ; 2^2 + 2^1 + 2^1・2^0
k=r+5 ; 2^3 + 2^2 + 2^1・2^1 + 2^2・2^0
k = k ; 2^(k-r-2)[r+2≦k≦n-r+1] + (k-r-2)2^(k-r-3)[r+3≦k≦n-r+1]
k=r+2で最初のr連勝の子の山に含まれるものが現れます。それ以降その山に含まれるものは2倍ずつ増えていきます。k=r+3で2番目のr連勝の子の山に含まれるものが現れます。これも以降同様に2倍ずつ増えていきます。
k=r+4でさらに2^1個の連勝の子の山に一個ずつ現れます(2^1・2^0)。これも以降2倍ずつ増えていきます。k=r+5ではさらに2^2個の連勝の子の山が現れ、、、というようにｒ連勝の子の山の数とそれに含まれるものが増大して行きます。
(3) 4.でいうr連勝の子の山に含まれる場合の数は、連勝の開始点がk段目にあるとすると、2^(n-k-r+1)。
(4) 6.に従ってN(n,r)を求める。No.6の回答では、k=1、2～r+1、r+2～n-r+1、r+3～n-r+1 に分割して計算しています。開始点の数の増大と連勝の子の場合の数の減少が相殺するので、計算は楽です。

以上から求めるN(n,r)がNo.6の回答のようになります。

この回答への補足

No.6の回答でjaspachateさんがお書きになっているN(n,r)の式を使って
N(5,2)の値を計算すると、確かにN(5,2)=19となり、これは事実と一致
しています。しかしこのN(n,r)の式を使ってN(5,3)の値を求めると、
N(5,3)=17/2 となってしまします。N(n,r)は整数であるはずなのに、
非整数となるのはおかしいです。
また、このN(n,r)の式を使ってN(6,2)の値を求めるとN(6,2)=40となります。
しかし実際には、6回の勝負をしてどこかで2回以上連続して勝つような勝負
のつきかたは43通りあります。
jaspachateさんの計算、もしくは考え方そのものに誤りがあるのではないか
と思います。

補足日時：2008/12/26 10:57

No.6 回答者： jaspachate 回答日時： 2008/12/25 15:59

場合の数を正確に数えました。

2分木を使います。1段目の右側に○と左側に×をおき、これらを頂点(分岐点)にしてそれぞれの下に２つづつの分岐を作り、それらにまた○と×を割り当てます。○の下に右に○と左に×、×の下にも右に○と左に×です。こうしてn段目まで下ります。n段目の○×の数は2^n個で、下から上へたどるたどり方は一通りに決まります。
今、上からたどると、○が続くのは分岐を右へ右へとたどった場合です。初めの一段目を仮想的に×と考えると、連勝(○)の始点は必ずその親(分岐の上方)が×のときです。また、r連勝したらその下にぶら下がる全ての分岐上で連勝が続こうと続くまいと、あるいは何度r連勝が現れようと、勝ちに数えます。r連勝の下にぶら下がる分岐は、r連勝目をひとつの山の頂点とする全ての分岐です。例えば k段目にある一つの○にぶら下がる場合の数は2^(n-k)になります。
こうやって1段目からn-r+1段目までの各段毎に連勝の始点の数を数え、r連勝後の全ての場合の数を勘定すればそれで数えつくしています。
結果は、

N(n、r) = 2^(n-r) + { Σ[k=2、r+1]2^(k-2)2^(n-k-r+1)
+ Σ[k=r+2、n-r+1](2^(k-2)-2^(k-r-2))2^(n-k-r+1)
- Σ[k=r+3、n-r+1](k-r-2)2^(k-r-3)2^(n-k-r+1) }

= 2^(n-r) + r 2^(n-r-1)
+ (n-2r)( 2^(n-r-1) - 2^(n-2r-1) )
+ { (r+1)(n-2r-1) - (n-r+1)(n-r+2)/2 + (r+2)(r+3)/2 }2^(n-2r-1)


確率は　N(n,r)/2^n で計算でき、上の式には全て2^nの因子があります。
n=1000、r=15の場合を計算すると、

N(1000、15)/2^1000 = 0.0149505....

また、N(5,2)=19 に確かになります。

お望みであればもう少し詳しくご説明できます。
いかがでしょうか。

No.5 回答者： arrysthmia 回答日時： 2008/12/21 21:31

別解：

n 試合中に 15 以上連勝が起こる確率を q[n] と置く。

n 試合中に 15 以上連勝するというのは、
(1) 第 2 試合から第 n 試合までの n-1 試合中に 15 以上連勝する
(2) 第 1 試合から丁度 15 連勝して、その後は 15 以上連勝は無い
のどちらかで、(1) と (2) に共通部分は無いから、

q[n] = q[n-1] + { (1/2)^16 }{ 1 - q[n-16] }.　…(*)
右辺第二項の (1/2)^16 は、
第 1 試合から第 15 試合まで勝って、第 16 試合は負ける確率。

初期条件は、
q[0] = q[1] = q[2] = … = q[14] = 0,
q[15] = (1/2)^15.

ここから、計算機に任せて q[1000] を求めてもよいし、

(*) の n をひとつ移動して、
q[n-1] = q[n-2] + { (1/2)^16 }{ 1 - q[n-17] }.　…(**)
(*) と (**) の辺々を引き算して、
q[n] - 2 q[n-1] + q[n-2] + c q[n-16] - c q[n-17] = 0.　…(***)
ただし、c = (1/2)^16.

(***) は、斉次線形漸化式と呼ばれる漸化式のひとつで、
一般項の求め方がよく知られている。
(ただし、17 次方程式を解くことができれば。)

No.4 回答者： slg-120nw 回答日時： 2008/12/21 20:55

すみません、回答番号：No.3は間違っていました。

正しくは、

p[n] = p[n-1]+p[n-2]+p[n-3]+p[n-4]+p[n-5]+p[n-6]+p[n-7]+p[n-8]+p[n-9]+p[n-10]+p[n-11]+p[n-12]+p[n-13]+p[n-14]+p[n-15]+2^(n-15)

p[1000] =
16020196378230824166193155663758732740364619440202
49449077467555470471863328247865552188425123025826
74375517377093460010002972267208705224759070815719
74770033172311630967020723241462486269127925335563
76846624348330496098831804865310584177438886507065
64100247482792629255768365891592429559196724451328

p[1000] / 2^1000 = 0.01495106644108

でした。シミュレーションの結果とよくあっていますね。

No.3 回答者： slg-120nw 回答日時： 2008/12/21 20:20

n回勝負したときの勝敗表の場合の数は2^n種類だけあります。

この2^n種類のうち15回以上連続して勝つ場合の数をp[n]と書くことにします。
すると、p[1]=p[2]=・・・=p[14]=0, p[15]=1。

p[n]についての漸化式を求めることを考えます。まず、勝敗表が、
×・・・
のようになって、かつ15回以上連続して勝つ場合の数は、p[n-1]通り。さらに、
○×・・・
となる場合は、p[n-2]通り。以下同様にして○を14個まで増やしていき、
○○○○○○○○○○○○○○×・・・
となる場合は、p[n-14]通り。最後に、
○○○○○○○○○○○○○○○・・・
となる場合は、残りの部分は何でも良いので2^(n-15)通り。

p[n]は以上を足し合わせたものになるので、
p[n] = p[n-1]+p[n-2]+p[n-3]+p[n-4]+p[n-5]+p[n-6]+p[n-7]+p[n-8]+p[n-9]+p[n-10]+p[n-11]+p[n-12]+p[n-13]+p[n-14]+2^(n-15)。

あとは、初期条件p[1]=p[2]=・・・=p[14]=0, p[15]=1を使えば任意のnについてp[n]は計算できます。
これを、フリーの数式処理ソフトmaximaを使って計算してみました。

p[1000] =
15903644099145190049949449951001602867421494546556
62707647950485107435313575659095863665765936391990
43134613195545497315183965615918707840809915544642
34606197600381946550183498241267050517605460308850
57825503943999406432228963942198503523310873943785
73447930319640063873196660686660471644027618391552

よって、求める確率は、

p[1000] / 2^1000 = 0.014842292439356

となりました。