ビンゴゲームの期待値

年末ということで、会社の忘年会に参加したところ、ビンゴ大会が行われました。*1

後から調べたところ、市販されている5x5のビンゴカードは、各マスに75までの数が書かれるのが一般的なようです。
私が参加したビンゴ大会は少し変わっていて、マスの数は変わらないものの、中にイラストが書かれていて、その種類は300近くありました。

この大会では、58個目の数（イラスト）が抽選された時に最初のビンゴ者が現れたのですが、これだけ種類が多いとなかなかマスを空けられず、この時点で（何なら大会終了時でも）私のビンゴカードはほとんど空いていない状態であり、今回のビンゴが早いのかどうかが気になりました。

帰宅してからいろいろ計算していたのですが、やはり似たような話題は他でもあるらしく、以下のヨビノリさんの動画について教えてもらいました。

www.youtube.com

この動画では、ビンゴの確率はシミュレーション結果を参照していて、実際、意外にも正確な確率を挙げている記事を見つけられなかったので*2、今回の計算結果について一部まとめてみます。

なお、記事中のプログラムは gist に公開してあります。

ビンゴゲームのルール
計算すること
ビンゴになるまでに空けるマスの数の期待値
抽選回数ごとのビンゴの確率
抽選回数の期待値
おわりに

ビンゴゲームのルール

今回対象にする「ビンゴゲーム」のルールを、以下のように定義します。

カードのサイズは5x5
中央のマスはFreeであり、最初から空いているものと見なす
Freeを除いた各マスには、1 ~ $N$ までの数が書かれている
どのマスにどの数が書かれるかはランダム
ゲームは、1 ~ までの数の抽選を繰り返すことで進行する
- まだ抽選されていない数がランダムに選ばれる
- 抽選された数と同じ数が書かれたマスがあれば、空ける
- 全ての数が選ばれるまで繰り返す
縦・横・斜めのいずれかのライン上の5マスが、全て空いたらビンゴ（12ラインある）

曖昧な部分もありますが、ビンゴゲームに参加したことがあれば、おそらく誤解は生じないと思います。

なお、市販のビンゴでは、ある数が書かれる場所に制限がある*3ようですが、今回はこのような制限は考えません。
$N = 75$ とすれば、上記の動画と同じルール設定になります。

計算すること

そもそもの計算のモチベーションは、

ビンゴになるまでに空けるマスの数の期待値
ビンゴになるまでの抽選回数の期待値

を知りたいことにありました。
これに加えて、動画内では近似的な値が参照されていた、抽選回数ごとのビンゴの確率を求めます *4。

ビンゴになるまでに空けるマスの数の期待値

ランダムにマスを空けていった時、ビンゴになるまでに空けることになるマスの数の期待値を求めます。
この問題設定では、「抽選」は関係ありません。

分かりやすいように、マス目に1 ~ 24までの番号を振ります。

すると、ビンゴになる条件は、以下のいずれかのマス目の全てが空いていることと同じになります。

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

ここからはプログラムを使って計算するのですが、さすがに $24!$ 通りの総当りをするのは厳しいので、空いているマスのパターンが同じものを同一視して全探索します。

さて、この方法だと、 $k$ 回目にビンゴが発生している場合の数を求めることはできそうですが、丁度 $k$ 回目にビンゴが発生する場合の数を求めること ≒ 丁度 $k$ 回目にビンゴが発生する確率を求めることが難しそうです。しかし、 $k$ 回目にビンゴが発生している確率と $k-1$ 回目にビンゴが発生している確率が分かれば、その差として丁度 $k$ 回目にビンゴが発生する確率を求めることができるので、大きな問題ではありません。

というわけで、以下の順に計算していきます。

1. $k$ 個マスが空いている時に、ビンゴになるパターンを全列挙する
2. $k$ 個マスが空いている時に、ビンゴになっている確率を求める
3. 丁度 $k$ 個マスが空いている時に、ビンゴになっている確率を求める

k個マスが空いている時に、ビンゴになるパターンを全列挙する

