本页目录

随机过程 II · Markov 链（一）：转移与状态分类

Markov 链是"只看现在、不问过去"的随机演化——这个看似粗暴的假设换来了完整的矩阵化理论：演化 = 矩阵幂。本页管"怎么转移、状态什么性格"，下一页管"转移到最后去哪"。高等代数的矩阵工具在此整装上岗。

学习层：平稳不等于混合，谱也不会替你补结构条件

1. 先预测：三个性质到底各自保证什么？

实验固定三张小转移矩阵，先不显示矩阵幂、TV 距离、特征值和结果账本。请先回答：

  1. \(\pi P=\pi\) 是“平稳分布”的方程，还是已经证明了链不可约、非周期并且从任意初态收敛？
  2. 有限状态链不可约且非周期时，\(\mu_t=\mu_0P^t\) 是否从每个初始分布都趋向同一个唯一 \(\pi\)？
  3. 不可约的周期链是否可以有唯一平稳分布，却让 \(\operatorname{TV}(\mu_t,\pi)\) 永远不趋于 \(0\)？
  4. 可约链是否可能有多个闭类、多个平稳分布，因而让长期行为依赖初始状态？

揭示前不显示数值参数或图表；提交后再用同一个 \(P\) 同时核对结构、\(P^t\)、分布和谱。这样“定理条件”与“一条样本曲线”不会混成一句混合保证。

2. 静态后备：三个反例把边界钉住

JavaScript 失效时的静态读法：以下使用行随机矩阵，状态从 \(0\) 开始，\(\operatorname{TV}(\mu,\nu)=\frac12\sum_i|\mu_i-\nu_i|\)。

预设 \(P\) 结构证书 平稳与谱 从 \(\delta_0\) 读什么
不可约、非周期 \(\begin{pmatrix}0.8&0.2\\0.3&0.7\end{pmatrix}\) 一个互通类，\(d=1\) \(\pi=(0.6,0.4)\)，\(\lambda=(1,0.5)\) \(\delta_0P^t=(0.6+0.4\cdot0.5^t,\,0.4-0.4\cdot0.5^t)\)，故 \(\operatorname{TV}=0.4\cdot0.5^t\)
不可约、周期 \(\begin{pmatrix}0&1\\1&0\end{pmatrix}\) 一个互通类，\(d=2\) \(\pi=(0.5,0.5)\)，\(\lambda=(1,-1)\) 分布在 \(\delta_0,\delta_1\) 间交替；TV 永远为 \(0.5\)
可约、两吸收类 \(\begin{pmatrix}1&0&0\\0&1&0\\0.5&0.5&0\end{pmatrix}\) 闭类 \(\{0\},\{1\}\)；全链不可约性失败 \(\pi_a=(a,1-a,0)\)，\(\lambda=(1,1,0)\) \(\delta_0,\delta_1\) 各自永远吸收；\(\delta_2P=(0.5,0.5,0)\)

第一行给出一个精确的谱对账：非平凡特征值的模为 \(0.5\)，而从 \(\delta_0\) 出发的 TV 恰为 \(0.4\cdot|0.5|^t\)。第二行的 \(-1\) 不衰减，所以“有平稳分布”不推出点态分布收敛。第三行甚至没有唯一的全局平稳分布；\(P^t\) 仍然可以精确算出，但它不能凭空制造不可约性。

3. 账本的四层读法

数学上对任意初始行分布 \(\mu_0\) 都有以下关系；实验可选各个点质量 \(\delta_i\)，以及当前选定的平稳分布 \(\pi\)，逐项列出

\[ P^t,\qquad \mu_t=\mu_0P^t,\qquad \operatorname{TV}(\mu_t,\pi)=\frac12\sum_i|(\mu_t)_i-\pi_i|,\qquad \|\pi P-\pi\|_1. \]

实验直接计算有限矩阵幂，展示的是整个概率分布，并非一条随机样本轨道；数值含浮点舍入。结构判断则把每个严格正的转移概率作为一条边，不能因概率很小就删去它。

谱栏报告 \(P\) 的特征值和非平凡谱模 \(\rho_\star=\max_{j\ge2}|\lambda_j|\)，并把 \(\rho_\star^t\) 与当前 TV 放在一起。对第一张二维模型，精确关系是 \(\mathrm{TV}(\mu_t,\pi)=\mathrm{TV}(\mu_0,\pi)\rho_\star^t\)，从 \(\delta_0\) 出发的系数是 \(0.4\)，从 \(\delta_1\) 出发是 \(0.6\)，从 \(\pi\) 出发则为 \(0\)；一般链中谱信息需要结合可逆性、范数和初始分布等假设，不能把一个 \(\rho_\star^t\) 数字自动宣称为所有 TV 的等号。平稳残差接近零只说明概率向量在数值精度内满足平稳方程，不能代替精确证明；不可约、非周期和可约证书仍要另行报告。

