ペニーのゲームの勝率｜最適戦略とマルコフ連鎖

「ペニーのゲーム」は，連続したコイントスを行い，自分が選んだ3連続のパターンが相手より先に出現するかを競う，確率が絡むゲームである．一見公平に見えるが，実は数学的に後攻が有利であることを示せる．本記事では，ゲームのルール，戦略，マルコフ連鎖による勝率計算を解説する．

この記事では，コインの表 (H - Head) が出る確率を$p$，裏 (T - Tail) が出る確率を$1-p$とする．公平なコイントスでは$p=1/2$である．

ペニーのゲームとは？直感に反する勝率
ペニーのゲームの最適戦略｜勝率を最大化する方法
遷移確率 | マルコフ連鎖による勝率の計算
パターンがでる確率 | マルコフ連鎖による勝率の計算
勝率 | HHH vs. THH
勝率 | HHT vs. THH
参考文献

ペニーのゲームとは？直感に反する勝率

2人のプレイヤーが，長さ3のコインのパターンをそれぞれ選ぶ（例えば，表・裏・表ならHTH）．コインを連続して投げ，先に自分の選んだパターンが出たプレイヤーが勝利するゲームを「ペニーのゲーム（➡ Wikipedia）」と呼ぶ．

どのパターンが出現する確率も$(1/2)^{3} = 1/8$であるため，このゲームは一見すると公平に見えるが，実はそうではない．

実際には，相手のパターンに対して有利なパターンを選ぶことで，高確率で勝つことができる．

ペニーのゲームの最適戦略｜勝率を最大化する方法

相手のパターンに対して自分がどのパターンを選べば最も勝率が高くなるかと，そのとき自分が相手に対して何倍勝ちやすいかをまとめたものが下表である．

相手のパターンが「$\text{ABC}$」であるとき，自分は「$\text{(Bの逆)AB}$」を選ぶのが最善である．例えば，HHTに対しては，THHを選ぶのが最善となる．

相手	自分	自分の勝率 / 相手の勝率
HHH	THH	7
HHT	THH	3
HTH	HHT	2
HTT	HHT	2
THH	TTH	2
THT	TTH	2
TTH	HTT	3
TTT	HTT	7

遷移確率 | マルコフ連鎖による勝率の計算

マルコフ連鎖を使うことで，相手より先に自分のパターンがでる確率をシステマチックに計算できる．

以降，以下の記事と同じ記法を用いる．
➡ コイントスのパターンとマルコフ連鎖 - Notes_JP

マルコフ連鎖による計算では，まず，各状態間の遷移が起きる確率を整理する．状態$i$から状態$j$への遷移確率を$p_{ij}$で表し，遷移確率を行列の形で表したものを遷移確率行列$P$と呼ぶ．

この問題の遷移確率行列は以下の形を取る．

\begin{aligned}
P&=\left(\begin{array} {ccc:c}
& & & \\
&U&&R \\
&&& \\ \hdashline
&0&&I
\end{array}\right)\\
\end{aligned}

$U$がパターンが出ていない状態内での遷移を表し，$R$がパターンが出ていない状態からパターンが出た状態への遷移を表している．単位行列$I$は，パターンが出たあとはその状態に留まることを表している（吸収状態）．

パターンがでる確率 | マルコフ連鎖による勝率の計算

上の記事で述べた通り，「パターンが出ていない状態$i$から始めて，$m$回目に始めてパターンが出る遷移」は

\begin{aligned}
U^{m-1} R \quad(m=1, 2, 3, \ldots)
\end{aligned}

と表せる．よって，「2人の選んだパターンが出ていない状態を何回か経た後，最後の1回どちらかのパターンがでる遷移」は

\begin{aligned}
\sum_{m=1}^{\infty} U^{m-1} R
&= (I - U)^{-1} R
\end{aligned}

となる．

勝率 | HHH vs. THH

「THHが勝つ確率」は「HHHが勝つ確率」の7倍である．つまり，

\begin{aligned}
& (\text{先にHHHが出る確率}) = \frac{1}{1 + 7} = \frac{1}{8} \\
& (\text{先にTHHが出る確率}) = \frac{7}{1 + 7} = \frac{7}{8}
\end{aligned}

