12.1.1 状态、信息与一步转移
本节的时间为 \(n=0,1,\ldots\)，状态空间 \(S\) 有限或可数，配备全部子集组成的 \(\sigma\) 代数。先修内容是条件期望与停时。给定滤过 \((\mathcal F_n)\)，设 \(X_n\) 对它适应；\(\mathcal F_n\) 表示时刻 \(n\) 已知的信息。
矩阵 \(P=(p_{ij})_{i,j\in S}\) 若满足 \(p_{ij}\ge0\)、\(\sum_jp_{ij}=1\)，称为转移矩阵（transition matrix）。若对每个 \(n\ge0,j\in S\)，都有
则 \(X\) 是相对于 \((\mathcal F_n)\) 的时间齐次马尔可夫链（time-homogeneous Markov chain）。齐次指 \(P\) 不随 \(n\) 改变；马尔可夫性指给定当前状态后，已有信息不再改变下一步的条件分布。
初始分布写作行向量 \(\mu=(\mu_i)\)，其中 \(\mu_i=\mathbb P(X_0=i)\)。记 \(\mathbb P_\mu\) 为这一起点下的路径概率，\(\mathbb P_i\) 表示从状态 \(i\) 出发。只有当 \(\mathbb P_\mu(X_n=i)>0\) 时，才可直接用事件条件概率的比值写 \(p_{ij}=\mathbb P_\mu(X_{n+1}=j\mid X_n=i)\)；未到达状态的转移行仍须作为模型的一部分给定。
任给 \(\mu,P\)，都可用独立的 \(U_0,U_1,\ldots\sim U(0,1)\) 构造该链：枚举 \(S\)，按 \(\mu\) 划分单位区间，用 \(U_0\) 选择 \(X_0\)；再按当前行 \((p_{X_nj})_j\) 划分区间，用 \(U_{n+1}\) 选择 \(X_{n+1}\)。可数行的部分和趋于 \(1\)，故除零概率端点外选择唯一。新变量独立于 \(\sigma(U_0,\ldots,U_n)\)，从而构造满足式 (12.1-1)。独立均匀变量序列的构造见9.4 节。
自然滤过 \(\mathcal N_n=\sigma(X_0,\ldots,X_n)\) 包含在 \(\mathcal F_n\) 中。对式 (12.1-1) 再取关于 \(\mathcal N_n\) 的条件期望，塔式性质说明该链也相对于自然滤过满足马尔可夫性。反过来，任意扩大信息未必保留这一性质。
12.1.2 从路径概率到 Chapman–Kolmogorov 方程
初始分布与转移矩阵决定每一条有限路径的概率：
证明。令 \(A=\{X_0=i_0,\ldots,X_{n-1}=i_{n-1}\}\in\mathcal F_{n-1}\)。条件期望的定义给出 \(\mathbb P_\mu(A,X_n=i_n)=\mathbb E_\mu[\mathbf1_Ap_{X_{n-1}i_n}]=p_{i_{n-1}i_n}\mathbb P_\mu(A)\)。逐步回推到 \(n=0\) 即得式 (12.1-2)。证明没有除以路径概率，因而零概率路径也包含在内。
置 \(P^0=I\)，\(p^{(m)}_{ij}=(P^m)_{ij}\)。对整数 \(m,n\ge0\)，
第二式是 Chapman–Kolmogorov 方程。若 \(\mu_n(j)=\mathbb P_\mu(X_n=j)\)，则 \(\mu_n=\mu P^n\)。
证明。第一式在 \(m=0,1\) 时成立。若对 \(m\) 成立，由塔式性质，
可数求和的各项非负；用单调收敛于条件期望的积分定义即可交换求和。再从 \(i\) 出发，在时刻 \(m\) 按 \(X_m=k\) 分类，应用已证的 \(n\) 步公式，便得第二式。各行和为 \(1\)，也是由非负求和交换归纳得到。最后按 \(X_0=i\) 分类，得 \(\mu_n(j)=\sum_i\mu_i p^{(n)}_{ij}\)。
对任意有界函数 \(f:S\to\mathbb R\)，定义 \((Pf)(i)=\sum_jp_{ij}f(j)\)，则 \(\mathbb E_\mu[f(X_{n+m})\mid\mathcal F_n]=(P^mf)(X_n)\)。有界性保证级数绝对收敛。时间非齐次链应使用逐时转移矩阵的有序乘积，不能直接使用同一个 \(P\) 的幂。
12.1.3 两个可计算的模型
状态按 \(A,B,C\) 排列，从 \(A\) 出发，取
例如 \((P^2)_{AC}=p_{AA}p_{AC}+p_{AB}p_{BC}+p_{AC}p_{CC}=1/8\)，两步到 \(C\) 的路径只能是 \(A\to B\to C\)。完整路径 \(A\to B\to B\to C\) 的概率是 \((1/2)(1/2)(1/4)=1/16\)，而三步终点在 \(C\) 的概率为
后者还包括更早到达 \(C\) 后一直停留的路径。计算终点概率时，必须把所有可能的中间路径加起来。
设 \(S=\{0,1\}\)，\(0\le\alpha,\beta\le1\)，\(q_n=\mathbb P_\mu(X_n=1)\)。由全概率公式，
若 \(s=\alpha+\beta>0\)，解固定点方程得 \(\pi_1=\alpha/s\)，\(\pi_0=\beta/s\)，直接代入可验 \(\pi P=\pi\)。这样的概率向量称为平稳分布（stationary distribution）。令 \(\rho=1-s\)，递推两边减去 \(\pi_1\)，归纳得
当 \(0<s<2\) 时，\(|\rho|<1\)，误差按几何速度趋零。例如 \(\alpha=0.2,\beta=0.3,q_0=0\)，则 \(q_n=0.4(1-2^{-n})\)，\(q_5=0.3875\)。误差不超过 \(0.01\) 等价于 \(2^n\ge40\)，最少需要 \(6\) 步。
边界必须单独处理：\(s=0\) 时 \(P=I\)，初始分布一直不变；\(s=2\) 时必有 \(\alpha=\beta=1\)，状态每步交替，除非 \(q_0=1/2\)，否则分布不收敛。中间情形 \(\rho<0\) 的误差交替变号，但幅度仍衰减。平稳分布与长期行为的一般关系将在下一节讨论。
12.1.4 互通、闭类与周期
若某个 \(n\ge0\) 满足 \(p^{(n)}_{ij}>0\)，记 \(i\to j\)，称 \(j\) 从 \(i\) 可达。若 \(i\to j\) 且 \(j\to i\)，称两状态互通（communicate），记 \(i\leftrightarrow j\)。互通是等价关系，其等价类称互通类。全体状态只有一个互通类时，链不可约（irreducible）。集合 \(C\subseteq S\) 若满足每个 \(i\in C\) 都有 \(\sum_{j\in C}p_{ij}=1\)，称为闭集；一个闭的互通类称为闭类（closed class）。若 \(p_{ii}=1\)，则 \(i\) 是吸收状态。
自反性来自 \(P^0=I\)，对称性来自定义，传递性来自 Chapman–Kolmogorov 方程中正概率路径的拼接。例 12.1-1 有两个互通类：\(\{A,B\}\) 与 \(\{C\}\)。前者可以经 \(B\) 离开，后者为闭类。“闭”只禁止离开，并不禁止外部状态进入。
对有正时间返回可能的状态 \(i\)，定义返回时刻集合 \(R_i=\{n\ge1:p^{(n)}_{ii}>0\}\) 与周期（period）
\(d(i)=1\) 称为非周期。若 \(R_i\) 为空，本节不为它指定周期；这种情况可能出现在无法返回的单点互通类中。
互通状态周期相同。若 \(i\ne j\) 且互通，取 \(a,b\ge1\) 使 \(p^{(a)}_{ij}>0,p^{(b)}_{ji}>0\)。于是 \(a+b\in R_i\cap R_j\)。对每个 \(n\in R_j\)，拼接 \(i\to j\)、在 \(j\) 返回及 \(j\to i\)，得到 \(a+n+b\in R_i\)。所以 \(d(i)\) 同时整除 \(a+b\) 与 \(a+n+b\)，从而整除每个 \(n\in R_j\)，即 \(d(i)\mid d(j)\)。交换 \(i,j\) 得反向整除，故两者相等。
有自环的状态周期为 \(1\)，同一互通类中的其他状态也因此非周期。确定性交替的两状态链只能在偶数步返回，周期为 \(2\)。可达性与周期只描述哪些路径可能发生；常返性还涉及无限时间内返回的概率，留待下一节区分有限与可数状态的结论。
12.1.5 信息扩大与状态合并的反例
独立公平硬币序列 \(X_n\in\{0,1\}\) 相对于自然滤过是马尔可夫链，转移矩阵两行均为 \((1/2,1/2)\)。若改用 \(\mathcal G_n=\sigma(X_0,\ldots,X_{n+1})\)，则下一枚硬币已在信息中，故 \(\mathbb P(X_{n+1}=1\mid\mathcal G_n)=\mathbf1_{\{X_{n+1}=1\}}\)。给定任一当前状态，这个指标仍可能取 \(0\) 或 \(1\)，不能表示成只依赖 \(X_n\) 的转移概率。因此不能省略“相对于哪个滤过”。
再考虑另一条链：三个状态按 \(A\to B\to C\to A\) 确定性循环，初始状态在三点上均匀分布。只观察合并后的状态 \(Y_n=f(X_n)\)，其中 \(f(A)=f(B)=0,f(C)=1\)。以下两种历史各有概率 \(1/3\)：
第一种历史迫使 \(X_1=A\)，下一步仍观察到 \(0\)；第二种迫使 \(X_1=B\)，下一步观察到 \(1\)。相同的当前观测值 \(Y_1=0\) 对应不同的未来条件分布，所以 \(Y\) 相对于自己的自然滤过也不是马尔可夫链。习题 12.1-4 给出可保证状态合并后仍为链的条件。
12.1.6 离散停时处的强马尔可夫性质
固定时刻的马尔可夫性还可延伸到根据已有信息选择的随机时刻。令 \(T\) 是关于 \((\mathcal F_n)\) 的停时，且 \(\mathbb P_\mu(T<\infty)=1\)。记 \(\mathcal F_T=\{A\in\mathcal F:A\cap\{T\le n\}\in\mathcal F_n,\ \forall n\}\)。特别地，\(A\in\mathcal F_T\) 蕴含 \(A\cap\{T=n\}\in\mathcal F_n\)。
对整数 \(r\ge1\) 与任意有界函数 \(h:S^r\to\mathbb R\)，定义
则强马尔可夫性质（strong Markov property）为
证明。先固定 \(n\)。对指定的未来路径，逐次使用式 (12.1-1) 与塔式性质，得到其关于 \(\mathcal F_n\) 的条件概率为 \(p_{X_nj_1}\prod_{\ell=1}^{r-1}p_{j_\ell j_{\ell+1}}\)。按可数条未来路径求和，便得 \(\mathbb E_\mu[h(X_{n+1},\ldots,X_{n+r})\mid\mathcal F_n]=K_h(X_n)\)。令 \(|h|\le C\)，则 \(|K_h|\le C\)，故这些求和绝对收敛。
对 \(A\in\mathcal F_T\)，先按互不相交的 \(\{T=n\}\) 分解，再用刚才的确定时刻结论：
每个级数的绝对值之和不超过 \(C\sum_n\mathbb P_\mu(A\cap\{T=n\})\le C\)。在零概率的 \(\{T=\infty\}\) 上，将涉及的状态变量统一取某个固定状态即可。此外 \(\{X_T=i\}\cap\{T\le m\}=\bigcup_{n=0}^m\{T=n,X_n=i\}\in\mathcal F_m\)，故 \(X_T\) 对 \(\mathcal F_T\) 可测。条件期望的定义与唯一性遂给出结论。
取 \(h(j_1,\ldots,j_m)=f(j_m)\)，得到 \(\mathbb E_\mu[f(X_{T+m})\mid\mathcal F_T]=(P^mf)(X_T)\)。本节证明的是有界测试函数的有限未来块形式，无需 \(\mathbb E_\mu T<\infty\)；若停时可能无限，则不能直接把 \(X_T\) 当作有限时刻状态代入。一般路径空间表述见参考文献中的定理 5.2.5。
12.1.7 习题与解答
习题 12.1-1 · 从混合初始分布计算
使用例 12.1-1 的矩阵，改取 \(\mu=(1/2,1/2,0)\)。计算两步后的分布，以及事件 \(\{X_0=B,X_1=B,X_2=C\}\) 的概率。解释两者中有关 \(C\) 的数值为何不同。
左乘式 (12.1-5) 的 \(P^2\)，得 \(\mu P^2=\frac12(3/8,1/2,1/8)+\frac12(1/4,3/8,3/8)=(5/16,7/16,1/4)\)。因而 \(\mathbb P_\mu(X_2=C)=1/4\)。指定路径的概率则为 \(\mu_Bp_{BB}p_{BC}=(1/2)(1/2)(1/4)=1/16\)。终点事件还包含 \(A\to B\to C\) 与 \(B\to C\to C\)，概率分别为 \(1/16\)、\(1/8\)；三项之和正是 \(1/4\)。
习题 12.1-2 · 达到给定误差需要几步
两状态链满足 \(\alpha=0.3,\beta=0.2\)，且从状态 \(1\) 出发。求平稳分布、\(q_n\) 及总变差误差不超过 \(0.005\) 的最小整数 \(n\)。若改为 \(\alpha=\beta=1\)，同一起点能否满足该误差要求？
\(\pi=(0.4,0.6)\)，代入可验 \(\pi P=\pi\)。递推为 \(q_{n+1}=0.3+0.5q_n\)，所以 \(q_{n+1}-0.6=0.5(q_n-0.6)\)，从 \(q_0=1\) 得 \(q_n=0.6+0.4\,2^{-n}\)。误差为 \(0.4\,2^{-n}\)，要求 \(2^n\ge80\)，最少 \(n=7\)；在 \(n=6\) 时误差 \(0.00625\) 仍过大。若 \(\alpha=\beta=1\)，平稳分布为 \((1/2,1/2)\)，而从确定状态出发的分布始终是某个点质量，总变差距离一直等于 \(1/2\)，不存在满足要求的时刻。
习题 12.1-3 · 闭类与周期并非同一问题
四状态链的非零转移为 \(p_{12}=1,p_{21}=p_{23}=1/2,p_{34}=p_{43}=1\)。求所有互通类、闭类和周期。再把第三行改成 \(p_{33}=\varepsilon,p_{34}=1-\varepsilon\)，其中 \(0<\varepsilon<1\)，哪些答案改变？
\(1,2\) 相互可达；\(3,4\) 相互可达，且都无法回到前两点。因此互通类为 \(\{1,2\}\)、\(\{3,4\}\)，只有后者闭。原链在每个类内只能交替，任何返回长度均为偶数，而长度 \(2\) 的返回概率为正，所以四个状态的周期均为 \(2\)。修改后可达关系未变，互通类和闭类不变。状态 \(3\) 有自环，周期变为 \(1\)，互通性使 \(4\) 也为周期 \(1\)。前两点一旦离开便不能回来，它们的返回路径仍只能在 \(1,2\) 间交替，周期仍为 \(2\)。
习题 12.1-4 · 何时可以合并状态
设 \(f:S\to E\)，其中 \(E=f(S)\)。假设只要 \(f(i)=f(i')=a\)，对每个 \(b\in E\) 都有 \(\sum_{j:f(j)=b}p_{ij}=\sum_{j:f(j)=b}p_{i'j}=:q_{ab}\)。证明 \(Y_n=f(X_n)\) 是转移矩阵为 \(Q=(q_{ab})\) 的链。用例 12.1-1 检查合并 \(A,B\) 是否满足条件；条件失败是否意味着每种初始分布下的 \(Y\) 都不是链？
各原状态的转移行按不相交的纤维 \(f^{-1}(\{b\})\) 求和，得到 \(q_{ab}\ge0,\sum_bq_{ab}=1\)。由条件得 \(\mathbb P(Y_{n+1}=b\mid\mathcal F_n)=\sum_{j:f(j)=b}p_{X_nj}=q_{Y_nb}\)。对 \(\mathcal H_n=\sigma(Y_0,\ldots,Y_n)\subseteq\mathcal F_n\) 再取条件期望，塔式性质给出 \(\mathbb P(Y_{n+1}=b\mid\mathcal H_n)=q_{Y_nb}\)，即所求马尔可夫性。合并例中的 \(A,B\) 时，它们到另一组 \(\{C\}\) 的概率分别为 \(0\) 和 \(1/4\)，条件不成立。这不能推出每种起点都会失败：若 \(X_0=C\)，则 \(Y_n\) 恒为同一个值，仍是马尔可夫链。这个条件保证所有初始分布都可使用同一个合并转移矩阵。
关键术语
- 马尔可夫性
- 给定当前状态后，已有信息不再改变下一步的条件分布。
- 转移矩阵
- 非负、各行和为 \(1\) 的一步转移概率矩阵。
- 初始分布
- 状态 \(X_0\) 的分布，与转移矩阵共同决定有限路径概率。
- Chapman–Kolmogorov 方程
- 按中间状态求和，将多步转移分解为两个时段的转移。
- 互通类与不可约性
- 双向可达形成等价类；全空间只有一个类时称链不可约。
- 闭类
- 链从中出发后，一步离开的概率为零的互通类。
- 周期
- 所有正概率返回时间的最大公约数。
- 平稳分布
- 满足 \(\pi P=\pi\) 的概率向量。
- 强马尔可夫性
- 在几乎必然有限的停时处，给定当前状态后仍按原转移机制演化。
参考文献
- Durrett, R. (2019). Probability: Theory and Examples, 5th ed. 作者公开版本，§§5.1–5.2 的链、条件分布与强马尔可夫性（定理 5.2.5）；周期及其后续理论另见 §5.7。本节仅证明有界函数的有限未来块版本。
- Polyanskiy, Y. (2018). MIT 6.436J / 15.085J, Lecture 21: Markov Chains I。用于转移矩阵、初始分布、多步转移与有限状态例子的对照；其有限状态分类结论不能直接推广到所有可数状态链。