偏ったコインのパターン競争

Part 1: P(HTHがHHTより先に現れる) = q/(1 + q) = (1 − p)/(2 − p).

• 「有用な接尾辞」の状態に関するマルコフ連鎖を構築する：S（進捗なし）、H、HH、HT。重要な構造的事実：状態HHからは、HHTパターンが確実に勝利する。なぜなら、ヘッドはHHにとどまり、最初のテールはHTHが決まる前に即座にHHTを完成させるからである。したがって、P(HTHが最初に勝つ | HH) = 0。
• S、H、HTからHTHが勝利する確率をそれぞれa、b、cとする。すると、a = p·b + q·a（よってa = b）、b = p·0 + q·c、およびc = p·1 + q·aとなる。これを解くと、a = q(p + qa)となり、a(1 − q²) = pq、したがってa = pq/(p(1+q)) = q/(1+q)が得られる。
• 健全性チェック：コインが公正な場合（p = 1/2）、これは1/3となり、HHTがHTHに2/3の確率で勝つというよく知られた結果と一致する。

Part 2: E[HTHまたはHHTのいずれかが最初に現れるまでのフリップ数] = (1 + p q²)/(p² q (1 + q))、ここでq = 1 − p。

• 同じ状態を使用し、期待追加フリップ数をE_S、E_H、E_HH、E_HTとする。すると、E_HH = 1 + p·E_HH、よってE_HH = 1/q；E_HT = 1 + q·E_S；E_H = 1 + p·E_HH + q·E_HT；およびE_S = 1 + p·E_H + q·E_S、すなわちE_S = 1/p + E_Hとなる。
• 代入すると、E_S(1 − q²) = 1/p + 1 + p/q + qとなり、1 − q² = p(1 + q)なので、これはE_S = (1 + p q²)/(p² q (1 + q))に単純化される。
• 健全性チェック：p = 1/2の場合、(1 + 1/8)/((1/4)(1/2)(3/2)) = (9/8)/(3/16) = 6フリップとなる。

Part 3: 「独立した非重複の3つのブロック」アプローチが失敗する理由。

• 境界発生が見落とされる：パターンは連続する2つのブロックにまたがることができる（例：フリップ2〜4または5〜7）。例のT H H Tでは、HHTはフリップ4で終了する。シーケンスを互いに素な3つ組に分割すると、これらの発生が見落とされ、誤った待ち時間分布が計算される。
• レースの記憶が破壊される：実際のプロセスはフリップ間で状態を保持する。特に、両方のパターンは、任意の固定された3つのフリップのブロックを占める確率がp²qと同じであるため、ブロックモデルはすべてのpに対して50対50のレースを予測するだろう。しかし、正しい答えq/(1+q)は、すべての0 < p < 1で1/2より厳密に小さい。なぜなら、パターンは非対称に重複するからである：プレフィックスHHが発生すると、HHTは確実に最初に終了するが、部分的なHTHの試み（HTの後にTが続く）はすべての進捗を無駄にする。この競争的で重複する構造は、独立ブロック推論では捉えられないものである。