24個の各マスについて、空いているか、空いていないかの2通りの状態があります。
全部で $2^{24}$ 通りのパターンを列挙して、それぞれビンゴになっているかどうかを確認します。

$i$ 番目のパターンについて、 $i$ の $k$ 個目のbitが立っていれば（ $(i \gg k) \And 1 \neq 0$ ）、 $k$ マス目が空いているものとして考えていきます。

import math
from fractions import Fraction

bingo5x5_seqs = [
  [1, 2, 3, 4, 5],
  [6, 7, 8, 9, 10],
  [11, 12, 13, 14],
  [15, 16, 17, 18, 19],
  [20, 21, 22, 23, 24],
  [1, 6, 11, 15, 20],
  [2, 7, 12, 16, 21],
  [3, 8, 17, 22],
  [4, 9, 13, 18, 23],
  [5, 10, 14, 19, 24],
  [1, 7, 18, 24],
  [5, 9, 16, 20],
]

def is_bingo(pattern: list[bool], bingo_seqs: list[list[int]]) -> bool:
  """
  ビンゴかどうか判定する.

  Args:
    pattern: ビンゴカードのマスの穴空きパターン. Trueならマスが空いている.
    bingo_seqs: ビンゴのパターン. listに含まれる全ての番号のマスが空いていれば、ビンゴと判定する.
  Returns:
    ビンゴならTrue
  """
  return any(all(pattern[i-1] for i in seq) for seq in bingo_seqs)


def build_card_pattern(n: int, mask: list[int]) -> list[bool]:
  """
  ビンゴカードの穴空きパターンを作る.

  Args:
    n: 全列挙中のパターンの番号. 0 <= n < 2^24

  Returns:
    真理値のリスト. Trueならマスが空いている
  """
  return [(n & m) != 0 for m in mask]


def count_patterns(n: int, bingo_seqs: list[list[int]]) -> list[int]:
  """
  ビンゴカードの空いているマスの数ごとに、ビンゴになっているパターンの数を数え上げる.

  Args:
    n: マス目の数 (24)
    bingo_seqs: ビンゴのパターン. listに含まれる全ての番号のマスが空いていれば、ビンゴと判定する.
  Returns:
    リスト. indexがiの要素は、i個のマスが空いているパターンの数を表す.
  """
  counts = [0] * (n + 1) # counts[i]: i個のマスが空いているパターンの数

  mask = [1 << i for i in range(n)]
  for i in range(1 << n):
    pattern = build_card_pattern(i, mask)

    if is_bingo(pattern, bingo_seqs):
      counts[i.bit_count()] += 1

  return counts


# k個のマスの空け方
counts = count_patterns(24, bingo5x5_seqs)
for i, c in enumerate(counts):
  print(i, c)

このPythonコードは死ぬほど遅いですが、私の環境だと80秒程で終了して、以下の結果が得られます。*5
中央のFreeマスは $k$ にカウントしていないことに注意してください。

k	ビンゴのパターンの数
0	0
1	0
2	0
3	0
4	4
5	88
6	912
7	5928
8	27102
9	92520
10	244092
11	507696
12	841100
13	1113360
14	1174620
15	981424
16	644445
17	331056
18	133428
19	42480
20	10626
21	2024
22	276
23	24
24	1

k個マスが空いている時に、ビンゴになっている確率を求める

以下、 $k$ 個マスが空いている事象を $H_k$ 、ビンゴになっている事象を $B$ と書くことにします。

$k$ 個マスが空いている時、マスの空け方は全部で ${}_{24} P_k$ 通りあり、それが特定のパターンであれば、空ける順番だけを考えて $k!$ 通りあります。
したがって、 $k$ 個マスが空いていてビンゴになっているパターンが $a$ 通りあるならば、

$P \lbrack B | H_{k} \rbrack = \dfrac{a \cdot k!}{{}_{24} P_{k}}$

です。
パターンの数は列挙できているので、 $0 \leqq k \leqq 24$ に対して、 $P \lbrack B | H_{k} \rbrack$ を計算できます。