4. 定理边界与迁移

  • 有限 + 不可约给唯一平稳分布；再加非周期才得到从任意初态到 \(\pi\) 的分布收敛。周期链的 Cesàro 平均可以收敛，但逐步分布可能振荡。
  • 上述不可约条件是一个方便的充分条件，并非所有初态趋同一极限的必要条件。例如 \(P=\begin{pmatrix}1&0\\1&0\end{pmatrix}\) 可约，但一步后所有初态都到 \(\delta_0\)。周期链从 \(\pi\) 出发也会始终平稳；“可能振荡”不是“每个初态必振荡”。
  • 可约时应先拆互通类和闭类。平稳分布可以有多个，瞬态类的质量会流向闭类；“看起来收敛”的一条初始轨迹不是唯一性证书。
  • 对无限状态空间，常返/正常返、平稳分布存在性和混合还要另加条件；本实验的有限矩阵不替代那些定理。
  • \(\pi P=\pi\) 是不变性方程，不是“链已经跑了很久”的经验拟合；\(P^t\) 的每一行和为 \(1\) 也不等于每一行都趋向同一个 \(\pi\)。

1. 状态要记住多少过去？

定义。 对可数状态空间 \(S\)，离散时间过程满足

\[ \Pr(X_{n+1}=j\mid X_0,\ldots,X_n)=p_{X_nj}\quad\text{几乎处处}, \]

就称为本页讨论的时齐 Markov 链。右侧不依赖时间 \(n\)；若转移律随 \(n\) 变化，仍可能有 Markov 性，却不能统一写成同一个矩阵的幂。对具体历史写条件概率时，只在该历史具有正概率时使用比值定义。

这里的“无记忆”是给定当前状态后，过去不再提供预测未来所需的额外信息，不是各时刻相互独立。天气链中，知道今天晴朗仍会改变明天晴朗的概率。

状态是建模的一部分。等待“连续两次正面”时，只记录抛掷次数不够；记录“目前没有连续正面 / 刚出现一个正面 / 已完成”才足够做一步预测。原则上可把完整历史放进状态，从而 Markov 化，但状态空间会增长，不保证得到小而实用的有限模型。把一个 Markov 链的若干状态合并，反过来也不保证仍是 Markov 链。

行随机矩阵 \(P=(p_{ij})\) 满足 \(p_{ij}\ge0\)、\(\sum_jp_{ij}=1\)。本页统一状态编号从 \(0\) 开始，初始分布用行向量 \(\mu_0\) 表示，之后

\[ \mu_{n+1}=\mu_nP. \]

“矩阵 + 初始分布”决定路径的有限维分布。例如 \(\Pr(X_0=i_0,\ldots,X_n=i_n)=\mu_0(i_0)\prod_{r=0}^{n-1}p_{i_ri_{r+1}}\)。

2. 从路径求和到矩阵幂

三种链的正概率转移图、闭类、周期与初态相关的分布

图 2.1每条箭头是一项严格正的转移概率。闭类只能流入、不能流出；周期由可返回的正整数步数决定。右侧公式与实验使用同一组矩阵。图为固定宽度，手机可横向滚动。

设 \(p_{ij}^{(n)}\) 为从 \(i\) 出发经过 \(n\) 步到 \(j\) 的概率，约定 \(P^{(0)}=I\)。按第 \(m\) 步的中转状态 \(k\) 分组：

\[ p_{ij}^{(m+n)} =\sum_{k\in S}p_{ik}^{(m)}p_{kj}^{(n)}. \]

第一段到 \(k\) 的概率乘以从 \(k\) 出发继续 \(n\) 步的概率，再把互斥的中转状态加起来。这就是 Chapman–Kolmogorov 方程。时齐性保证第二段用的仍是同一个转移律，所以 \(P^{(n)}=P^n\)、\(\mu_n=\mu_0P^n\)。可数无限状态时，非负求和可用 Tonelli 交换顺序。

以实验第一张矩阵为例：