1. HTH が HHT より先に現れる確率：
$P(HTH)$ を、HTH が HHT より先に現れる確率とする。列の現在の状態に基づいて、連立一次方程式を立てることができる。$E$ を、いずれかのパターンが現れるまでの期待投数とする。$E_S$ を、直前の投げが列 $S$ をなしているときに必要な追加の投数の期待値とする。ここで関心があるのは $P(HTH)$ である。
$P_S$ を、直前の投げが列 $S$ をなしているときに、HTH が HHT より先に現れる確率とする。求めたいのは $P_{\text{empty}}$ である。
状態は次のとおり：empty, H, HH, HT。
$P_{\text{empty}} = p P_H + q P_{\text{empty}}$（最初の投げが T なら、empty 状態に戻る）
$P_H = p P_{HH} + q P_{\text{empty}}$
$P_{HH} = p P_{HHH} + q P_{HT}$
$P_{HT} = p P_{HTH} + q P_{\text{empty}}$
吸収状態は HTH と HHT である。HTH が起これば、HTH が HHT より先に現れる確率は 1 である。HHT が起これば、その確率は 0 である。
$P_{HTH} = 1$
$P_{HHT} = 0$
$P_{HH} = p P_{HHH} + q P_{HT}$ より、次の投げが H なら HHH となる。関係する接尾辞は HH なので、$P_{HHH} = P_{HH}$。したがって、$P_{HH} = p P_{HH} + q P_{HT}$ であり、これは $(1-p)P_{HH} = q P_{HT}$ を意味する。よって $q P_{HH} = q P_{HT}$、したがって $P_{HH} = P_{HT}$。
これを代入すると：
$P_H = p P_{HT} + q P_{\text{empty}}$
$P_{\text{empty}} = p P_H + q P_{\text{empty}} \rightarrow p P_{\text{empty}} = p P_H \rightarrow P_{\text{empty}} = P_H$
よって、$P_{\text{empty}} = p P_{HT} + q P_{\text{empty}} \rightarrow p P_{\text{empty}} = p P_{HT} \rightarrow P_{\text{empty}} = P_{HT}$。
これは $P_{\text{empty}} = P_H = P_{HH} = P_{HT}$ を意味する。この共通の確率を $P$ とする。
すると $P = p P + q P$、すなわち $P=P$ となる。このアプローチは状態の取り方に問題があるようである。ターゲットパターンのどちらかの接頭辞になりうる最長接尾辞に基づいて状態を再定義しよう。
状態：$\emptyset$（empty）, H, HH, HT。
$P_S$ を、状態 $S$ から始めたときに HTH が勝つ確率とする。
$P_{\emptyset} = p P_H + q P_{\emptyset}$ （T なら $\emptyset$ に戻る）
$P_H = p P_{HH} + q P_{\emptyset}$ （HT なら状態 HT にいる）
$P_{HH} = p P_{HHH} + q P_{HT}$ （HHH なら接尾辞は HH なので $P_{HHH} = P_{HH}$。HHT なら負けなので $P_{HHT}=0$）
$P_{HT} = p P_{HTH} + q P_{\emptyset}$ （HTH なら勝ちなので $P_{HTH}=1$。HTT なら $\emptyset$ に戻る）
よって、$P_{HH} = p P_{HH} + q P_{HT} \rightarrow (1-p)P_{HH} = q P_{HT} \rightarrow q P_{HH} = q P_{HT} \rightarrow P_{HH} = P_{HT}$。
$P_H = p P_{HT} + q P_{\emptyset}$
$P_{\emptyset} = p P_H + q P_{\emptyset} \rightarrow p P_{\emptyset} = p P_H \rightarrow P_{\emptyset} = P_H$。
よって、$P_{\emptyset} = P_H = P_{HT} = P_{HH}$。これを $P$ とする。
$P = p P + q P$、すなわち $P=P$。これは状態定義または方程式に問題があることを示している。

より標準的なマルチンゲール法、あるいは別の状態定義を使おう。
状態を、HTH または HHT の接頭辞となる最長接尾辞として考える。
状態：$\emptyset$, H, HH, HT。
$P$ を HTH が勝つ確率とする。
$P = p P_H + q P_{\emptyset}$ （T なら $\emptyset$ に戻る）
$P_H = p P_{HH} + q P_{\emptyset}$ （HT なら状態 HT にいる）
$P_{HH} = p P_{HHH} + q P_{HHT}$ （HHT なら負け、$P_{HHT}=0$。HHH なら接尾辞は HH なので $P_{HHH}=P_{HH}$）
$P_{HT} = p P_{HTH} + q P_{HTT}$ （HTH なら勝ち、$P_{HTH}=1$。HTT なら接尾辞は T なので $\emptyset$ に戻り、$P_{HTT}=P_{\emptyset}$）
方程式は次のとおり：
$P = p P_H + q P_{\emptyset}$
$P_H = p P_{HH} + q P_{\emptyset}$
$P_{HH} = p P_{HH} + q \times 0 \rightarrow (1-p)P_{HH} = 0 \rightarrow q P_{HH} = 0$。$q \neq 0$ なので、$P_{HH} = 0$。
$P_{HT} = p \times 1 + q P_{\emptyset} = p + q P_{\emptyset}$。
$P_H$ に $P_{HH}=0$ を代入すると：$P_H = p \times 0 + q P_{\emptyset} = q P_{\emptyset}$。
これを $P$ に代入すると：$P = p (q P_{\emptyset}) + q P_{\emptyset} = pq P_{\emptyset} + q P_{\emptyset} = (pq+q) P_{\emptyset} = q(p+1) P_{\emptyset}$。これは正しくない。

https://math.stackexchange.com/questions/129670/expected-number-of-coin-tosses-to-get-a-sequence-of-heads-and-tails の方法を使おう。
$P_A$ を、パターン A（HTH）がパターン B（HHT）より先に現れる確率とする。
$A = HTH$、$B = HHT$ とする。
公式 $P_A = \frac{B:B - B:A}{A:A - A:B + B:B - B:A}$ を用いる。ここで $X:Y = \sum_{k=1}^{m} I(X_k = Y^{(k)}) 2^{k-1}$ であり、$X_k$ は $X$ の長さ $k$ の接頭辞、$Y^{(k)}$ は $Y$ の長さ $k$ の接尾辞である。$I$ は指示関数である。
$A = HTH$、$B = HHT$。
$A:A$: HTH:HTH。$k=1$: H=H（12^0=1）。$k=2$: HT=HT（12^1=2）。$k=3$: HTH=HTH（12^2=4）。$A:A = 1+2+4 = 7$。
$A:B$: HTH:HHT。$k=1$: H=H（12^0=1）。$k=2$: HT=HH（0）。$k=3$: HTH=HHT（0）。$A:B = 1$。
$B:B$: HHT:HHT。$k=1$: H=H（12^0=1）。$k=2$: HH=HH（12^1=2）。$k=3$: HHT=HHT（12^2=4）。$B:B = 1+2+4 = 7$。
$B:A$: HHT:HTH。$k=1$: H=H（12^0=1）。$k=2$: HH=TH（0）。$k=3$: HHT=HTH（0）。$B:A = 1$。
$P_{HTH} = \frac{7 - 1}{7 - 1 + 7 - 1} = \frac{6}{12} = \frac{1}{2}$。

