ヨーキョクデイ

100% pure impurities, which may imply some value. （j は虚数単位）

n 回目に初めてビンゴする確率

数学

ヨビノリの動画で $n$ 回目に初めてビンゴする確率について触れていたので、コンピュータのパワーで計算してみようと思った。
www.youtube.com

復習

ありがちな高校数学の問題。

問 1

赤玉が $R$ 個、緑玉が $G$ 個、青玉が $B$ 個あり、これらはすべて区別できる。

(1)

玉を $k$ 個を選ぶ選び方の総数は？

(2)

赤玉、緑玉、青玉をそれぞれ $r,g,b$ 選ぶ選び方の総数は？

答 1

(1)

$R+G+B$ 個の玉から $k$ 個選ぶ場合の数であるから、$\binom{R+G+B}{k}$。

(2)
  • 赤玉について、$R$ 個から $r$ 個選ぶ場合の数は $\binom{R}{r}$
  • 緑玉について、$G$ 個から $g$ 個選ぶ場合の数は $\binom{G}{g}$
  • 青玉について、$B$ 個から $b$ 個選ぶ場合の数は $\binom{B}{b}$

求める総数はそれらの積で、$\binom{R}{r} \binom{G}{g} \binom{B}{b}$。

特定の盤面を得る確率

問 2

縦横 $5$ マスずつからなるビンゴカードがある。中央のマスは FREE であり穴があらかじめ開けてある。このビンゴカードの FREE 以外のマスには下の図のように数が割り振られている。

1 2 3 4 5
6 7 8 9 10
11 12 FREE 14 15
16 17 18 19 20
21 22 23 24 25

さて、$1$ から $75$ までの数が書かれたボールを重複なくランダムに引いてゆき、引いたボールに書かれた数が割り振られたマスがビンゴカードにあればそのマスを開けることを $10$ 回繰り返す。

(1)

引かれたボールの組合せの総数は？

(2)

結果として新たに $1,2,3$ のマスにのみ穴が開くときに引かれたボールの組合せの総数は？

(3)

結果として新たに $1,2,3$ のマスにのみ穴が開く確率は？

答 2

前述の問 1 と同じ考え方で解ける。

(1)

$75$ 個のボールから引くボールを $10$ 個選ぶ場合の数であるから、$\binom{75}{10}=828931106355$。

(2)

ボールについて $(1,2,3),(4,\dots,12,14,\dots,25),(26,\dots,75,13)$ がそれぞれ書かれたボールの組はそれぞれ、

  • 引くと狙ったマスに穴を開けられるボールの組（甲）
  • 引くと狙ったマス以外のマスに穴を開けられるボールの組（乙）
  • カードにない数の書かれたボールの組（丙）

に対応する。

  • （甲）について、$3$ 個のボールから $3$ 個選ぶ場合の数は $\binom{3}{3}=1$
  • （乙）について、$21$ 個から $0$ 個選ぶ場合の数は $\binom{21}{0}=1$
  • （丙）について、$51$ 個から $10-3-0=7$ 個選ぶ場合の数は $\binom{51}{7}=115775100$

求める総数はそれらの積で、$\binom{3}{3} \binom{21}{0} \binom{51}{7}=\binom{51}{7}=115775100$。

(3)

(1)(2) より、$\binom{51}{7} / \binom{75}{10} = 115775100/828931106355 = 19740/141335227$。

補題

縦横 $M$ マスずつからなるビンゴカードがある。FREE マスが適当な箇所に $f$ 個あり、穴があらかじめ開けてある。$N$ 個のボールを重複なくランダムに引いてゆき、引いたボールに書かれた数に対応するマスがビンゴカードにあればそのマスを開けることを $n$ 回繰り返すとき、新たに特定の $m$ マスにのみ穴が開く確率を $p(M,f;N;n,m)$ とすると、$$p(M,f;N;n,m) = \frac{ \binom{N-(M^2-f)}{n-m} }{ \binom{N}{n} }$$である。

これは問 2 と同様に考えることで導ける。

リーチ盤面から考える

n-1 回目に特定のリーチ状態である確率

上記の補題と同様のビンゴカードとボールを考える。$n-1$ 回ボールを引いたとき、新たに特定の $m$ マスにのみ穴が開く確率は、補題より、$$
p(M,f;N;n-1,m) = \frac{ \binom{N-(M^2-f)}{(n-1)-m} }{ \binom{N}{n-1} }$$である。

