Penneyのゲーム

第 $1\sim3$ 回、第 $4\sim6$ 回、…、第 $3m-2\sim3m$ 回の $m$ 個の組を考える。各組の 3 回の結果が $A$ と一致する確率は $\dfrac18$ で、組ごとの結果は互いに独立である。第 $3m$ 回までに $A$ が現れないなら、どの組も $A$ と一致しないので、その確率は $\left(1-\dfrac18\right)^m=\left(\dfrac78\right)^m$ 以下である。$m\to\infty$ で $\left(\dfrac78\right)^m\to0$ なので、$A$ がいつまでも現れない確率は $0$ である。ゲームは $A$ が現れた時点までには必ず終わるので、確率 $1$ で終わる。$\square$

状態 $s$ から始めて、次の 1 回の結果で場合を分ける。H が出る確率は $\dfrac12$ で、そのとき以後の結果は前の結果と独立なので、以後に $B$ が先に現れる確率は状態 $s_{\text{H}}$ から始めた場合と同じ $x_{s_{\text{H}}}$ である（状態だけで次の状態が決まるので、それより前の結果は勝ち負けに関係しない）。T の場合も同じである。2 つの場合は同時には起こらないので、足して式を得る。$\square$

方針：各並びについて状態ごとの期待値 $e_s$ の連立方程式を立てて解く。状態の移り方は図 2 のとおりである。
段 1（HHT）。状態は「始め」、H、HH で、期待値を $e_0,e_1,e_2$ とする。「始め」で H なら H へ、T なら「始め」のまま。H で H なら HH へ、T なら HT の最後の部分に頭の部分がないので「始め」へ。HH で T なら HHT が現れ、H なら HHH の最後の HH が頭の部分なので HH のままである。よって
$$ e_0=1+\frac12e_1+\frac12e_0,\qquad e_1=1+\frac12e_2+\frac12e_0,\qquad e_2=1+\frac12e_2+\frac12\cdot0 $$
である。3 つ目から $\dfrac12e_2=1$、$e_2=2$。1 つ目から $\dfrac12e_0=1+\dfrac12e_1$、つまり $e_0=2+e_1$。2 つ目に $e_2=2$ を入れて $e_1=2+\dfrac12e_0$。これを $e_0=2+e_1$ に入れて $e_0=4+\dfrac12e_0$、よって $e_0=8$、$e_1=6$ である。
段 2（HTH）。状態は「始め」、H、HT。H で H が出ると HH で、最後の H が頭の部分なので H のまま、T なら HT へ。HT で H なら HTH が現れ、T なら HTT で頭の部分がないので「始め」へ。よって
$$ e_0=1+\frac12e_1+\frac12e_0,\qquad e_1=1+\frac12e_1+\frac12e_{\text{HT}},\qquad e_{\text{HT}}=1+\frac12\cdot0+\frac12e_0 $$
である。1 つ目から $e_0=2+e_1$、2 つ目から $e_1=2+e_{\text{HT}}$、3 つ目は $e_{\text{HT}}=1+\dfrac12e_0$。順に入れると $e_0=2+2+1+\dfrac12e_0=5+\dfrac12e_0$、よって $e_0=10$、$e_1=8$、$e_{\text{HT}}=6$ である。
段 3（HHH）。状態は「始め」、H、HH で、どの状態でも T が出ると「始め」にもどる。
$$ e_0=1+\frac12e_1+\frac12e_0,\qquad e_1=1+\frac12e_2+\frac12e_0,\qquad e_2=1+\frac12\cdot0+\frac12e_0 $$
1 つ目から $e_0=2+e_1$。3 つ目を 2 つ目に入れて $e_1=1+\dfrac12\left(1+\dfrac12e_0\right)+\dfrac12e_0=\dfrac32+\dfrac34e_0$。よって $e_0=\dfrac72+\dfrac34e_0$、$\dfrac14e_0=\dfrac72$、$e_0=14$ である。
段 4（H と T の入れ替え）。H と T を入れ替えても、硬貨の表と裏の確率は同じ $\dfrac12$ なので、連立方程式は文字の名前が変わるだけで同じ形になり、同じ解をもつ。8 つの並びは、入れ替えで HHH と TTT、HHT と TTH、HTH と THT、HTT と THH の 4 組に分かれる。まだ解いていない組は HTT と THH なので、HTT を解く。HTT は、状態「始め」、H、HT で、H で H が出ると H のまま、HT で H が出ると HTH の最後の H が頭の部分なので H にもどる。段 2 と同じ型の連立方程式を解いて $e_0=8$ を得る（計算は下に畳む）。