\[ P=\begin{pmatrix}0.8&0.2\\0.3&0.7\end{pmatrix}, \quad P^2=\begin{pmatrix}0.70&0.30\\0.45&0.55\end{pmatrix}. \]

从状态 \(0\) 两步回到 \(0\)，概率为 \(0.8^2+0.2\times0.3=0.70\)。把 \(0.3\) 误抄成另一条天气链的 \(0.4\)，就会得到属于另一模型的 \(0.72\)。

矩阵幂不要求可对角化。 只有确实存在可逆 \(V\) 使 \(P=V\Lambda V^{-1}\)，才能写 \(P^n=V\Lambda^nV^{-1}\)。例如

\[ J=\begin{pmatrix}1/2&1/2&0\\0&1/2&1/2\\0&0&1\end{pmatrix}, \qquad \delta_0J^n=(2^{-n},\,n2^{-n},\,1-(n+1)2^{-n}). \]

重复特征值 \(1/2\) 对应非平凡 Jordan 块，衰减中有 \(n2^{-n}\)，不能只看特征值的幂而漏掉多项式因子。这里 \(n=0\) 也成立。随机矩阵的特征值满足 \(|\lambda|\le1\)；单位圆上除了 \(1\) 还可能有 \(-1\) 或复数，循环链正是反例。一般谱分析留到下一页，本页先把状态结构辨清。

3. 可达、闭类、返回与周期

可达 \(i\to j\) 指存在整数 \(n\ge0\) 使 \((P^n)_{ij}>0\)。允许 \(n=0\)，每个状态都可达自身。互通 \(i\leftrightarrow j\) 指双向可达；它是等价关系，把状态分成互通类。全空间只有一个类才叫不可约。一个类若没有正概率边通往类外，就叫闭类；吸收状态是仅含一个状态的闭类，满足 \(p_{ii}=1\)。

3.1 返回必须排除第零步

从 \(i\) 出发，首次返回时刻是

\[ \tau_i^+=\inf\{n\ge1:X_n=i\},\qquad \inf\varnothing=\infty. \]

一次返回后可以重新从 \(i\) 计算，这是离散链的强 Markov 性在返回时刻的应用。若返回概率为 \(f<1\)，包括起点的总访问次数 \(V_i\) 满足 \(\Pr_i(V_i\ge k)=f^{k-1}\)，故

\[ \mathbb E_iV_i=\sum_{n\ge0}(P^n)_{ii} =\frac1{1-f}<\infty. \]

若 \(f=1\)，每次回到 \(i\) 后还会再返回，访问次数几乎必然无穷。因此 \(i\) 常返当且仅当 \(\sum_{n\ge0}(P^n)_{ii}=\infty\)。这是概率结论，不能由一条有限模拟中“回来了几次”证明。

有限链的实用结论：闭互通类中的状态全部正常返，其他状态全部瞬过。 非闭类有一条正概率路径离开且不再返回；有限闭不可约类则能从每个状态在统一有限步数内、以统一正概率到达指定状态。按这样的步数分块，未返回概率有几何尾，因此平均返回时间有限。可数无限链中，“闭”不保证常返，常返也不保证正常返。

3.2 周期是所有返回步数的最大公约数

若存在正时间返回路径，定义

\[ d(i)=\gcd\{n\ge1:(P^n)_{ii}>0\}. \]

实验对没有任何正时间返回的瞬过单点（第三预设的状态 \(2\)）显示“无正时间返回”，不把它误标成周期 \(1\)。周期 \(1\) 称非周期；有自环 \(p_{ii}>0\) 就足以保证 \(d(i)=1\)，但无自环也可能非周期，例如同时存在长度 \(2\) 和 \(3\) 的返回环。

互通状态的常返性、正常返性和周期相同。周期相同可从路径看出：若 \(i\to j\) 有长度 \(a\) 的路径、\(j\to i\) 有长度 \(b\) 的路径，那么 \(a+b\) 和 \(a+n+b\) 都是 \(i\) 的返回长度，其中 \(n\) 是 \(j\) 的任一返回长度；相减说明 \(d(i)\) 整除所有这样的 \(n\)，再交换两点得到相等。

二状态互换链只在偶数步返回，所以 \(d=2\)。从 \(\delta_0\) 出发的分布交替；从 \(\pi=(1/2,1/2)\) 出发却每步相同。结构决定哪些结论适用，初态决定具体轨迹。

3.3 无限空间的边界：对称随机游走

整数线上每步向右概率 \(p\)、向左概率 \(q=1-p\)，其中 \(0<p<1\)。原点的返回概率满足