2. 期待投数：
$E$ を、HTH または HHT のいずれかが現れるまでの期待投数とする。
パターンに対する期待待ち時間の同じ公式を使うことができる。単一パターン $A$ に対しては、期待時間は $E_A = A:A$ である。しかしここでは、2 つのパターンが競合している。
$E$ を期待投数とする。再び状態を用いることができる。
状態：$\emptyset$, H, HH, HT。
$E_S$ を、状態 $S$ から始めたときに必要な追加の投数の期待値とする。
$E_{\emptyset} = 1 + p E_H + q E_{\emptyset}$ （T なら $\emptyset$ に戻る）
$E_H = 1 + p E_{HH} + q E_{\emptyset}$ （HT なら状態 HT にいる）
$E_{HH} = 1 + p E_{HHH} + q E_{HHT}$ （HHT なら終了、$E_{HHT}=0$。HHH なら接尾辞は HH、$E_{HHH}=E_{HH}$）
$E_{HT} = 1 + p E_{HTH} + q E_{HTT}$ （HTH なら終了、$E_{HTH}=0$。HTT なら接尾辞は T なので $\emptyset$ に戻り、$E_{HTT}=E_{\emptyset}$）
方程式は次のとおり：
$E_{\emptyset} = 1 + p E_H + q E_{\emptyset} \rightarrow p E_{\emptyset} = 1 + p E_H \rightarrow E_{\emptyset} = 1/p + E_H$。
$E_H = 1 + p E_{HH} + q E_{\emptyset}$。
$E_{HH} = 1 + p E_{HH} + q \times 0 \rightarrow (1-p)E_{HH} = 1 \rightarrow q E_{HH} = 1 \rightarrow E_{HH} = 1/q$。
$E_{HT} = 1 + p \times 0 + q E_{\emptyset} = 1 + q E_{\emptyset}$。
$E_H$ に $E_{HH}=1/q$ を代入すると：$E_H = 1 + p (1/q) + q E_{\emptyset} = 1 + p/q + q E_{\emptyset}$。
これを $E_{\emptyset}$ に代入すると：$E_{\emptyset} = 1/p + (1 + p/q + q E_{\emptyset}) = 1/p + 1 + p/q + q E_{\emptyset}$。
$E_{\emptyset} (1-q) = 1/p + 1 + p/q \rightarrow p E_{\emptyset} = 1/p + 1 + p/q = (q + pq + p^2)/(pq)$。
$E_{\emptyset} = (q + pq + p^2)/(p^2 q)$。
次にこれを $E_{HT}$ に代入すると：$E_{HT} = 1 + q E_{\emptyset} = 1 + q (q + pq + p^2)/(p^2 q) = 1 + (q + pq + p^2)/p^2 = (p^2 + q + pq + p^2)/(p^2) = (2p^2 + pq + q)/p^2$。
これは過度に複雑に見える。パターン A または B が現れるまでの期待時間の公式を使おう。
$E = \frac{p(A:A) + q(B:B) - (A \text{ overlaps with } B)}{p+q}$ は正しくない。
パターン A または B が現れるまでの期待投数は次で与えられる：
$E = \frac{A:A + B:B - (A \text{ overlaps with } B)}{A:B + B:A}$ これも正しくない。

公式 $E = \frac{N_A + N_B}{P(A \text{ or } B \text{ occurs at a given step})}$ を使おう。これは役に立たない。