def calc_P_given_Hk(k: int, counts: list[int]) -> Fraction:
  """
  ビンゴカードのマスがk個空いている時に、ビンゴになっている確率(P[B|H_k])を計算する.

  Args:
    k: 空いているマスの数
    counts: 空いているマスの数ごとに、ビンゴになっているパターンの数を数え上げたリスト.
  """
  return Fraction(counts[k] * math.factorial(k), math.perm(24, k))


# k個マスが空いている時に、ビンゴになっている確率(P[B|H_k])
ps_given_Hk = [calc_P_given_Hk(i, counts) for i in range(len(counts))]
for i, p in enumerate(ps_given_Hk):
  print(i, p, p.numerator / p.denominator)

結果は以下の通り。

k	$P \lbrack B \vert H_{k} \rbrack$
0	0
1	0
2	0
3	0
4	2/5313
5	1/483
6	12/1771
7	13/759
8	9034/245157
9	11565/163438
10	20341/163438
11	1511/7429
12	16175/52003
13	23195/52003
14	97885/163438
15	61339/81719
16	71605/81719
17	22/23
18	33357/33649
19	1770/1771
20	1
21	1
22	1
23	1
24	1

先の動画で、18個マスが空いてビンゴにならなかった話がされていましたが、この確率は $1 - 33357/33649 = 292/33649 \fallingdotseq 0.0086778$ で、およそ115人に1人の割合で発生するということになります。

丁度k個マスが空いた時に、初めてビンゴになる確率を求める

最後に、丁度 $k$ 個マスが空いた時に初めてビンゴになる確率を求めます。
これを $P \lbrack B | H_{k} \rbrack '$ と書けば、

$P \lbrack B | H_{k} \rbrack ' = P \lbrack B | H_{k} \rbrack - P \lbrack B | H_{k-1} \rbrack$

です。

def calc_from_sum(ps: list[Fraction]) -> list[Fraction]:
  """
  累積された確率のリストから、元の確率のリストを計算する.

  Args:
    ps: 累積された確率のリスト
  """
  return [ps[0]] + [ps[i] - ps[i-1] for i in range(1, len(ps))]


# 丁度k個目のマスを空けた時にビンゴになる確率(P[B|H_k]')
ps_given_Hk_ = calc_from_sum(ps_given_Hk)
for i, p in enumerate(ps_given_Hk_):
  print(i, p, p.numerator / p.denominator)

k	$P \lbrack B \vert H_{k} \rbrack '$
0	0
1	0
2	0
3	0
4	2/5313
5	3/1771
6	25/5313
7	5/483
8	4835/245157
9	16627/490314
10	4388/81719
11	679/8602
12	5598/52003
13	7020/52003
14	174905/1144066
15	24793/163438
16	10266/81719
17	6561/81719
18	1171/33649
19	39/4807
20	1/1771
21	0
22	0
23	0
24	0

ビンゴになるまでに空けるマスの数の期待値（ $E_{k}$ とします）を計算すると、 $E_{k} = 4245967/312018 \fallingdotseq 13.608083508002743$ が得られます。
中央のFreeマスも合わせると、14 ~ 15マス程度ということですね。

def calc_E(ps: list[Fraction]) -> Fraction:
  """
  期待値を計算する
  """
  ret = Fraction(0, 1)
  for i in range(len(ps)):
    ret += i * ps[i]

  return ret


print(calc_E(ps_Bk))

抽選回数ごとのビンゴの確率

今度は、抽選回数ごとのビンゴの確率を求めていきます。

先ほどと同様、 $K$ 回目の抽選後にビンゴになっている確率を求めて、 $K-1$ 回目の抽選後にビンゴになっている確率との差によって計算します。
以下、 $K$ 回目の抽選後の確率を $P_{K}$ と表すことにします。例えば、求めたい $K$ 回目の抽選後にビンゴになっている確率は $P_{K} \lbrack B \rbrack$ と書きます。

$K$ 回目の抽選後に $k$ マス空いている時の条件付き確率を考えることにより、