\[ p_{00}^{(2n)}=\binom{2n}{n}(pq)^n,\qquad p_{00}^{(2n+1)}=0. \]

当 \(p=q=1/2\)，由中心二项式系数渐近式，偶数步项约为 \(1/\sqrt{\pi n}\)，总和发散，所以常返。它没有可归一化的平稳概率分布（平稳方程要求在整个 \(\mathbb Z\) 上非负的仿射序列，只能是常数，而非零常数不可求和），故是零常返。当 \(p\ne q\)，\(4pq<1\)，返回级数被几何级数控制，因此瞬过。两种情况下周期都为 \(2\)：周期与常返性是不同分类轴。

4. 一步分析：首达概率与首达时间

对目标集合 \(A\)，定义

\[ \tau_A=\inf\{n\ge0:X_n\in A\},\quad h_i=\Pr_i(\tau_A<\infty),\quad m_i=\mathbb E_i\tau_A. \]

这次允许第零步，所以在 \(A\) 内 \(h_i=1\)、\(m_i=0\)，与“首次返回”不同。对 \(i\notin A\)，按第一步分解：

\[ h_i=\sum_jp_{ij}h_j,\qquad m_i=1+\sum_jp_{ij}m_j. \]

第二式允许期望为无穷。方程本身未必唯一确定答案；概率和期望分别是对应边界方程的最小非负解。理由是先求“在前 \(n\) 步到达”的概率或截断期望，逐步迭代并取单调极限；任何非负解都逐步压住这些截断量。

例如 \(P=I\)、\(A=\{1\}\)，从状态 \(0\) 永远到不了 \(A\)，所以 \(h_0=0\)；但方程仅给 \(h_0=h_0\)，任意非负数都满足。对于期望，\(m_0=1+m_0\) 没有有限解，实际答案是无穷。

若是有限链且从每个目标外状态都存在到达 \(A\) 的正概率路径，则统一有限步内到达的概率有正下界，故 \(\tau_A\) 有几何尾。按目标外/目标内排列矩阵，设 \(Q\) 是目标外子矩阵，\(R\) 是进入各吸收目标的子矩阵。在把目标变成吸收态后，

\[ F=\sum_{n\ge0}Q^n=(I-Q)^{-1},\qquad m=F\mathbf1,\qquad H=FR. \]

\(F_{ij}\) 是吸收前访问瞬过状态 \(j\) 的期望次数（含第零步）；\(H\) 各列是吸收到对应目标的概率。计算时解线性方程组即可，不必显式求逆。若目标外还有永不到达目标的闭类，这个 \(Q\) 就不能直接当作瞬过矩阵。

4.1 赌徒破产：把条件和量级写完整

状态为 \(0,1,\ldots,N\)，\(N\ge2\)；内部每步以 \(p\) 加 \(1\)、以 \(q=1-p\) 减 \(1\)，到 \(0\) 或 \(N\) 停止。对 \(0<p<1\)，吸收时间 \(\tau_{\{0,N\}}\) 的期望有限。成功概率满足

\[ h_i=ph_{i+1}+qh_{i-1},\quad h_0=0,\ h_N=1, \qquad h_i= \begin{cases} i/N,&p=q=1/2,\\ \dfrac{1-(q/p)^i}{1-(q/p)^N},&p\ne q. \end{cases} \]

差分方程的特征根是 \(1,q/p\)；公平时重根产生仿射解。若 \(p=0\)，内部 \(h_i=0\)；若 \(p=1\)，内部 \(h_i=1\)，不把端点代入含除法的公式。

期望停止时间满足 \(m_i=1+pm_{i+1}+qm_{i-1}\)、\(m_0=m_N=0\)，解为

\[ m_i= \begin{cases} i(N-i),&p=q=1/2,\\ \dfrac{Nh_i-i}{p-q},&p\ne q. \end{cases} \]

偏置式也可由停止后的平均位置 \(Nh_i=i+(p-q)m_i\) 读出；这里有限期望和有界停止位置支持这个计算，不能把任意无界停止时刻直接代入鞅等式。

例如 \(p=0.4,q=0.6,N=4,i=2\)，\(h_2=4/13\)、\(m_2=50/13\)。公平时 \(h_2=1/2\)、\(m_2=4\)。对固定初始本金 \(i\) 和 \(p<q\)，让目标 \(N\to\infty\)，成功率按指数衰减；若 \(i\) 同时变化，须重新分析。它不证明所有规则、下注方式和停止策略下的无条件口号。

