马尔可夫链基础
马尔可夫链只要求一件事：下一步的概率只看现在在哪儿，不看是怎么来的。这个假设弱到几乎不像假设，却足以让"长期会怎样"变成一道线性代数题。这一页把一条三状态的链摆在你面前——调转移概率、按播放、看小球乱跑，同时看着它的长期占比一点点落到那个用公式算出来的稳态上。
LAB 01
转移矩阵与状态图
改转移概率，看小球在三个状态之间怎么跑，长期比例落到哪儿
问题
天气、机器的运行状态、用户在几个页面之间的跳转——这些系统的共同点是：下一步只取决于现在在哪儿，和怎么走到这儿的没关系。这一台先把这个假设变成一张可以拨动的转移矩阵，看小球在三个状态之间实际怎么跑。
模型
马尔可夫性：P(Xn+1=j | Xn=i, …, X0) = P(Xn+1=j | Xn=i) = pij。把所有 pij 排成矩阵 P，每一行加起来是 1。
P = [pij]， Σj pij = 1， pij ≥ 0
pij：这一步在状态 i、下一步到状态 j 的概率。这样的矩阵叫随机矩阵。理论稳态 π—
模拟出来的长期占比—
已经走了多少步—
1/(1−p) 归一化后—
按播放，让它跑几千步，然后把两排柱子叠着看：模拟占比会一根一根压到理论稳态上。这就是马尔可夫链最核心的一句话——不管从哪个状态出发，长期来看待在每个状态的时间比例是固定的，而这个比例只由转移概率决定。再看最后一行读数。这条链里每个状态"留在原地"的概率是 p，剩下的概率在另外两个状态上对半分。在这种对称的分法下，稳态分布恰好正比于 1/(1−p)——你把三个滑杆拖成任何组合，最后两行读数都会一模一样。比如 70%/50%/30% 给出 0.493 / 0.296 / 0.211，90%/50%/10% 给出 0.763 / 0.153 / 0.085。1/(1−p) 有一个很好懂的意思：它就是一次进入这个状态之后，平均会连续待多少步。晴天维持概率 90%，一旦转晴平均就连晴 10 天；雨天维持概率 10%，平均只下 1.1 天。待得久的状态占的时间自然多——稳态分布说到底就是"平均停留时长"的归一化。
LAB 02
n 步转移
矩阵自乘：不管从哪个状态出发，几步以后每一行都长得一样
问题
如果今天是晴天，一周以后下雨的概率是多少？这不是查一次表就能答的——要把一步的概率"接力"很多次。问题是：接力这件事有没有一个干净的写法，以及接力很多次之后会发生什么。
模型
n 步转移概率就是矩阵的 n 次幂，这是 Chapman–Kolmogorov 方程的矩阵写法。
P(Xn=j | X0=i) = (Pn)ij， Pm+n = Pm Pn
n 越大，Pn 的每一行越接近同一个向量——出发点被"忘掉"了。三行之间的最大差—
|λ₂|—
|λ₂|ⁿ 的预测—
收敛了吗—
把 n 一格一格往上推，盯着三行数字：它们会越来越像，最后完全一样。P 的第 i 行第 j 列是"从 i 出发走 n 步到 j"的概率。三行变成同一行，意思就是走了足够多步之后，你在哪儿已经和从哪儿出发无关了——这正是"遗忘初始条件"。重点在后两行读数：行间最大差与 |λ₂|ⁿ 几乎一致。普通链的 |λ₂|=0.473，n=1 时差 0.500、n=5 时 0.026、n=10 时 0.0006；黏住不动的链 |λ₂|=0.957，n=40 了还差 0.185。收敛速度是指数的，底数就是第二大特征值的模。这个数在应用里很重要：PageRank 要迭代多少轮、MCMC 要烧机多久，问的都是同一个 |λ₂|。最后试试另外两条链。周期链永远不收敛（三行在三个位置上循环，差一直是 1）；可约链会收敛，但收敛到的分布把第三个状态的概率压成了 0。这两个反例说明："转移矩阵一直乘下去就会收敛"这句话需要两个条件——不可约、非周期。
LAB 03
稳态分布
解 πP=π 与直接迭代两条路，给出同一个答案
问题
一台机器长期有多少比例的时间在维修？一个网页长期能分到多少流量？这类"长期占比"问题，问的都是同一个东西：这条链有没有一个稳下来的分布，有的话怎么算最省事。
模型
稳态分布 π 是转移矩阵的左特征向量（特征值 1），也是 Pn 每一行的极限。
π P = π， Σi πi = 1
链不可约且非周期时 π 唯一存在，且与初始分布无关。解线性方程和直接迭代 πk+1 = πkP 给出同一个答案。解方程得到的 π—
幂迭代得到的分布—
模拟 4000 步的频率—
三者一致吗—
同一个稳态分布，这里用了三条完全不同的路：解线性方程组、把一个初始分布反复乘矩阵、直接跑一条链数频率。在普通链上，三根柱子会对齐到小数点后三位。这不是巧合，而是三件事在说同一句话——π 是方程 πP=π 的解，是幂迭代的不动点，也是长期访问频率的极限。第三种说法（遍历定理）在实践中最有用：当状态空间大到没法解方程时，你还可以直接跑。把链换成周期链，幂迭代那根柱子会随着步数在三个位置来回跳——把步数滑杆一格一格拖，能看见它在循环。但解方程仍然给出 (1/3, 1/3, 1/3)，长期频率也是 1/3。这说明"平稳分布存在"和"分布会收敛到它"是两件不同的事。再换成可约链：第三个状态出得去回不来，解方程给出的 π₃ = 0，而模拟频率是一个很小的正数——因为模拟只跑了 4000 步，链还记得自己是从哪儿出发的。
LAB 04
收敛有多快
第二大特征值的模决定混合时间，慢链长什么样
问题
知道"最后会稳下来"还不够用——做 MCMC 要知道烧机烧多久，做排队要知道多久算长期。这一台问：收敛的快慢由什么决定，慢的链看起来是什么样子。
模型
收敛速度由第二大特征值的模 |λ₂| 控制，误差按 |λ₂|n 几何衰减。
‖πn − π‖ ≲ C·|λ₂|n， tmix ≈ 1 ⁄ (1 − |λ₂|)
1 − |λ₂| 叫谱隙。谱隙越小收敛越慢；有明显"团块"的链谱隙就小，因为跨团块很难。|λ₂|—
log₁₀|λ₂|（理论斜率）—
实测混合时间—
ln ε / ln|λ₂| 的估计—
纵轴是对数，三条曲线都是直线——这说明距离是按指数衰减的。三条线分别从三个不同的状态出发，斜率却完全一样，和那条虚线平行。斜率就是 log₁₀|λ₂|：起点只影响截距，不影响衰减速度。把懒惰程度往上拖，看这些直线怎么一起变平。懒惰化的意思是"每一步以概率 a 原地不动"，它不改变稳态分布（你停在哪儿的比例没变），却让 |λ₂| 从 0.473 一路涨到 0.947，混合时间从 6 步变成 75 步。同一个稳态，可以用快链达到，也可以用慢链达到，代价差十倍以上。MCMC 的全部调参工夫就花在这件事上：构造一条稳态正确、但混合尽量快的链。最后比一比后两行读数。ln ε / ln|λ₂| 给出的估计总是略大于实测值（懒惰 0.9 时是 86 对 75）——因为它假设距离从 1 开始按 |λ₂| 精确衰减，而真实的初始距离小于 1，且前几步衰减得比渐近速度更快。这个估计是一个可用的上界，不是精确值。
这一页想说的
马尔可夫链把"下一步只看现在"这个假设，变成了一整套可以动手算的工具：转移矩阵描述一步，矩阵幂描述 n 步，特征向量给出长期分布，第二大特征值给出收敛速度。这四件事在这一页里各对应一个实验台。记住两个限制：稳态要唯一，链必须不可约；分布要收敛，链还必须非周期。这两条在后面的 MCMC 里会以"链设计得对不对"的形式再出现一次。