Probability Model Of Bingo Game

本文介紹經典的"賓果 Bingo" 遊戲，機率與期望值的解析計算公式的計算概念，相關的數學建模....等等

[遊戲情境]

總共有 $n$ 個相異的號碼彩球，號碼集為 $S:=\{1,2,3,....n\}$，今玩家可以花$1$元，買$1$張賓果卡 ($5 \times 5$) 位置座標集 $Z$, $|Z|=25$，然後從$S$ 隨機均勻選擇 $25$個相異的號碼並排列到一個佇列(queue)，而開球只會開前 $m$ 顆球，$25 \leq m\leq n$，而給定獎項圖形集 $\color{red}{p \in P := \{Bingo，王，十，一_1,一_2,...,一_5  \}}$ (可自行設計) ，以及已知賠率表向量 $odds_{P}$。開完球後，把Bingo 卡上的中獎的號碼圈起來形成"中獎圖形"
=====================================================
其中獎項圖形 :
"$Bingo$" 代表$25$個號碼全中
"十"代表第 $3$ 列(row)  第 $3$ 行 (column) 有中 (共$9$個號碼)
"王"代表第 $1$ , $3$ , $5$ 列(row)  第 $3$ 行 (column) 有中 (共$17$個號碼)
"$一_k$" 代表第 $k$ 列有中 (共$5$個號碼)

=====================================================

若中獎圖形有涵蓋獎項圖形大致會獲得，賠率 $odds_{p} \times 1$ 元，但有些合理規則:
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
$[ 規則 1 ]$ 若獎項圖形 $p_1,p_2$ 有完全重疊$(p_1 \subseteq p_2)$，則以大圖形 $odds_{p_2}$ 賠率算
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
$$\color{green}{ 重要假設: 合理的遊戲， odds_{p_1} <  odds_{p_2} ，也就是大圖形對大賠率}$$

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
$[ 規則 2 ]$ 若獎項圖形 $p_1,p_2$ 非完全重疊$(p_1 \not\subseteq p_2)$ 時，則以賠率相加 $odds_{p_1} + odds_{p_2}$

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

例如: 中獎圖形為 "$Bingo$" 時，賠率就是 $odds_{Bingo}$ ，而非 $\displaystyle{\sum_{p\in P}odds_{p}}$
例如: 中獎圖形為 "$田$" 時，賠率就是 $odds_{\text{王}}$ ，因為 "$十$" , "$一_k$" $\subset$ "$王$"
例如: 中獎圖形為 "$土$" 時，賠率就是 $odds_{十}  \underset{plus}{+}  odds_{一_{5}}$
註:  中獎圖形 $\color{red}{"田" , "土" \not\in P}$，$\color{blue}{\text{概念上需區分 "中獎圖形" 與 "獎項圖形" 的差異}}$


[數學建模] 

首先可把中獎圖形二元編碼化，例如: "$田$"$= \overbrace{11111,10101,11111,10101,11111}^{\text{row}1,\text{row}2,...,\text{row}5}$
$1$ 代表那個位置的號碼有中， $0$ 代表那個位置的號碼沒中。
令所有中獎圖形編碼元/編碼集為 $b \in 2^{Z}$ ，所以遊戲中會有 $2^{|Z|} = 33554432$ 互斥基本事件 ，此樣本空間大小對電腦來說是可以在有效時間被處理的 ，所以玩$1$張卡，此遊戲的期望回報值/淨收入分別為
$$\text{期望回報值}  = \sum_{b \in 2^{Z}} prob_b  \cdot  odds_{b} \cdot 1$$
$$\text{期望淨收入 } =  \sum_{b \in 2^{Z}} prob_b  \cdot  odds_{b} \cdot 1 - 1$$

其中 $prob_{b}$ 為中獎圖形 $b$ 的機率，
$odds_{b} := \sum_{p \in P_{b}}  odds_{p}$為中獎圖形 $b$ 的賠率
其中 $P_{b} \subset P$ 為中獎圖形 $b$ 的最高層獎項圖形集 !!