5. 例题：把图、方程与答案连起来

例 1：可约链的状态分类。

\[ P=\begin{pmatrix}1/2&1/2&0\\1/2&1/2&0\\1/3&1/3&1/3\end{pmatrix}. \]

互通类为 \(\{0,1\}\) 和 \(\{2\}\)。前者闭、正常返、自环使周期为 \(1\)；后者非闭、瞬过，也有自环所以周期为 \(1\)。从 \(2\) 出发首次返回 \(2\) 的概率仅为 \(1/3\)：若第一步离开，之后就再也回不来。包括起点的平均访问次数为 \(\sum_{n\ge0}(1/3)^n=3/2\)。

例 2：连续两次正面。 公平且独立地抛硬币，以状态 \(0\) 表示无连续正面、\(1\) 表示刚有一个正面、\(2\) 表示已经完成。矩阵为

\[ P=\begin{pmatrix}1/2&1/2&0\\1/2&0&1/2\\0&0&1\end{pmatrix}. \]

设 \(m_2=0\)，则 \(m_0=1+\tfrac12m_0+\tfrac12m_1\)、\(m_1=1+\tfrac12m_0\)，得到 \(m_0=6,m_1=4\)。两次正面这类“模式”会重叠，不能把每个长度为 \(2\) 的滑动窗口当作独立试验后直接套几何分布。

练习 1：周期链真的每次都振荡吗？

对二状态互换链，从 \(\mu_0=(a,1-a)\) 出发，求 \(\mu_n\)、TV 和 Cesàro 平均。

展开推导与核对

偶数步仍是 \((a,1-a)\)，奇数步变为 \((1-a,a)\)，所以 \(\operatorname{TV}(\mu_n,(1/2,1/2))=|a-1/2|\)。仅当 \(a=1/2\) 时逐步分布始终平稳。对前 \(M\) 项 \(\bar\mu_M=M^{-1}\sum_{n=0}^{M-1}\mu_n\)，偶数 \(M\) 时恰为 \(\pi\)，奇数 \(M\) 时 TV 为 \(|a-1/2|/M\)。平均收敛与逐步收敛不同。

练习 2：为什么不能直接宣布 TV 等于谱模的幂？

对第 2 节矩阵 \(J\)，从 \(\delta_0\) 出发，验证分布公式并求到 \(\delta_2\) 的 TV。

展开推导与核对

在状态 \(0\) 停留 \(n\) 步的概率为 \(2^{-n}\)。要在第 \(n\) 步位于 \(1\)，须恰有一次 \(0\to1\)，这次转移可放在 \(n\) 个位置，每条路径概率为 \(2^{-n}\)，得到 \(n2^{-n}\)。其余概率在吸收态 \(2\)，故 TV 为 \((n+1)2^{-n}\)。例如 \(n=4\)，分布为 \((1/16,4/16,11/16)\)、TV 为 \(5/16\)，而非 \(|1/2|^4=1/16\)。这也直接说明 \(J\) 的重复特征值不能按三个独立特征向量处理。

练习 3：由访问次数矩阵求吸收时间

对“连续两次正面”模型，计算瞬过子矩阵 \(Q\) 的 \(F=(I-Q)^{-1}\)，核对从两个未完成状态出发的期望。

展开推导与核对
\[ Q=\begin{pmatrix}1/2&1/2\\1/2&0\end{pmatrix}, \qquad F=\begin{pmatrix}4&2\\2&2\end{pmatrix}. \]

相乘可检验 \((I-Q)F=I\)。行和为 \((6,4)\)，与一步分析相同。从 \(0\) 出发，吸收前平均访问状态 \(0\) 四次、状态 \(1\) 两次，其中前者包括初始访问。进入唯一吸收态的向量为 \(R=(0,1/2)^\mathsf T\)，所以 \(FR=(1,1)^\mathsf T\)：两个初态都几乎必然完成。期望 \(6\) 不意味着第六次一定完成。

推导与进一步阅读：Levin、Peres、Wilmer 的 Markov Chains and Mixing Times，第 1、2、4、21 章分别讨论有限链结构、经典模型、混合以及可数无限状态的区别。

下一页：平稳分布、收敛定理与 MCMC / PageRank。一步分析还可与LP 和 DP中的 Bellman 递推对照：状态保存了未来计算所需的信息，条件期望把第一步和余下过程连接起来。