把转移表里的箭头换成数字：从晴到阴是 0.2。一张矩阵，每行加起来是 1。其余什么都没改 —— 这就是马尔可夫链。 它只记得上一步，前面所有历史全扔掉。 这个假设很粗暴， 但换来一件惊人的事：长期行为可以用矩阵直接算出来，不用跑模拟。这一节既算这个， 也看它什么时候算不出来。
上一节的自动机，下一个状态是确定的。这一节把箭头变成概率，骨架一个字没动。 这个骨架后面会反复出现：第 6 章的隐马尔可夫模型、第 11 章的语言模型，都是它加了几样东西。 先把这一个吃透，后面那几个都是变体。
一、把箭头换成数字
上一节的转移表长这样：(晴, 阴) → 阴。
马尔可夫模型把它换成：从晴到阴的概率是 0.2。整张表变成一个矩阵，
第 i 行第 j 列就是从 i 到 j 的概率。
| 今天＼明天 | 晴 | 阴 | 雨 |
|---|---|---|---|
| 晴 | 0.70 | 0.20 | 0.10 |
| 阴 | 0.30 | 0.50 | 0.20 |
| 雨 | 0.20 | 0.30 | 0.50 |
| 每行加起来必须等于 1 —— 明天总得有个天气。这个约束叫「随机矩阵」，它是整节所有结论的前提。 | |||
| 「马尔可夫」这三个字说的是一个假设，不是一条定理： |
P(明天 | 今天, 前天, 大前天, …) = P(明天 | 今天)
等号左边是「知道全部历史时的判断」，右边是「只知道今天时的判断」。 这句话的意思是：一旦知道今天，前面那些天就没有额外信息了。 这个假设在物理叫「无后效性」。 它显然是假的 —— 连着下三天雨，第四天下雨的概率跟刚晴一天是不一样的。 但它近似得还不错，而且它把「要知道多少东西」从一个无限长的历史压缩成了一个状态。 要更准就得加阶数：二阶看前两天。 代价是状态数按阶数指数涨：三个天气到二阶就是 9 个组合状态，到三阶 27 个。下一节末尾会看到， 这个指数就是语言模型的死穴。
二、走久了会停在一个分布上
Demo 第二段从「今天是晴」出发，一天一天乘矩阵：
| 天数 | 晴 | 阴 | 雨 |
|---|---|---|---|
| 1 | 0.7000 | 0.2000 | 0.1000 |
| 3 | 0.5120 | 0.2970 | 0.1910 |
| 10 | 0.4636 | 0.3170 | 0.2194 |
| 40 | 0.4634 | 0.3171 | 0.2195 |
| 第 40 天到了 0.4634／0.3171／0.2195。 | |||
| 再走一天，差 9.99e-15 —— 这个数已经是浮点数的噪声了，等于不动。 | |||
| 这个分布叫平稳分布，记作 π，定义只有一行： | |||
πP = π。求解它就是求矩阵里特征值 1 的那个左特征向量。 |
|||
| 这是一组线性方程，不用模拟，直接解。 | |||
| 更关键的是它跟起点无关。Demo 从晴、阴、雨三个起点各走 100 步，三行数字一模一样。 | |||
| 所以「长期看晴天占 46%、雨天占 22%」这句话，是对这个矩阵说的，不是对某一天的天气说的。 | |||
| 这个性质是马尔可夫链最有用的地方： | |||
| 你不需要跑十万天去数，解一个三元一次方程组就得到了。物理里的统计力学、排队论里的队伍长度、 | |||
| 搜索引擎的网页排名，用的都是这一步。 |
三、要走多少步才算是「到了」
「长期」到底是多长？ Demo 第三段量了：达到「跟平稳分布差小于 0.1」要 2 到 3 步，小于 0.01 要 5 到 6 步， 小于 0.001 要 8 到 9 步。 这个步数叫混合时间。它是一个很实际的概念： 模拟前面的那些步，结果是被起点污染的，必须扔掉。第 6 章讲 MCMC 抽样时会再见识到它 —— 那里的「预热期」就是混合时间。 混合时间的长短跟矩阵有关，跟起点几乎无关。这张天气表十几步就混匀了； 换一张对角线上全是 0.999 的表（每天几乎都在原地），可能要走几千步。 直觉上说得通：转移越粘，越难忘掉出身。
四、不是每张表都会停下来
Demo 第四段摆了三张有毛病的表：
| 表 | 现象 | 病在哪 |
|---|---|---|
| 来回换 | 奇偶步各占一半，永远在跳 | 有周期 |
| 原地不动 | 进去就不出来 | 不混合 |
| 一个陷坑 | 都掉进第一个状态 | 退化了 |
| 第一张表——两个状态互相跳、概率都是 1——是最值得琢磨的。奇数天一定在状态 1，偶数天一定在状态 0， | ||
| 任何时刻的分布都在两个极端之间跳，没有极限。可它偏偏有平稳分布 —— | ||
解 πP = π 得到 (0.5, 0.5)。 |
||
| 这就是一个容易混的点：平稳分布存在，不等于极限分布存在。对这张表，(0.5, 0.5) 是「长期平均」， | ||
| 不是「某一天的概率」。 | ||
| 区别在于「时间平均」和「空间平均」在这里对不上，而这种对不上正是遍历性失效的样子。 | ||
| 第二张表是单位矩阵：每个初始状态自己就是一个平稳分布，解不唯一。第三张表有个吸收态， | ||
| 从状态 0 出发就出不来，长期分布退化成一个点 (1, 0)。 | ||
| 收敛的标准条件是两条：不可约（从任何状态都能走到任何状态）、非周期（不会按固定节拍循环）。 | ||
| 三条病对应三种破法：来回换坏在周期性，陷坑坏在不可约，单位矩阵两条都坏。 |
五、用它生成文字
Demo 第五段把语料换成一段 204 字的中文，不切词，按单字建表。 一阶：键是「上一个字」，值是后面跟过的字。 一阶建出 125 个键，平均每个键后面跟 1.62 个字。 生成 300 字，其中三字组合在原句里出现过的占 69.6%。生成的样子：
现不能认出实验室里能这些规则系统在一次出现是在一走出实验室里表现是
这个功能认出人工智能模仿人的判断。这条路。后仍然是给机器看例子
两个字看着都认识，连起来常常不通。因为它选下一个字时只查「上一个字是什么」， 根本不知道这句话在讲什么。 二阶记的是「上两个字」，189 个键，平均每个键后面只跟 1.07 个字。 三字组合命中率 100% —— 因为它的每个输出片段都是原文里原样出现过的。 生成的样子也基本是原文的拼贴：
规则而是给机器学会思考。他们相信只要把推理过程写成规则而是给机器就
能模仿人的判断。二十年直到算力足够多才真正跑起来。今天你手机里
阶数越高越像原文，新东西越少。到某一阶，模型就退化成「把训练集抄一遍」。 这就是 n-gram 语言模型，2010 年代之前机器翻译和语音识别的主力。 它的死穴在状态数：词表五万个词，三阶模型的格子数是五万的立方， 1.25 乘 10 的 14 次方 —— 存不下，更别说每一项都要有统计。 出路只有一条：不再枚举「前文的每一种可能」，而是把前文压成一个固定长度的向量。 那就是神经网络语言模型，第 11 章的内容。但骨架没变：还是在算「给定前文，下一个词是什么概率」。
六、动手 Demo：一张天气表，和一台只会说半句话的机器
这段代码分两半：前一半乘矩阵，后一半数汉字。
前一半只有一个循环 —— v = v.dot(P) 反复做 40 次，就是「一天一天过下去」。
平稳分布是乘法自己走出来的，不是解方程解出来的，两者结果一样。
后一半把一段 204 字的文字建成「上一个字 → 后面跟过哪些字」的表，再按表随机往下抽。
一阶和二阶用的是同一个函数，只有 order 不一样。
# 行是今天，列是明天，每行加起来是 1
P = np.array([[0.70, 0.20, 0.10],
[0.30, 0.50, 0.20],
[0.20, 0.30, 0.50]])
# 幂迭代：从「今天是晴」出发，一天一天乘过去
v = np.array([1.0, 0.0, 0.0])
for t in range(1, 41):
v = v.dot(P)
print(v) # 第 40 天：0.4634 0.3171 0.2195
print(v.dot(P)) # 再走一天，差 9.99e-15，不动了
# 字符级马尔可夫：键是「上一个字」（或两个字），值是后面跟过的字
def build(order):
tab = {}
for i in range(len(CORPUS) - order):
key = CORPUS[i:i + order]
nxt = CORPUS[i + order]
tab.setdefault(key, []).append(nxt)
return tab
def gen(tab, order, n, seed):
rg = np.random.default_rng(seed)
keys = sorted(k for k in tab if len(tab[k]) >= 2)
cur = keys[int(rg.integers(0, len(keys)))]
out = cur
for _ in range(n):
cand = tab.get(cur)
if not cand:
break
nxt = cand[int(rg.integers(0, len(cand)))]
cur = (cur + nxt)[-order:] if order > 1 else nxt
out += nxt
return out
实跑输出：
--------------------------------------------------------------------
只记得上一步
--------------------------------------------------------------------
==============================================================
[1] 天气的转移矩阵
看了一年的天气，统计出这样一张表：
今天\明天 晴 阴 雨
----------------------------------------
晴 0.70 0.20 0.10
阴 0.30 0.50 0.20
雨 0.20 0.30 0.50
每行加起来：1.0 1.0 1.0
一定是 1 —— 明天总得有个天气。
这张表只说一件事：今天是什么，明天是什么的概率各是多少。
至于前天、大前天是什么，表里没有这一栏。
这就是「马尔可夫」的意思：过去全扔了，只留现在。
[2] 一直按这张表走下去，最后各占多少
步数 晴 阴 雨
--------------------------------------------
1 0.7000 0.2000 0.1000
2 0.5700 0.2700 0.1600
3 0.5120 0.2970 0.1910
5 0.4737 0.3131 0.2133
10 0.4636 0.3170 0.2194
20 0.4634 0.3171 0.2195
40 0.4634 0.3171 0.2195
走到第 40 步，分布停在 0.4634／0.3171／0.2195
再走一步： 0.4634／0.3171／0.2195
最大差 9.99e-15 —— 不动了。这个分布叫平稳分布。
它跟从哪一天开始没关系：
从「晴」出发走 100 步：0.4634／0.3171／0.2195
从「阴」出发走 100 步：0.4634／0.3171／0.2195
从「雨」出发走 100 步：0.4634／0.3171／0.2195
三条路走到同一个地方。按平稳分布算，长期看晴天占 46%，
雨天占 22%。这个比例不用模拟，解矩阵就能算出来。
[3] 要走多少步才算是「到了」
从每个起点出发，每步量一次跟平稳分布的最大差：
起点 差小于 0.1 差小于 0.01 差小于 0.001
------------------------------------------------------
晴 第 3 步 第 6 步 第 9 步
阴 第 2 步 第 5 步 第 8 步
雨 第 3 步 第 6 步 第 9 步
十几步就差不多了。这个步数叫混合时间，实际系统里它决定了
「跑多久的模拟才算数」—— 前面那些步的结果要扔掉。
[4] 不是每张表都会停下来
两状态来回换：
表 [0.0 1.0] [1.0 0.0]
从状态 0 走 6 步：0.00/1.00 1.00/0.00 0.00/1.00 1.00/0.00 0.00/1.00 1.00/0.00
从状态 1 走 6 步：1.00/0.00 0.00/1.00 1.00/0.00 0.00/1.00 1.00/0.00 0.00/1.00
原地不动：
表 [1.0 0.0] [0.0 1.0]
从状态 0 走 6 步：1.00/0.00 1.00/0.00 1.00/0.00 1.00/0.00 1.00/0.00 1.00/0.00
从状态 1 走 6 步：0.00/1.00 0.00/1.00 0.00/1.00 0.00/1.00 0.00/1.00 0.00/1.00
一个陷坑：
表 [1.0 0.0] [0.3 0.7]
从状态 0 走 6 步：1.00/0.00 1.00/0.00 1.00/0.00 1.00/0.00 1.00/0.00 1.00/0.00
从状态 1 走 6 步：0.30/0.70 0.51/0.49 0.66/0.34 0.76/0.24 0.83/0.17 0.88/0.12
第一张表在两列之间来回跳，永远不停；第二张表根本不动；
第三张表不管从哪出发都掉进第一个状态，进去了出不来。
所以「有转移矩阵」不等于「有平稳分布」，更不等于「模拟会有意义」。
要它收敛，得满足「从任何状态都能走到任何状态」这类条件。
跳来跳去的那张表，问题在于它有个固定的节拍 —— 奇偶步各占一半，
谈不上「稳定在某个比例上」。
[5] 拿它生成文字：只记上一个字
语料是一段 204 个字的说明文字，不切词，就按单字建表。
一阶：记「上一个字是 X，下一个字最可能是谁」
1 阶：表里有 125 个键，平均每个键后面跟 1.62 个字
生成 300 字，其中三字组合在原文里出现过的占 69.6%
生成的样子：
现不能认出实验室里能这些规则系统在一次出现是在一走出实验室里表现是这个功能
认出人工智能模仿人的判断。这条路。后仍然是给机器看例子让机器就是在实验室就
是这条路不再教机器看例子让机器规则系统在实验室里表现不能不能这些规则系统在
2 阶：表里有 189 个键，平均每个键后面跟 1.07 个字
生成 300 字，其中三字组合在原文里出现过的占 100.0%
生成的样子：
规则而是给机器学会思考。他们相信只要把推理过程写成规则而是给机器就能模仿人
的判断。二十年直到算力足够多才真正跑起来。今天你手机里能认出人脸的那个功能
背后仍然是这条路。
一阶生成的句子，两个字看着都认识，连起来常常不通 ——
因为它只知道上一个字，不知道前面说过什么。
二阶开始像人话了，代价是它更愿意照抄原文。
阶数往上加，模型记的越多，输出越接近原文，新东西越少。
这就是为什么后来的语言模型不再只记几个字，
而是把整句话压成一大堆数字，再算下一个字该是什么。
第一段的矩阵里最该注意的是每行和为 1。这不是格式要求，是「明天一定有个天气」这句话的数学化。 行和不是 1 的矩阵叫「亚随机矩阵」，那是另一套理论（有质量流失），本书不涉及。 第二段那个 9.99e-15 是浮点误差，不是真的收敛到 0。 判断「到了」的实用办法是看两次迭代的差小于某个阈值，而不是等它变成 0。 这也是所有迭代算法的通病：永远差一点点。 第三段那三列数字说明「收敛」是个程度问题。差小于 0.1 只要 2 到 3 步， 要小到 0.001 就得 8 到 9 步。报告「收敛了」必须带上精度，不然这句话没有信息量。 第四段三张表要分开看。「来回换」那张表的平稳分布是 (0.5, 0.5)， 可它永远在两个极端之间跳 —— 平稳分布存在，极限分布不存在，这两件事不一样。这个区别是很多教材一笔带过、读者一头雾水的地方。 第五段生成的两段文字，对比着读最有效。一阶那段里「实验室里」出现了三次， 「这些规则系统」出现了两次 —— 因为这几个字在原文里后面跟的字比较单一，模型就一直往回抽。二阶那段则整句整句地照搬。 最后那句关于 1.25 乘 10 的 14 次方，是这一节真正的落点。马尔可夫模型本身没错， 错在「用枚举的方式表示前文」。 换掉这一处，模型就从「查表」变成了「算向量」，也就从这一章走到了第 11 章。
30 秒实验
- 把
P的第一行改成[0.50, 0.30, 0.20]，重跑第二段。 平稳分布应该往「晴少一点、阴雨多一点」的方向挪 —— 因为从晴出发更容易走掉了。 - 把第四段那张「来回换」的表改成
[[0.9, 0.1], [0.1, 0.9]]。 周期被打破了，这次应该收敛到 (0.5, 0.5) 并且真的停下来 —— 同样是 0.5， 一个是极限一个是平均，这下能看出区别。 - 把语料换成你自己写的一段 200 字，跑
order=3。 三字组合命中率应该还是 100%（四阶才可能造出原文没有的四字片段），但生成的句子会更像原文， 几乎就是摘抄。
常见误区
- 以为马尔可夫链「记住」了历史。它只记一步，而且这一步是假设，不是事实。 天气显然不满足这个假设，但近似还能用 —— 工程上关心的是「够不够用」，不是「对不对」。
- 以为平稳分布就是「最终会停在那个状态」。它是「长期各状态出现的比例」， 不是「某一天的结果」。 三态天气表里，任何一天都只可能是一种天气，0.4634 这个数是十万天的平均，不是某一天的概率。
- 以为有转移矩阵就一定收敛。三张病表摆在那里：周期、不混合、吸收态。 「不可约 + 非周期」这两条不是装饰，是收敛的前提。
- 以为阶数越高模型越好。阶数每加一，状态数乘一个词表大小。 语料撑不住的时候，高阶模型的绝大部分格子是空的，抽到空表就卡住 —— 这叫数据稀疏， n-gram 时代最头疼的问题。
自测三问（点开对答案）
1. 为什么平稳分布可以「解出来」，不必跑模拟？ —— 因为 `πP = π` 是一组线性方程。 **只要矩阵满足不可约且非周期，这个方程有唯一解，求它就是找特征值 1 的左特征向量。** 模拟是把答案逼近出来，解方程是直接算出来 —— **前者要跑很久，后者一次算完。** 2. 「来回换」那张表为什么不收敛，可它又有平稳分布？ —— 因为它有周期 2：奇数步必在状态 1，偶数步必在状态 0。 **任何时刻的分布都在两个极端之间跳，不存在极限分布。** 而它的平稳分布 (0.5, 0.5) 是「长期时间平均」—— **平稳分布存在，不等于极限分布存在，这两件事在周期链上会分开。** 3. 一阶马尔可夫生成的句子为什么不通？ —— 因为**它选下一个字时只查「上一个字是什么」**，两步以前的信息全扔了， 所以不知道这句话在讲什么。 **局部搭配都对，整体语义全散。**二阶会好一些， 因为它至少记住了一个二字片段 —— **但代价是键的数量翻了十几倍，而且越往上越接近照抄。**状态、转移、概率，三样都齐了。 下一节把它们装进一个具体的东西里：一个在房间里转、会擦地、会自己回去充电的机器人。
- ☐ （本节完，下一节 3.4 状态驱动智能体）