さて、このとき、ビンゴが完成したラインが存在せず、かつリーチ状態であるとする。$n-1$ 回目で初めてリーチしたとは限らないことに注意。そして $n$ 回目に引いたボールによってビンゴが完成するようなボールが $k$ 個あるとする。

例として、下に示す $M=5,f=2$ の珍奇なビンゴカードを考える。$n-1$ 回ボールを引いたとき、○で示した $m=9$ マスに穴が開いていた。

F ○
○ ☆
○ ○ ☆ ○ ○
F ○
○ ○

$n$ 回目引いたボールによって☆で示した $k=2$ マスのいずれかに穴が開けば斜めビンゴか縦ビンゴが完成する。

n-1 回目に特定のリーチ状態であるとき n 回目にビンゴが完成する確率

このような $n-1$ 回で特定のリーチ状態であるとき、ビンゴが完成するようなボールを $n$ 回目に引く確率は $k/\qty[ N-(n-1) ]$ であるから、そのようなリーチ状態から $n$ 回目に初めてビンゴが完成する確率は、$$
p(M,f;N;n-1,m) \frac{k}{N-(n-1)} = \frac{ \binom{N-(M^2-f)}{(n-1)-m} }{ \binom{N}{n-1} } \frac{k}{N-(n-1)}$$となる。

確率分布

n 回目にビンゴが完成する確率

前述の議論より。

ボールの数を $N$ とする。縦横 $M$ マス、FREE マスが $f$ 個あるビンゴカードを考える。このカードにおいて $n-1$ 回ボールを引いたときに実現しうる、ビンゴが完成したラインが存在せず、かつリーチ状態である盤面全体の集合を $S$ とする。そのような任意の盤面 $s \in S$ について、FREE マス以外の穴の数を $m_s$ とし、$n$ 回目にボールを引いたときにビンゴが完成するようなボールが $k_s$ 個あるとする。このとき、$n$ 回目にボールを引いたときにビンゴが完成する確率は、$$
\sum_{s \in S} p(M,f;N;n-1,m_s) \frac{k_s}{N-(n-1)} = \sum_{s \in S} \frac{ \binom{N-(M^2-f)}{(n-1)-m_s} }{ \binom{N}{n-1} } \frac{k_s}{N-(n-1)}$$となる。

数値計算

とはいえ、そのようなリーチ状態を組合せ論的に列挙するのは非常にやりたくないので、コンピュータによって列挙することにし、その上で具体的な確率分布を算出した。小数第 12 位まで。FREE マスは存在するならば中央に 1 個だけある想定で。

以下に $n$ 回目で初めてビンゴが完成する確率とその累積である $n$ 回目までにビンゴが完成する確率の一覧表を挙げる。