である．これをマルコフ連鎖による計算で確かめる．

状態遷移図は下図のようになる．HHH側からTHH側への遷移はあるが逆はないことから，$p=1/2$の場合，THHの方が勝ちやすいことが読み取れる．

状態遷移図と遷移確率行列 (HHH vs. THH) — 状態遷移図と遷移確率行列$P$ (HHH vs. THH)

➡Wolfram|Alphaで$(I - U)^{-1}$を計算する

\begin{aligned}
(I - U)^{-1} R
&=
\begin{pmatrix}
1 & p & \frac{1}{p^{2}} - p & p^{2} & \frac{1}{p} - p^{2} \\
0 & 1 & \frac{1}{p^{2}} - 1 & p & \frac{1}{p} - p \\
0 & 0 & \frac{1}{p^{2}} & 0 & \frac{1}{p} \\
0 & 0 & \frac{1 - p}{p^{2}} & 1 & \frac{1}{p} - 1 \\
0 & 0 & \frac{1 - p}{p^{2}} & 0 & \frac{1}{p}
\end{pmatrix}
\begin{pmatrix}
0 & 0 \\
0 & 0 \\
0 & 0 \\
p & 0 \\
0 & p
\end{pmatrix} \\
&=
\begin{pmatrix}
p^{3} & 1 - p^{3} \\
* & * \\
* & * \\
* & * \\
* & *
\end{pmatrix}
\end{aligned}

よって，スタートから始めて，HHHが先に出る確率が$p^{3}$，THHが先に出る確率が$1 - p^{3}$である．特に，$p=1/2$のとき，

\begin{aligned}
& (\text{先にHHHが出る確率}) = \frac{1}{8} \\
& (\text{先にTHHが出る確率}) = \frac{7}{8}
\end{aligned}

が確かめられた．

勝率 | HHT vs. THH

「THHが勝つ確率」は「HHTが勝つ確率」の3倍である．つまり，「HHT」が先に出る確率と「THH」が先に出る確率の関係は，

\begin{aligned}
& (\text{先にHHTが出る確率}) = \frac{1}{1 + 3} = \frac{1}{4} \\
& (\text{先にTHHが出る確率}) = \frac{3}{1 + 3} = \frac{3}{4}
\end{aligned}

である．これをマルコフ連鎖による計算で確かめる．

状態遷移図は下図のようになる．HHH vs. THHの場合よりも，THH側への遷移が減っているから，$p=1/2$の場合に勝率の比率が7倍から3倍へ減少したことが定性的にも理解できる．

状態遷移図と遷移確率行列 (HHT vs. THH) — 状態遷移図と遷移確率行列$P$ (HHT vs. THH)

➡Wolfram|Alphaで$(I - U)^{-1}$を計算する

\begin{aligned}
(I - U)^{-1} R
&=
\begin{pmatrix}
1 & p & \frac{1}{p^{2}} - 1 & \frac{p^{2}}{1 - p} & \frac{1}{p} - p \\
0 & 1 & \frac{1 - p}{p^{2}} & \frac{p}{1 - p} & \frac{1}{p} - 1 \\
0 & 0 & \frac{1}{p^{2}} & 0 & \frac{1}{p} \\
0 & 0 & 0 & \frac{1}{1 - p} & 0 \\
0 & 0 & \frac{1 - p}{p^{2}} & 0 & \frac{1}{p}
\end{pmatrix}
\begin{pmatrix}
0 & 0 \\
0 & 0 \\
0 & 0 \\
1 - p & 0 \\
0 & p
\end{pmatrix} \\
&=
\begin{pmatrix}
p^{2} & 1 - p^{2} \\
* & * \\
* & * \\
* & * \\
* & *
\end{pmatrix}
\end{aligned}

よって，スタートから始めて，HHTが先に出る確率が$p^{2}$，THHが先に出る確率が$1 - p^{2}$である．特に，$p=1/2$のとき，

\begin{aligned}
& (\text{先にHHHが出る確率}) = \frac{1}{4} \\
& (\text{先にTHHが出る確率}) = \frac{3}{4}
\end{aligned}

が確かめられた．