[構造 $P_{b}$ ]
單純演算法概念為，先把每個可能中獎元  $b \in 2^{C}$  與獎項元 $p \in P \subset 2^{C}$ 比對集合隸屬關係，收集 $p$ 滿足以下邏輯: $$p \in P_{b}  \Longleftrightarrow \left( p \subseteq b  \text{ and }  \underbrace{\not\exists p' \in P \text{ s.t } p\subset p'   \subset  b  }_{p \text{ is maximal }}\right)$$

$$\color{purple} {詳細實作留給讀者自行推敲 ，這也是筆者認為 Bingo 遊戲的數學有趣奧秘的部分 :)}$$
[**Warning**]
$$\color{green}{  若 [規則1] 改成取最高賠率，但最高層的賠率值不是"最大"，則作法不同，故重要假設是重要的 !! }$$

[計算 $prob_{b}$ 公式]
給定一個中獎元 $b$ ，可以先計算 $b$ 裡 $1$ 的個數，記做 ${\#1}_{b}$
可以利用以下組合學公式 (台式寫法:  $C^{x}_{y} \equiv \frac{x!}{y!(x-y)!}$)
$$prob_{b} := \left[\frac{ C^{{\#1}_{b}}_{{\#1}_{b}} \cdot C^{|S|-|Y|}_{m-\#1_{b}}}{C^{|S|}_{m}} \right]  = \left[ \frac{C^{\text{總球數}-\text{Bingo 卡大小}}_{\text{開球數} - \text{中獎圖形$b$中獎數}}}{C^{\text{總球數}}_{\text{開球數}}  } \right]$$
====================================================
計算邏輯:
因為不管同個號碼先開還後開，只要"存在"在 Bingo 卡裡就算中獎，所以使用組合的想法。分子的部分，可以假設玩家依序選定了號碼 $1,2,3,4,...25$ 在 Bingo 卡裡，等著開獎，則若要計算$\color{red}{恰好}$中 "田" 這個字，代表 ${\#1}_{b} = 21$ ，而其它位置都沒中獎，即號碼 $7,9,17,19$ 沒中。剩下的 $(\text{開球數} - \text{中獎圖形$b$中獎數})$ 顆球在開獎的過程會出現在 Bingo 卡以外的數字，也就是 $26 \sim n$ ，否則就與 $\color{red}{恰好}$ 矛盾!!
=====================================================

[機率算法- 有中獎圖形$b$ ]
考慮 Merge Encoding， $2 \equiv \{0,1\}$  詳細可參考:

http://discoverforgottenmath.blogspot.com/2018/07/binary-representation-merge-encoding.html

則如果一般口語問說，$\color{blue}{有中獎圖形 ( b = 田 ) 的機率}$，事實上是求 $11111,12121,11111,12121,11111$ 編碼展開的機率總和 !!
而非只是 $\color{red}{恰好}$ ，$11111,10101,11111,10101,11111$


[機率算法- 有獎項圖形 $p$ (含賠率規則) ]

考慮自然對偶對應(Natural Dual Correspondence) ，定義 $B_{p}$  滿足以下邏輯

$$p \in P_{b}  \Longleftrightarrow  b \in B_{p}$$
$$\color{blue}{有獎項圖形  ( p = 王 ) 的機率}  =  \sum_{b \in B_p} prob_{b}$$

[小結]
從 Bingo 遊戲的分析發現，人為設計的獎項集$P$ 為產生類似資料結構的 heap ，而中獎圖形則為 Hidden Nodes 的概念，本文介紹窮舉所有 Hidden Nodes 來去分析與給定的 heap 的結構的關係，或許日常生活中其它的應用問題也有這些現象，分享給讀者。

[以上純為學術經驗交流知識分享，如有錯誤或建議可留言~~] 

by Plus & Minus 2018.08