3×3 マス、FREE あり、ボール 45 個
n n 回目で初ビンゴの確率 n 回目までにビンゴする確率
1 0.000000000000 0.000000000000
2 0.004040404040 0.004040404040
3 0.008362696735 0.012403100775
4 0.012846068660 0.025249169435
5 0.017376258329 0.042625427764
6 0.021847025477 0.064472453242
7 0.026161359911 0.090633813152
8 0.030232439839 0.120866252992
9 0.033984353607 0.154850606599
10 0.037352598740 0.192203205339
11 0.040284372231 0.232487577569
12 0.042738665971 0.275226243540
13 0.044686181260 0.319912424799
14 0.046109076297 0.366021501096
15 0.047000560581 0.413022061677
16 0.047364350132 0.460386411809
17 0.047213997454 0.507600409263
18 0.046572110160 0.554172519423
19 0.045469472164 0.599641991588
20 0.043944081380 0.643586072968
21 0.042040117820 0.685626190788
22 0.039806856029 0.725433046817
23 0.037297535766 0.762730582583
24 0.034568204846 0.797298787429
25 0.031676548069 0.828975335498
26 0.028680716145 0.857656051644
27 0.025638168541 0.883294220184
28 0.022604544156 0.905898764340
29 0.019632573760 0.925531338100
30 0.016771048093 0.942302386193
31 0.014063855560 0.956366241753
32 0.011549103426 0.967915345179
33 0.009258336440 0.977173681619
34 0.007215866797 0.984389548416
35 0.005438229363 0.989827777779
36 0.003933776069 0.993761553848
37 0.002702423409 0.996463977256
38 0.001735566944 0.998199544201
39 0.001016176739 0.999215720940
40 0.000519087643 0.999734808583
41 0.000211498340 0.999946306923
42 0.000053693077 1.000000000000
43 0.000000000000 1.000000000000
44 0.000000000000 1.000000000000
45 0.000000000000 1.000000000000
3×3 マス、FREE なし、ボール 45 個
n n 回目で初ビンゴの確率 n 回目までにビンゴする確率
1 0.000000000000 0.000000000000
2 0.000000000000 0.000000000000
3 0.000563777308 0.000563777308
4 0.001691331924 0.002255109232
5 0.003364657023 0.005619766255
6 0.005548966695 0.011168732950
7 0.008194320333 0.019363053283
8 0.011237564815 0.030600618098
9 0.014604520118 0.045205138216
10 0.018212338522 0.063417476738
11 0.021971972087 0.085389448825
12 0.025790687593 0.111180136418
13 0.029574572632 0.140754709050
14 0.033230981080 0.173985690130
15 0.036670870677 0.210656560807
16 0.039810989956 0.250467550763
17 0.042575876280 0.293043427043
18 0.044899631263 0.337943058306
19 0.046727444345 0.384670502651
20 0.048016839849 0.432687342500
21 0.048738627298 0.481425969798
22 0.048877539348 0.530303509146
23 0.048432546164 0.578736055310
24 0.047416839589 0.626152894899
25 0.045857484995 0.672010379895
26 0.043794743171 0.715805123065
27 0.041281069164 0.757086192230
28 0.038379799481 0.795465991710
29 0.035163543561 0.830629535272
30 0.031712299978 0.862341835250
31 0.028111322302 0.890453157552
32 0.024448764103 0.914901921655
33 0.020813137068 0.935715058723
34 0.017290620724 0.953005679447
35 0.013962266773 0.966967946220
36 0.010901145570 0.977869091790
37 0.008169486762 0.986038578551
38 0.005815870649 0.991854449200
39 0.003872531326 0.995726980526
40 0.002352837180 0.998079817705
41 0.001249018833 0.999328836538
42 0.000530219135 0.999859055673
43 0.000140944327 1.000000000000
44 0.000000000000 1.000000000000
45 0.000000000000 1.000000000000
5×5 マス、FREE あり、ボール 75 個
n n 回目で初ビンゴの確率 n 回目までにビンゴする確率
1 0.000000000000 0.000000000000
2 0.000000000000 0.000000000000
3 0.000000000000 0.000000000000
4 0.000003290962 0.000003290962
5 0.000013627365 0.000016918327
6 0.000035227201 0.000052145528
7 0.000072771981 0.000124917509
8 0.000131404952 0.000256322460
9 0.000216725572 0.000473048033
10 0.000334778066 0.000807826099
11 0.000492031665 0.001299857764
12 0.000695349959 0.001995207722
13 0.000951946596 0.002947154319
14 0.001269324440 0.004216478759
15 0.001655195257 0.005871674016
16 0.002117377057 0.007989051072
17 0.002663666417 0.010652717489
18 0.003301683470 0.013954400960
19 0.004038687833 0.017993088793
20 0.004881364553 0.022874453346
21 0.005835580218 0.028710033564
22 0.006906110718 0.035616144282
23 0.008096343748 0.043712488030
24 0.009407961019 0.053120449050
25 0.010840607219 0.063961056269
26 0.012391555002 0.076352611271
27 0.014055377606 0.090407988876
28 0.015823642977 0.106231631854
29 0.017684645381 0.123916277235
30 0.019623192253 0.143539469488
31 0.021620465339 0.165159934827
32 0.023653975732 0.188813910559
33 0.025697632150 0.214511542708
34 0.027721940422 0.242233483130
35 0.029694349642 0.271927832772
36 0.031579756534 0.303507589307
37 0.033341174341 0.336848763647
38 0.034940565920 0.371789329568
39 0.036339832819 0.408129162387
40 0.037501943118 0.445631105504
41 0.038392171080 0.484023276584
42 0.038979411523 0.523002688107
43 0.039237521875 0.562240209982
44 0.039146635724 0.601386845706
45 0.038694384054 0.640081229761
46 0.037876954948 0.677958184709
47 0.036699920280 0.714658104989
48 0.035178759369 0.749836864358
49 0.033339015516 0.783175879874
50 0.031216032218 0.814391912091
51 0.028854231898 0.843246143989
52 0.026305921190 0.869552065179
53 0.023629632664 0.893181697843
54 0.020888042611 0.914069740454
55 0.018145536595 0.932215277049
56 0.015465527271 0.947680804320
57 0.012907659890 0.960588464210
58 0.010525067351 0.971113531560
59 0.008361855459 0.979475387019
60 0.006451006931 0.985926393950
61 0.004812886624 0.990739280574
62 0.003454507638 0.994193788212
63 0.002369676574 0.996563464786
64 0.001540075598 0.998103540384
65 0.000937260353 0.999040800737
66 0.000525459574 0.999566260312
67 0.000264961019 0.999831221331
68 0.000115768584 0.999946989915
69 0.000041130838 0.999988120752
70 0.000010488700 0.999998609453
71 0.000001390547 1.000000000000
72 0.000000000000 1.000000000000
73 0.000000000000 1.000000000000
74 0.000000000000 1.000000000000
75 0.000000000000 1.000000000000
5×5 マス、FREE なし、ボール 75 個
n n 回目で初ビンゴの確率 n 回目までにビンゴする確率
1 0.000000000000 0.000000000000
2 0.000000000000 0.000000000000
3 0.000000000000 0.000000000000
4 0.000000000000 0.000000000000
5 0.000000695274 0.000000695274
6 0.000003476369 0.000004171642
7 0.000010429106 0.000014600748
8 0.000024334580 0.000038935327
9 0.000048668793 0.000087604120
10 0.000087601166 0.000175205287
11 0.000145990755 0.000321196041
12 0.000229378565 0.000550574606
13 0.000343973902 0.000894548508
14 0.000496632236 0.001391180744
15 0.000694821588 0.002086002332
16 0.000946574049 0.003032576382
17 0.001260418618 0.004292995000
18 0.001645291315 0.005938286315
19 0.002110418328 0.008048704642
20 0.002665168006 0.010713872649
21 0.003318867770 0.014032740418
22 0.004080582546 0.018113322964
23 0.004958852271 0.023072175235
24 0.005961387262 0.029033562497
25 0.007094722017 0.036128284514
26 0.008363830172 0.044492114686
27 0.009771705995 0.054263820681
28 0.011318920863 0.065582741544
29 0.013003166567 0.078585908110
30 0.014818800955 0.093404709066
31 0.016756415165 0.110161124231
32 0.018802445262 0.128963569493
33 0.020938854369 0.149902423862
34 0.023142913848 0.173045337710
35 0.025387113669 0.198432451379
36 0.027639232205 0.226071683585
37 0.029862594205 0.255934277789
38 0.032016542087 0.287950819876
39 0.034057139899 0.322007959775
40 0.035938120995 0.357946080770
41 0.037612079735 0.395558160504
42 0.039031894419 0.434590054924
43 0.040152353517 0.474742408441
44 0.040931940613 0.515674349054
45 0.041334716138 0.557009065192
46 0.041332216861 0.598341282053
47 0.040905278585 0.639246560637
48 0.040045674840 0.679292235477
49 0.038757456308 0.718049691785
50 0.037057873626 0.755107565411
51 0.034977771826 0.790085337237
52 0.032561359060 0.822646696297
53 0.029865276564 0.852511972861
54 0.026956931111 0.879468903972
55 0.023912095354 0.903380999326
56 0.020811833900 0.924192833226
57 0.017738871413 0.941931704639
58 0.014773579829 0.956705284468
59 0.011989820066 0.968695104535
60 0.009450923565 0.978146028100
61 0.007206133559 0.985352161659
62 0.005287837989 0.990639999647
63 0.003709907966 0.994349907613
64 0.002467401328 0.996817308942
65 0.001537795793 0.998355104735
66 0.000883779286 0.999238884020
67 0.000457450181 0.999696334202
68 0.000205577794 0.999901911995
69 0.000075362487 0.999977274482
70 0.000019944423 0.999997218905
71 0.000002781095 1.000000000000
72 0.000000000000 1.000000000000
73 0.000000000000 1.000000000000
74 0.000000000000 1.000000000000
75 0.000000000000 1.000000000000

シミュレーション

より一般的な 5×5 マス、FREE あり、ボール 75 個の場合について、モンテカルロ法を使ってビンゴするまでボールを引き続けるシミュレーションを 10 万回した結果と理論値を比較したグラフを示す。横軸がボールを引く回数、縦軸がそこで初めてビンゴする確率である。

青い点がシミュレーション結果、赤い点が理論値であるが、どうだろう。

参考