方針：H と T の入れ替えで表の右半分を左半分に帰着させ、左半分の 4 列を 1 つずつ計算する。ゲームが確率 $1$ で終わることは lem-pny-end で示したので、先手が勝つ確率は $1$ から後手が勝つ確率を引いたものである。
段 1（入れ替え）。H と T を入れ替えても、硬貨の表と裏の確率は同じなので、先に現れる確率は変わらない。表の右半分の 4 列は、左半分の 4 列の $A$ と $B$ の両方で H と T を入れ替えたもの（HHH と THH の組なら TTT と HTT の組）なので、左半分を示せばよい。
段 2（HHH に対する THH）。ex-pny-start-hhh で示したとおり $\dfrac78$ である。
段 3（HHT に対する THH）。ex-pny-start で示したとおり $\dfrac34$ である。
段 4（HTH に対する HHT）。状態は「始め」、H、HH、HT である（図 3）。状態 $s$ から始めて HHT が先に現れる確率を $x_s$ とし、lem-pny-first-step を使う。

• HH の状態：T なら HHT が現れる。H なら HHH で、状態は HH のまま。よって $x_{\text{HH}}=\dfrac12x_{\text{HH}}+\dfrac12\cdot1$、つまり $x_{\text{HH}}=1$ である。
• HT の状態：H なら HTH が現れて先手が勝つ。T なら HTT で、最後の部分に頭の部分がないので「始め」へ。よって $x_{\text{HT}}=\dfrac12\cdot0+\dfrac12x_0$ である。
• H の状態：H なら HH へ、T なら HT へ。よって $x_{\text{H}}=\dfrac12x_{\text{HH}}+\dfrac12x_{\text{HT}}=\dfrac12+\dfrac14x_0$ である。
• 「始め」：H なら H へ、T なら「始め」のまま。よって $x_0=\dfrac12x_{\text{H}}+\dfrac12x_0$、つまり $x_0=x_{\text{H}}$ である。
  最後の 2 つから $x_0=\dfrac12+\dfrac14x_0$、$\dfrac34x_0=\dfrac12$、$x_0=\dfrac23$ である。連立方程式の解はこのようにただ 1 つに決まり、本当の確率は lem-pny-first-step によりこの方程式を満たすので、本当の確率は $\dfrac23$ である。
  段 5（HTT に対する HHT）。段 4 と同じ状態で、違うのは HT の状態からの移り方だけである。HT で T が出ると HTT が現れて先手が勝ち、H が出ると HTH の最後の H が頭の部分なので H の状態へ移る。段 4 と同じ型の連立方程式を解いて $x_0=\dfrac23$ を得る（計算は下に畳む）。$\square$
  段 5 の連立方程式を開く

  $x_{\text{HH}}=1$ は段 4 と同じで、$$x_{\text{HT}}=\frac12x_{\text{H}}+\frac12\cdot0,\qquad x_{\text{H}}=\frac12x_{\text{HH}}+\frac12x_{\text{HT}}=\frac12+\frac14x_{\text{H}},\qquad x_0=x_{\text{H}}$$ である。2 つ目から $\dfrac34x_{\text{H}}=\dfrac12$、$x_{\text{H}}=\dfrac23$、よって $x_0=\dfrac23$ である。

thm-pny-main の表の 2 列目（先手 HHT、後手 THH）から、THH が HHT より先に現れる確率は $\dfrac34$ である。4 列目（先手 HTT、後手 HHT）から、HHT が HTT より先に現れる確率は $\dfrac23$ である。6 列目（先手 TTH、後手 HTT）から、HTT が TTH より先に現れる確率は $\dfrac34$ である。8 列目（先手 THH、後手 TTH）から、TTH が THH より先に現れる確率は $\dfrac23$ である。
推移的だとすると、THH は HHT より、HHT は HTT より先に出やすいので THH は HTT より先に出やすく、さらに HTT は TTH より先に出やすいので THH は TTH より先に出やすい。つまり THH が先に現れる確率は $\dfrac12$ より大きい。ところが TTH が先に現れる確率は $\dfrac23$ で、引き分けはないので THH が先に現れる確率は $\dfrac13$ である。これは矛盾である。$\square$