$P_{K} \lbrack B \rbrack = \displaystyle \sum_{k} P \lbrack B | H_{k} \rbrack \cdot P_{K} \lbrack H_{k} \rbrack$

が分かります。

${ \begin{eqnarray} P_{K} \lbrack H_{k} \rbrack = \left\{ \begin{array}{ll} 0 & (k > K \lor (K - k) > 75 - 24) \\ \dfrac {{}_{K} C_{k} \cdot {}_{24} P_{k} \cdot {}_{51} P_{K-k}}{{}_{75} P_{K}} & (otherwise) \end{array}\right. \end{eqnarray} }$
であり、 $P \lbrack B | H_{k} \rbrack$ はすでに求めているので、 $P_{K} \lbrack B \rbrack$ を計算できます。

def calc_P_K_B(N: int, n: int, K: int, ps: list[Fraction]) -> Fraction:
  """
  K回目の抽選後にビンゴになっている確率(P_K[B])を計算する.

  Args:
    N: 抽選総数 (75)
    n: マスの数 (24)
    K: 抽選回数
    ps: マスがk個空いている時、それがビンゴである確率(P[B|H_k])
  """
  ret = Fraction(0, 1)
  for k in range(min(K, n) + 1):
    p = calc_P_K_Hk(N, n, K, k) * ps[k]
    ret += p

  return ret


# K回目の抽選後にビンゴになっている確率(P_K[B])
ps_B = [calc_P_K_B(75, 24, i, ps_given_Hk) for i in range(76)]
for i, p in enumerate(ps_B):
  print(i, p)

先ほどと同様に、丁度 $K$ 回目の抽選後にビンゴになる確率を $P_{K} \lbrack B \rbrack '$ と書けば、

$P_{K} \lbrack B \rbrack ' = P_{K} \lbrack B \rbrack - P_{K-1} \lbrack B \rbrack$

です。

# 丁度K回目の抽選でビンゴになる確率(P_K[B]')
ps = calc_from_sum(ps_B)
for i, p in enumerate(ps):
  print(i, p)

# 抽選回数の期待値
print(calc_E(ps))

k	$P_{K} \lbrack B \rbrack '$
0	0
1	0
2	0
3	0
4	2/607725
5	196/14382825
6	304/8629695
7	628/8629695
8	147796/1124736915
9	244978048/1130360599575
10	1387539764/4144655531775
11	8836974296/17960173971025
12	1362393407/1959291705930
13	195839812429/205725629122650
14	4151338277/3270510001437
15	707599909481/427502378759265
16	18103674568309/8550047575185300
17	511299087082/191953122882775
18	710305313728003/215134285310912475
19	7827569554862/1938146714512725
20	582168537354/119263482788975
21	6444558015450568/1104355997929350705
22	9805891878046472/1419886283052022335
23	18463091933944714/2280423424295672235
24	36378750114515606/3866804936849183355
25	712614729737722252/65735683926436117035
26	271522447653999787/21911894642145372345
27	497506078328867198/35396137498850216865
28	124465742791689541/7865808333077825970
29	33120007382489577/1872811507875672850
30	1900890014103763/96869560752189975
31	28902236732320489/1336799938380221655
32	4986766542109411/210821495658529580
33	12189629800508932/474348365231691555
34	41840454473190082/1509290253009927675
35	23750605450244/799835852151525
36	10825123490674/342786793779225
37	1981011803872/59416377588399
38	17300348815592/495136479903325
39	10795906141408/297081887941995
40	2571034168354/68557358755845
41	54103575725904/1409234596647925
42	8404463697145862/215612893287132525
43	4046142251526044/103119209832976425
44	61897142200670587/1581161217438971850
45	8767228850746273/226576260742410450
46	16877970346826341/445599979460073885
47	116494971251739/3174256793009615
48	553418757184023473/15731616666155651940
49	22265516552462938/667851650921702205
50	684002409096065647/21911894642145372345
51	1896752667983133982/65735683926436117035
52	101719865924434562/3866804936849183355
53	2342850775461932/99148844534594445
54	2513444507055104/120329346021357825
55	14313665838593366/788825712806679075
56	1998297391236/129209780967515
57	37025069138516/2868457137478833
58	150953522820961/14342285687394165
59	351513454773514/42037733911327725
60	3064245342741/475002643065850
61	96597205657/20070534214050
62	18830002967/5450850002395
63	81250533989/34287604853775
64	2011638231/1306194470620
65	673334360/718406958841
66	31563028/60067471475
67	33277944/125595622175
68	651046/5623684575
69	31748/771878275
70	352/33559925
71	4/2876565
72	0
73	0
74	0
75	0

また、抽選回数の期待値（ $E_{K}$ とします）は $8491934/205275 \fallingdotseq 41.36857386432834$ です。

抽選回数の期待値

めでたしめでたし、で終わってもよいのですが、もう少し続けます。
実のところ、期待値だけ計算したいのであれば、丁度 $K$ 回抽選した後にビンゴになる確率を求める必要はありません*6。

違う問題として、最初のマスが空くまでの抽選回数の期待値を考えます。
マスに書かれていない数 $x$ が、マスに書かれているどの数よりも先に抽選される確率は $1/25$ なので、これは $(75 - 24) \times 1/25 + 1$ というように求められます*7。

同様に、 $k$ 個のマスが空くまでの抽選回数の期待値は、 $(75 - 24) \times k/25 + k = 76k/25$ となります。

さて、この記事では、最初に「ビンゴになるまでに空けるマスの数の期待値（ $E_{k}$ ）」を求めました。
$E_{k}$ は自然数ではないので、「 $E_{k}$ 個のマスが空くまでの抽選回数」を考えることはできませんが、試しに上の式に代入してみると、

$76/25 * 4245967/312018 = 8491934/205275$

となり、先程求めた期待値に一致しています。

ということは、なにかありそうなわけですが、実際、抽選回数の期待値 $E_{K}$ は、

$\begin{eqnarray*} E_{K} &=& \displaystyle \sum_{K} K \cdot P_{K} \lbrack B \rbrack ' \\ &=& \displaystyle \sum_{K} K \sum_{k} P \lbrack B | H_{k} \rbrack ' \cdot P_{K} \lbrack H_{k} \rbrack \\ &=& \displaystyle \sum_{K} \sum_{k} K \cdot P \lbrack B | H_{k} \rbrack ' \cdot P_{K} \lbrack H_{k} \rbrack \\ &=& \displaystyle \sum_{k} P \lbrack B | H_{k} \rbrack ' \sum_{K=k} K \cdot P_{K} \lbrack H_{k} \rbrack \\ \end{eqnarray*}$

で、 $\displaystyle \sum_{K=k} K \cdot P_{K} \lbrack H_{k} \rbrack$ は「 $k$ 個のマスが空くまでの抽選回数の期待値」なので、

$\begin{eqnarray*} E_{K} &=& \displaystyle \sum_{k} P \lbrack B | H_{k} \rbrack ' \times 76k / 25 \\ &=& 76/25 \displaystyle \sum_{k} k \cdot P \lbrack B | H_{k} \rbrack ' \\ &=& 76/25 \times E_{k} \\ \end{eqnarray*}$

となり、この計算で正しいことが分かります。

おわりに

私の参加したビンゴゲームにおいて、58回の抽選でビンゴになったのは早かったのかどうか……。
もちろん計算したのですが、概算しかしてない & 力尽きたので、気になる方は計算してみてください。

*1:年が明けているように見えるのは気のせい

*2:少なくとも日本語では。投稿直前にネタかぶりしているのを観測しましたが

*3:例えば、1列目には1 ~ 15までの数しか入らないなど

*4:抽選回数の期待値を求めるので、抽選回数ごとのビンゴの確率を求める必要がありそうにも見えますが……

*5:もともとはGoで書いていて、そちらの実装だと2秒ほどで終了します

*6:元々、「ビンゴになるまでに空けるマスの数の期待値」を求めようとしていたのは、これが理由

*7:期待値の加法性を使っています