Guibas と Odlyzko の公式、あるいは期待値に対するマルチンゲール法を使う。
$E$ を期待投数とする。
HHH または TTT に対しては、$E = \frac{1}{p^3} + \frac{1}{p^2 q} + \frac{1}{p q^2} + \frac{1}{q^3}$。
HTH または HHT に対して：
$E$ を期待投数とする。
HHH に対しては $E = \frac{1}{p} + \frac{1}{p^2} + \frac{1}{p^3}$。
もう一度、慎重に状態法を使おう。
状態：$\emptyset$, H, HH, HT。
$E_{\emptyset} = 1 + p E_H + q E_{\emptyset} \rightarrow p E_{\emptyset} = 1 + p E_H \rightarrow E_{\emptyset} = 1/p + E_H$。
$E_H = 1 + p E_{HH} + q E_{\emptyset}$。
$E_{HH} = 1 + p E_{HH} + q \times 0 \rightarrow q E_{HH} = 1 \rightarrow E_{HH} = 1/q$。
$E_{HT} = 1 + p \times 0 + q E_{\emptyset} = 1 + q E_{\emptyset}$。
$E_{HH} = 1/q$ を $E_H$ に代入すると：$E_H = 1 + p(1/q) + q E_{\emptyset} = 1 + p/q + q E_{\emptyset}$。
これを $E_{\emptyset}$ に代入すると：$E_{\emptyset} = 1/p + (1 + p/q + q E_{\emptyset}) = 1/p + 1 + p/q + q E_{\emptyset}$。
$E_{\emptyset} (1-q) = 1/p + 1 + p/q \rightarrow p E_{\emptyset} = 1/p + 1 + p/q = (q + pq + p^2)/(pq)$。
$E_{\emptyset} = (q + pq + p^2)/(p^2 q)$。
これが HTH または HHT が現れるまでの期待投数である。
$E = \frac{q + pq + p^2}{p^2 q} = \frac{1-p + p(1-p) + p^2}{p^2 (1-p)} = \frac{1-p + p-p^2 + p^2}{p^2(1-p)} = \frac{1}{p^2(1-p)}$。

状態と遷移を再評価しよう。
状態：$\emptyset$, H, HH, HT。
$E_0$（開始）：$1 + p E_1 + q E_0$（T なら開始に戻る）
$E_1$（H）：$1 + p E_2 + q E_0$（HT なら状態 HT）
$E_2$（HH）：$1 + p E_2 + q \times 0$（HHT なら停止）
$E_3$（HT）：$1 + p \times 0 + q E_0$（HTH なら停止）
$E_2$ から：$(1-p)E_2 = 1 \rightarrow q E_2 = 1 \rightarrow E_2 = 1/q$。
$E_0$ から：$p E_0 = 1 + p E_1 \rightarrow E_0 = 1/p + E_1$。
$E_3$ から：$E_3 = 1 + q E_0$。
$E_2=1/q$ を $E_1$ に代入すると：$E_1 = 1 + p(1/q) + q E_0 = 1 + p/q + q E_0$。
これを $E_0$ に代入すると：$E_0 = 1/p + (1 + p/q + q E_0) = 1/p + 1 + p/q + q E_0$。
$E_0 (1-q) = 1/p + 1 + p/q \rightarrow p E_0 = 1/p + 1 + p/q = (q + pq + p^2)/(pq)$。
$E_0 = (q + pq + p^2)/(p^2 q)$。
$E_0 = \frac{1-p + p(1-p) + p^2}{p^2(1-p)} = \frac{1-p+p-p^2+p^2}{p^2(1-p)} = \frac{1}{p^2(1-p)}$。

$E_{HT}$ の計算を確認しよう。
$E_{HT} = 1 + q E_0 = 1 + q rac{q+pq+p^2}{p^2 q} = 1 + rac{q+pq+p^2}{p^2} = rac{p^2 + q+pq+p^2}{p^2} = rac{2p^2+pq+q}{p^2}$。
これは状態 HT にいるときの期待投数である。求めたいのは $E_0$ である。
したがって、期待投数は $E_0 = \frac{1}{p^2(1-p)}$ である。

例で確認しよう。$p=1/2$、$q=1/2$ のとき、$E_0 = \frac{1}{(1/2)^2 (1/2)} = \frac{1}{1/8} = 8$。
これは HTH または HHT に関する既知の結果と一致する。

3. 重ならないブロックを独立試行として扱うのがなぜ誤りなのかの説明：
このアプローチが不適切なのは、パターン照合の文脈ではコイン投げが独立試行ではないからである。1 回の投げの結果は、その後の投げでパターンが形成される確率に影響を与える。具体的には、ある 3 回投げの候補ブロックの終わりが、次の候補ブロックの始まりと重なる可能性がある。たとえば、列が HHT であれば、これは目標パターンの一つである。もし次の重ならないブロックを 4 回目の投げから考えるなら、最初の 3 回の投げがすでに結果を決定していたという事実を無視することになる。さらに重要なのは、HTH と HHT というパターンは、それ自身または互いに重なりうるため、独立性が成り立たないことである。たとえば列が HTHHT なら、最初に HTH が形成され、その直後に HHT パターンが始まる。これらを独立試行として扱うと、そのような重なりや、列生成過程に内在する記憶性を考慮できなくなる。目標パターンに到達する確率を決めるには、列の状態（つまり列の接尾辞）が重要である。