字符串匹配的 Markov 链
题目
A、B 两人玩抛硬币游戏，他们连续掷一枚均匀的硬币，每次记录硬币的朝向，正面记录为 1，反面记录为 0，构成一串 01 序列。若序列先出现连续的 1001001，则 A 赢；若序列先出现连续的 0010010，则 B 赢。求 A、B 各自的胜率。
解法
高中解法（巧解）
Markov 链解法
读入一堆字符，要求和两个给定字符串匹配，由此可以联想到 AC 自动机
首先构造字符串 1001001 和 0010010 的 AC 自动机的状态图，得到：
上面可以视为一个 Markov 链的状态转移图，每个节点表示当前匹配到字符串的什么位置，而 7 和 14 是自动机的接受节点，对应 Markov 链的吸收态。由于读入的字符是 0 和 1 的概率是相等的，所以除了代表吸收态 7、14 节点，每个节点沿两条出边转移的概率是相等的。
因此，可以构造出这一 Markov 链的转移矩阵：
A = \left(
\begin{array}{cccccccccccccc}
\frac{1}{2} & \frac{1}{2} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
\frac{1}{2} & 0 & \frac{1}{2} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & \frac{1}{2} & 0 & 0 & 0 & 0 & \frac{1}{2} & 0 & 0 & 0 & 0 & 0 \\
\frac{1}{2} & 0 & 0 & 0 & \frac{1}{2} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
\frac{1}{2} & 0 & 0 & 0 & 0 & \frac{1}{2} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & \frac{1}{2} & 0 & \frac{1}{2} & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
\frac{1}{2} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \frac{1}{2} & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \frac{1}{2} & \frac{1}{2} & 0 & 0 & 0 & 0 \\
\frac{1}{2} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \frac{1}{2} & 0 & 0 & 0 \\
\frac{1}{2} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \frac{1}{2} & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \frac{1}{2} & 0 & 0 & 0 & \frac{1}{2} & 0 \\
\frac{1}{2} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \frac{1}{2} \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\
\end{array}
\right)
由于有两个吸收态，极限分布与初始分布有关。
这里初始分布为 p_0 = \displaystyle \left(\frac{1}{2},0,0,0,0,0,0,\frac{1}{2},0,0,0,0,0,0\right)，其极限分布为
p_\infty = \lim_{n \to \infty} p_0 A^n.
由于该 Markov 链只有两个吸收态，其极限分布必定收敛于这两个状态，可以设
p_\infty = \left(0,0,0,0,0,0,P_1,0,0,0,0,0,0,P_2\right).
这里 P_1, P_2 就是 A 和 B 的胜率。
求出 Ax = x 的基础解系，得到
X = \left(
\begin{array}{cc}
-1 & 2 \\
-1 & 2 \\
-1 & 2 \\
-\frac{8}{7} & \frac{15}{7} \\
-\frac{9}{7} & \frac{16}{7} \\
-\frac{11}{7} & \frac{18}{7} \\
-\frac{16}{7} & \frac{23}{7} \\
-\frac{13}{14} & \frac{27}{14} \\
-\frac{6}{7} & \frac{13}{7} \\
-\frac{6}{7} & \frac{13}{7} \\
-\frac{5}{7} & \frac{12}{7} \\
-\frac{3}{7} & \frac{10}{7} \\
0 & 1 \\
1 & 0 \\
\end{array}
\right).
则 X 中各列均为 A 的不动点，有 A^n X = X，所以 p_0 A^n X = p_0 X。又有
\lim_{n \to \infty} p_0 A^n X = p_\infty X.
于是得到 p_0 X = p_{\infty} X，也就是
\left(-\frac{27}{28},\frac{55}{28}\right) = \left(P_2-\frac{16}{7}P_1,\frac{23}{7}P_1\right),
解得
P_1 = \frac{55}{92},P_2 = \frac{37}{92}.
于是 A 和 B 的胜率之比为 55:37。
扩展
BEYOND THE ARTICLE
读完了，有什么想法？
阅读已保存的问答示例，并循着引用回到原文。
— 本文完 — 返回文章列表