等 HH 与等 HT
题
一枚公平硬币反复抛，首次出现连续两次正面（HH）平均要抛几次？首次出现"正面后接反面"（HT）呢？
一句话
HH 要 6 次，HT 只要 4 次——两种图案在任一位置出现的概率都是 \(1/4\)，差别全在自重叠：HH 失败时会把手里的 H 一起丢掉，HT 失败时 H 还留着。
关键技巧
一、状态递推。 状态取"当前已匹配的前缀长度"，对每个状态列一条"再抛一次"的方程。
HH：设 \(e_0\)、\(e_1\) 分别是从零开始、手握一个 H 时的剩余期望。
解得 \(e_0 = 6\)。关键在第二式——手握 H 抛出 T，退回起点。
HT：
手握 H 再抛出 H，原地不动——还握着一个 H。于是 \(e_1 = 2\)，\(e_0 = 4\)。
二、赌徒鞅（ABRACADABRA 法）。 每抛一次之前来一个新赌徒，带 1 元入场，押"下一次是图案的第 1 个字母"，赔率公平（押中翻倍）；押中就把全部身家押图案的下一个字母，押错出局。赌场是公平的，所以到停时 \(\tau\)（图案首次完成）为止：
停时那一刻还活着的，只有"入场点恰好让已开出的尾巴等于图案前缀"的赌徒：
- HH：第 \(\tau-1\) 次入场的赌徒押中两次，身家 4；第 \(\tau\) 次入场的押中一次，身家 2。\(E[\tau] = 4 + 2 = 6\)。
- HT：第 \(\tau-1\) 次入场的身家 4；第 \(\tau\) 次入场的押 H 开出 T，出局。\(E[\tau] = 4\)。
一般公式：长度 \(n\) 的图案、字母表大小 \(m\)，
猴子打出 ABRACADABRA：前后缀重合的长度是 1（A）、4（ABRA）、11（全体），\(E[\tau] = 26^{11} + 26^4 + 26\)。
解
两种方法都给：
直觉版——长期看 HH 和 HT 出现的频率一样，都是每个位置 \(1/4\)。但 HH 会扎堆（HHH 里有两个重叠的 HH），同样的频率挤成一团团，团与团之间的空档就更长，首次等待自然更久。同频率 + 更扎堆 = 更长的首次等待。
延伸
- \(k\) 连正：全正图案每个长度都自重叠，\(E = 2 + 4 + \cdots + 2^k = 2^{k+1} - 2\)。\(k=6\) 是 126——正是 100 次抛硬币的最长连正 里拿来对照的那个数。
- 长度 3 的图案：HHH 14，HTH 10，HHT、HTT、THH、TTH 都是 8。自重叠越多等得越久，HTH 因为首尾都是 H 比 HHT 多等 2 次。
- 比谁先出现 ≠ 比谁期望短：HH 与 HT 同场比赛，谁先出现各 \(1/2\)——第一个 H 出现后下一抛直接定胜负。期望 6 对 4，胜率却是五五开。
-
Penney 游戏的非传递性：甲先选一个长度 3 的图案，乙后选，先出现者胜。乙永远有优势——对甲的 \(a_1a_2a_3\)，乙选 \(\bar a_2 a_1 a_2\)（\(\bar a_2\) 为 \(a_2\) 翻面）。于是形成一个环：
\[ \text{HHT} \xleftarrow{3/4} \text{THH} \xleftarrow{2/3} \text{TTH} \xleftarrow{3/4} \text{HTT} \xleftarrow{2/3} \text{HHT} \]箭头读作"被……击败，胜率"。没有最强的图案，像石头剪刀布。胜率用 Conway 的 leading number 算：\(P(B \text{ 先于 } A) : P(A \text{ 先于 } B) = (A{\cdot}A - A{\cdot}B) : (B{\cdot}B - B{\cdot}A)\)，其中 \(X{\cdot}Y = \sum_k 2^{k-1}[\,X \text{ 的长 } k \text{ 后缀} = Y \text{ 的长 } k \text{ 前缀}\,]\)。 - 常见错误：以为"HH 和 HT 都是 1/4 的事件，所以等待都是 4"。每个位置出现的概率相同，只决定长期频率；首次等待还取决于相邻位置的相关性。
数值验证
状态方程精确解、鞅公式、Penney 胜率、蒙特卡洛四路对照：
from fractions import Fraction as F
import itertools, random
def wait(pat, m=2):
"""Conway / 鞅公式：前缀 = 后缀的每个长度 k 贡献 m^k。"""
return sum(m ** k for k in range(1, len(pat) + 1) if pat[:k] == pat[-k:])
def wait_chain(pat):
"""精确解：状态 = 已匹配前缀长度，e[i] = 1 + (e[抛 H 后] + e[抛 T 后]) / 2，高斯消元。"""
n = len(pat)
def nxt(i, c):
s = pat[:i] + c
return max(k for k in range(min(len(s), n) + 1) if s[len(s) - k:] == pat[:k])
A = [[F(0)] * (n + 1) for _ in range(n)]
for i in range(n):
A[i][i] += 1; A[i][n] = F(1)
for c in "HT":
j = nxt(i, c)
if j < n: A[i][j] -= F(1, 2)
for c in range(n):
p = next(r for r in range(c, n) if A[r][c] != 0)
A[c], A[p] = A[p], A[c]
for r in range(n):
if r != c and A[r][c] != 0:
f = A[r][c] / A[c][c]
A[r] = [x - f * y for x, y in zip(A[r], A[c])]
return A[0][n] / A[0][0]
for p in ["HH", "HT", "HHH", "HHT", "HTH"]:
print(p, wait(p), wait_chain(p))
# HH 6 6 / HT 4 4 / HHH 14 14 / HHT 8 8 / HTH 10 10
print(wait("ABRACADABRA", 26) == 26**11 + 26**4 + 26) # True
def p_first(a, b):
"""Conway leading number：P(b 先于 a 出现)。"""
L = lambda x, y: sum(2 ** (len(x) - k) for k in range(len(x)) if x[k:] == y[:len(x) - k])
u, v = L(a, a) - L(a, b), L(b, b) - L(b, a)
return F(u, u + v)
print(p_first("HH", "HT")) # 1/2
for a in ["HHT", "THH", "TTH", "HTT"]:
b = max((x for x in map("".join, itertools.product("HT", repeat=3)) if x != a),
key=lambda x: p_first(a, x))
print(a, "<-", b, p_first(a, b))
# HHT <- THH 3/4 / THH <- TTH 2/3 / TTH <- HTT 3/4 / HTT <- HHT 2/3
random.seed(0)
def sim_wait(pat, T=200000):
tot = 0
for _ in range(T):
s, n = "", 0
while not s.endswith(pat):
s = (s + random.choice("HT"))[-len(pat):]; n += 1
tot += n
return tot / T
print(sim_wait("HH"), sim_wait("HT")) # 5.985285 3.993925