12.4 可逆性、耦合与马尔可夫链遍历平均

平稳分布描述分布保持不变，可逆性进一步要求平稳路径正反同分布。本节用详细平衡求生灭链的平稳概率，再由耦合不等式证明有限链的几何混合界。最后把样本路径分成独立的返回区段，证明正常返可数链的遍历平均，并通过周期链区分逐时分布与时间平均，为马尔可夫链蒙特卡洛建立理论基础。

12.4.1 详细平衡与时间逆转

以下 \(P=(p_{ij})\) 是有限或可数状态空间 \(S\) 上的离散时间齐次转移矩阵。沿用12.1 节的行向量约定，并使用12.2 节的平稳分布与正常返结论。

定义 12.4-1 · 详细平衡

概率向量 \(\pi\) 若满足

\[ \pi_i p_{ij}=\pi_jp_{ji}\qquad(i,j\in S), \]

(12.4-1)

则称它满足详细平衡（detailed balance，也称细致平衡）。两边是在平稳状态下沿同一条边正反向转移的概率。

对 \(i\) 求和，得到 \((\pi P)_j=\pi_j\sum_i p_{ji}=\pi_j\)，所以详细平衡蕴含平稳性。这里比较的是每一对状态；平稳方程只要求每个状态的总流入等于其平稳质量。

现设 \(\pi P=\pi\) 且每个 \(\pi_i>0\)。若 \(X_0\sim\pi\)，固定终点时刻后倒序观察路径，得到的转移矩阵为

\[ p^*_{ij}=\frac{\pi_jp_{ji}}{\pi_i}, \qquad \pi_{i_0}\prod_{k=0}^{n-1}p_{i_ki_{k+1}} =\pi_{i_n}\prod_{k=0}^{n-1}p^*_{i_{k+1}i_k}. \]

(12.4-2)

证明。平稳性给出 \(\sum_jp^*_{ij}=1\)，故 \(P^*\) 确为转移矩阵。将右侧的 \(p^*\) 逐项代入，所有相邻 \(\pi\) 因子消去，就得到左侧。此路径概率分解说明倒序过程也是齐次马尔可夫链，初始分布为 \(\pi\)、转移矩阵为 \(P^*\)。

若每段平稳路径与倒序路径同分布，称链在 \(\pi\) 下可逆（reversible）。式 (12.4-2) 表明 \(P^*=P\) 足以保证可逆；反过来，对长度为一的路径使用可逆性即得式 (12.4-1)。因此可逆性等价于详细平衡。起点若非平稳，逆向转移通常依赖时刻；有零平稳质量的状态则应先限制到 \(\pi\) 的支集，避免除以零。

平稳性不蕴含详细平衡

三个状态按模 \(3\) 编号，每步以 \(1/2\) 停留、以 \(1/2\) 向下一点移动。转移矩阵每列之和也为 \(1\)，故均匀分布平稳；但 \(\pi_0p_{01}=1/6\)，而 \(\pi_1p_{10}=0\)。这条链不可约、非周期，却不可逆。详细平衡是求平稳分布的充分条件，不是一般链平稳性的必要条件。

12.4.2 生灭链的平稳比率

在 \(S=\{0,\ldots,N\}\) 或 \(S=\{0,1,\ldots\}\) 上，生灭链（birth–death chain）只允许相邻转移与停留。记向上概率为 \(b_i\)，向下概率为 \(d_i\)，并设所有存在的相邻方向概率均正，\(b_i+d_i\le1\)；边界取 \(d_0=0\)，有限情形另取 \(b_N=0\)。

\[ w_0=1,\qquad w_n=\prod_{k=0}^{n-1}\frac{b_k}{d_{k+1}},\qquad W=\sum_{n\in S}w_n,\qquad \pi_n=\frac{w_n}{W}\quad(W<\infty). \]

(12.4-3)

这些比率保证 \(\pi_n b_n=\pi_{n+1}d_{n+1}\)，其余不同状态间的双向流量都为零，所以 \(\pi\) 可逆且平稳。反之，将任一平稳方程对有限集合 \(\{0,\ldots,n\}\) 求和，内部流量抵消，得到同一个边界平衡关系。因此平稳概率必须正比于 \(w_n\)；若 \(W=\infty\)，形式权重无法归一化，这条不可约链没有平稳概率。

例 12.4-1 · 非恒定生灭概率

按状态 \(0,1,2,3\) 排列，令

\[ P=\begin{pmatrix} \frac12&\frac12&0&0\\ \frac14&\frac5{12}&\frac13&0\\ 0&\frac12&\frac14&\frac14\\ 0&0&\frac12&\frac12 \end{pmatrix}. \]

(12.4-4)

相邻比率依次为 \(2,2/3,1/2\)，故 \(w=(1,2,4/3,2/3)\)、\(W=5\)，得到 \(\pi=(1/5,2/5,4/15,2/15)\)。逐边核算：\(\pi_0p_{01}=\pi_1p_{10}=1/10\)，\(\pi_1p_{12}=\pi_2p_{21}=2/15\)，\(\pi_2p_{23}=\pi_3p_{32}=1/15\)。

链不可约，且有自环，所以非周期。平稳时的平均状态为 \(\sum_i i\pi_i=2/5+8/15+6/15=4/3\)，在端点集合 \(\{0,3\}\) 中的概率为 \(1/5+2/15=1/3\)。第 12.4.5 小节将证明，这些数值也分别是长期样本平均与端点占用比例的几乎必然极限。

图 12.4-1 · 例 12.4-1 的平稳流量示意。状态位置任意，所有标注均由 \(\pi_i p_{ij}\) 精确计算；详细平衡比较同一条边的两个方向，而非要求各条边流量相同。

12.4.3 总变差与耦合不等式

定义 12.4-2 · 在同一概率空间上比较分布

可数空间上两个概率分布的总变差距离（total variation distance）为

\[ \|\mu-\nu\|_{\mathrm{TV}} =\sup_{A\subseteq S}|\mu(A)-\nu(A)| =\frac12\sum_{i\in S}|\mu_i-\nu_i|. \]

(12.4-5)

一个耦合（coupling）是联合随机变量 \((U,V)\)，其边缘分布分别为 \(\mu,\nu\)。耦合允许它们相关，但必须保持各自的边缘分布。

式 (12.4-5) 的第二个等号可这样核查：\(\sum_i(\mu_i-\nu_i)=0\)，故正项之和等于负项绝对值之和；取 \(A=\{i:\mu_i\ge\nu_i\}\) 就达到上确界。

定理 12.4-1 · 耦合不等式

\[ \|\mu-\nu\|_{\mathrm{TV}}\le\mathbb P(U\ne V). \]

(12.4-6)

证明。对任一 \(A\subseteq S\)，\(|\mu(A)-\nu(A)|=|\mathbb E(\mathbf1_{\{U\in A\}}-\mathbf1_{\{V\in A\}})|\le\mathbb E|\mathbf1_{\{U\in A\}}-\mathbf1_{\{V\in A\}}|\le\mathbb P(U\ne V)\)。再取上确界即得结论。

对两条链，若耦合后各坐标仍按 \(P\) 转移，且相遇后始终使用同一次转移，则以相遇时刻 \(T\) 表示，有 \(\|\mathcal L(X_n)-\mathcal L(Y_n)\|_{\mathrm{TV}}\le\mathbb P(T>n)\)。此外，任一转移矩阵都具有总变差收缩性：

\[ \|\mu P-\nu P\|_{\mathrm{TV}} \le\frac12\sum_j\sum_i|\mu_i-\nu_i|p_{ij} =\|\mu-\nu\|_{\mathrm{TV}}. \]

(12.4-7)

它说明对两种分布施加同一种随机转移，不会增加其总变差距离。

12.4.4 Doeblin 条件与有限链的混合界

定理 12.4-2 · 共同分量产生几何收敛

设 \(S\) 有限。若存在整数 \(m\ge1\)、\(0<\varepsilon<1\) 与概率向量 \(\nu\)，使

\[ (P^m)_{ij}\ge\varepsilon\nu_j\qquad\text{对所有 }i,j, \]

(12.4-8)

则 \(P\) 有唯一平稳分布 \(\pi\)，且对任意初始分布 \(\mu\)，

\[ \|\mu P^n-\pi\|_{\mathrm{TV}} \le(1-\varepsilon)^{\lfloor n/m\rfloor}. \]

(12.4-9)

式 (12.4-8) 称为 Doeblin 条件：每个起点经过 \(m\) 步后的分布，都含有同一份质量为 \(\varepsilon\) 的分量 \(\nu\)。

证明。有限链的平稳分布至少存在一个，见 12.2 节。令 \(K=P^m\)，将每行写成 \(K(i,\cdot)=\varepsilon\nu+(1-\varepsilon)R(i,\cdot)\)，其中 \(R_{ij}=(K_{ij}-\varepsilon\nu_j)/(1-\varepsilon)\) 非负且行和为 \(1\)。

构造两条按 \(K\) 转移的链，初始分布为 \(\mu\) 与 \(\pi\)。每一轮独立抛同一枚成功率 \(\varepsilon\) 的硬币；成功时让两坐标使用同一个服从 \(\nu\) 的新状态，失败时各自使用相应的 \(R\) 转移。相遇以后，在失败分支也使用相同随机选择。两边的转移行都保持为 \(K\)，而第一轮成功后必然相同。因此经过 \(k\) 轮尚未相遇的概率至多为 \((1-\varepsilon)^k\)，耦合不等式给出 \(n=km\) 时的界。

写 \(n=km+r\)，其中 \(0\le r<m\)，再用式 (12.4-7) 及 \(\pi P^r=\pi\)，便得一般 \(n\) 的结论。如果 \(\widetilde\pi\) 也是平稳分布，以它作为 \(\mu\)，令 \(n\to\infty\) 即得 \(\widetilde\pi=\pi\)。若式 (12.4-8) 可取 \(\varepsilon=1\)，则 \(P^m\) 所有行相同，经过 \(m\) 步便精确达到平稳。

有限不可约非周期链必满足这一条件。下面补齐其中的步数问题，不能只用“有路径”代替“有相同长度的路径”。

从非周期到统一正性。固定状态 \(a\)。其返回长度集合对加法封闭，且最大公约数为 \(1\)，因此可从中选有限个 \(r_1,\ldots,r_\ell\)，最大公约数仍为 \(1\)。由 Bézout 等式，它们的整数线性组合能表示模 \(r_1\) 的任意余数；将系数加上足够大的 \(r_1\) 可变成非负数而不改变余数。于是每个余数 \(u\) 都有一个可实现的非负组合 \(b_u\)。取 \(B\ge1+\max_u b_u\)，每个 \(n\ge B\) 都等于相应的 \(b_u\) 加上非负整数倍 \(r_1\)，故 \(p^{(n)}_{aa}>0\)。

不可约性给出从各点 \(i\) 到 \(a\)、再从 \(a\) 到各点 \(j\) 的有限路径。状态数有限，所以可取统一的大整数 \(m\)，使这两段路径之间能插入长度至少 \(B\) 的返回路径，得到 \((P^m)_{ij}>0\) 对所有 \(i,j\) 成立。若 \(|S|=s\)、\(\eta=\min_{i,j}(P^m)_{ij}>0\)，取均匀 \(\nu\) 与 \(\varepsilon=s\eta/2\in(0,1)\)，即得式 (12.4-8)。

对 \(0<\delta<1\)，定义混合时间 \(t_{\mathrm{mix}}(\delta)=\min\{n\in\mathbb N_0:\sup_\mu\|\mu P^n-\pi\|_{\mathrm{TV}}\le\delta\}\)。由几何界立即得到

\[ t_{\mathrm{mix}}(\delta) \le m\left\lceil\frac{\log\delta}{\log(1-\varepsilon)}\right\rceil. \]

(12.4-10)

例 12.4-2 · 保留状态或重新采样

取 \(\pi=(1/2,1/3,1/6)\)，设 \(J_{ij}=\pi_j\)，并令 \(P=\frac34I+\frac14J\)。每步以 \(3/4\) 保留当前状态，以 \(1/4\) 按 \(\pi\) 重新采样；例如第 \(0\) 行为 \((7/8,1/12,1/24)\)。由于 \(J^2=J\)，归纳相乘可得

\[ P^n=\left(\frac34\right)^n I+ \left[1-\left(\frac34\right)^n\right]J,\qquad \|\mu P^n-\pi\|_{\mathrm{TV}} =\left(\frac34\right)^n\|\mu-\pi\|_{\mathrm{TV}}. \]

(12.4-11)

该链满足 \(m=1,\varepsilon=1/4,\nu=\pi\) 的 Doeblin 条件；非对角流量为 \(\pi_i\pi_j/4\)，故也可逆。从状态 \(0\) 出发，精确误差为 \(\frac12(3/4)^n\)，在 \(n=13\) 时约 \(0.011879\)，在 \(n=14\) 时约 \(0.008909\)，所以达到 \(0.01\) 首次需要 \(14\) 步。

若要求所有起点统一达到该精度，最大初始距离为 \(1-\min_i\pi_i=5/6\)，精确混合时间是 \(16\) 步。式 (12.4-10) 给出 \(17\) 步，虽非最紧，却无须逐个计算转移矩阵的幂。

图 12.4-2 · 例 12.4-2 的精确离散数值，连线仅供阅读。绿色曲线对应固定起点，紫色上界适用于任意起点；前者在第 \(14\) 步首次低于 \(0.01\)，后者在第 \(17\) 步保证达到这一精度。

12.4.5 可数正常返链的遍历平均

定理 12.4-3 · 马尔可夫链强大数定律

设可数状态链不可约、正常返，唯一平稳分布为 \(\pi\)。若 \(f:S\to\mathbb R\) 满足 \(\pi|f|:=\sum_i\pi_i|f(i)|<\infty\)，则对任意初始分布 \(\mu\)，

\[ \overline f_n:=\frac1n\sum_{t=0}^{n-1}f(X_t) \longrightarrow\pi f:=\sum_i\pi_if(i) \qquad\mathbb P_\mu\text{-几乎必然}. \]

(12.4-12)

结论不要求非周期，也不要求可逆。这里的对象是同一条路径的时间平均。

第一步：返回区段及其可积性。固定状态 \(a\)，令 \(\tau_0=\inf\{t\ge0:X_t=a\}\)，\(\tau_k=\inf\{t>\tau_{k-1}:X_t=a\}\)。不可约常返性保证这些停时几乎必然有限。由强马尔可夫性，给定 \(\mathcal F_{\tau_{k-1}}\) 后，下一条首次返回路径 \(a=i_0,i_1,\ldots,i_r=a\)（中间状态均非 \(a\)）的条件概率为 \(\prod_{\ell=0}^{r-1}p_{i_\ell i_{\ell+1}}\)，与此前信息无关。这些有限状态串构成可数集合，并穷尽几乎必然有限的返回区段，故各完整区段相互独立、同分布。置

\[ L_k=\tau_k-\tau_{k-1},\qquad R_k=\sum_{t=\tau_{k-1}}^{\tau_k-1}f(X_t),\qquad A_k=\sum_{t=\tau_{k-1}}^{\tau_k-1}|f(X_t)|,\quad k\ge1. \]

(12.4-13)

由正常返性，\(m=\mathbb E_aT_a^+\) 有限且 \(m\ge1\)。12.2 节已证明一次返回前的占用期望为 \(m\pi_i\)，故先用 Tonelli 处理绝对值，再分正负部分，可得

\[ \mathbb E L_1=m,\qquad \mathbb E A_1=m\pi|f|<\infty,\qquad \mathbb E R_1=m\pi f. \]

(12.4-14)

第二步：完整区段。独立同分布可积强大数定律给出 \(\tau_k/k\to m\) 与 \(k^{-1}\sum_{\ell=1}^kR_\ell\to m\pi f\)。对 \(n\ge\tau_0\)，记 \(N(n)=\max\{k\ge0:\tau_k\le n\}\)。从 \(\tau_{N(n)}\le n<\tau_{N(n)+1}\) 夹逼，得到 \(N(n)/n\to1/m\)，于是完整区段的奖励和除以 \(n\) 趋于 \(\pi f\)。

第三步：尚未完成的末段。末段的绝对奖励不超过 \(A_{N(n)+1}\)。对任意 \(\eta>0\)，

\[ \sum_{k=1}^{\infty}\mathbb P(A_k>\eta k) =\sum_{k=1}^{\infty}\mathbb P(A_1>\eta k) \le\frac{\mathbb E A_1}{\eta}<\infty. \]

(12.4-15)

第一条 Borel–Cantelli 引理并对正有理 \(\eta\) 取可数交，给出 \(A_k/k\to0\) 几乎必然。因此 \(A_{N(n)+1}/n=[A_{N(n)+1}/(N(n)+1)]\,[(N(n)+1)/n]\to0\)。首次到达 \(\tau_0\) 之前只有几乎必然有限项，其和除以 \(n\) 也趋于零。将初段、完整区段、末段相加，式 (12.4-12) 得证。

上述论证展开了本节需要的更新奖励方法：区段长度均值有限，区段绝对奖励均值有限，两者缺一便不能照搬证明。它给出任意初始分布下的几乎必然收敛；并未据此声称任意起点下还自动有 \(L^1\) 收敛。

12.4.6 周期与蒙特卡洛估计

两状态确定性交替链 \(P=\left(\begin{smallmatrix}0&1\\1&0\end{smallmatrix}\right)\) 可逆且正常返，平稳分布为 \((1/2,1/2)\)。从 \(0\) 出发，逐时分布始终在两个点质量间交替，总变差距离恒为 \(1/2\)；但前 \(n\) 项中状态 \(0\) 出现 \(\lceil n/2\rceil\) 次，占用比例仍趋于 \(1/2\)。非周期性用于消除逐时分布的振荡，时间平均已经同时计入了周期中的各个阶段。

马尔可夫链蒙特卡洛（Markov chain Monte Carlo，MCMC）通过构造以目标分布为平稳分布的链，估计 \(\pi f\)。详细平衡是一种可检验的构造方法。在可数空间上，归一化的平稳概率与不可约性由 12.2 节保证正常返；再核查 \(\pi|f|<\infty\)，便可应用式 (12.4-12)。可约链可能一直留在某个闭类，时间平均便受起点影响。

样本相关性不会否定这个强大数结论，但会影响误差。在平稳起点且 \(f\in L^2(\pi)\) 时，令 \(\gamma_h=\operatorname{Cov}_\pi(f(X_0),f(X_h))\)。把方差的双重求和按时间差分组，得到

\[ \operatorname{Var}_\pi(\overline f_n) =\frac1{n^2}\left[n\gamma_0+ 2\sum_{h=1}^{n-1}(n-h)\gamma_h\right]. \]

(12.4-16)

因此不能仅凭平稳分布的方差套用独立样本误差公式。一般可数链的中心极限定理还需要额外条件，本节的遍历平均定理只负责一致性。

12.4.7 习题与解答

习题 12.4-1 · 求平稳分布与逆向核

三个状态以 \(1/2\) 概率停留、以 \(1/2\) 概率沿 \(0\to1\to2\to0\) 移动。求平稳分布与平稳起点时的逆向转移，判断详细平衡、逐时分布收敛及时间平均定理各自是否成立。

解

每列之和为 \(1\)，所以 \(\pi=(1/3,1/3,1/3)\) 平稳；不可约性保证唯一。因为 \(\pi_i\) 相同，\(P^*=P^{\mathsf T}\)：逆向链以 \(1/2\) 停留，以 \(1/2\) 沿反方向移动。正向 \(0\to1\) 流量为 \(1/6\)，反向流量为零，所以不满足详细平衡。链有限、不可约且有自环，由第 12.4.4 小节从任意初始分布都有总变差收敛。任意实函数在有限空间上可积，第 12.4.5 小节也保证时间平均几乎必然趋于其均匀平均值。不可逆没有破坏这两种结论。

习题 12.4-2 · 构造达到下界的耦合

在 \(\{0,1,2\}\) 上取 \(\mu=(0.6,0.3,0.1)\)、\(\nu=(0.2,0.5,0.3)\)。求总变差距离，并构造一个耦合使 \(\mathbb P(U\ne V)\) 等于该距离。

解

距离为 \(\frac12(0.4+0.2+0.2)=0.4\)。先把共同质量 \(\min(\mu_i,\nu_i)\) 放在对角线上，令联合概率 \(q_{00}=0.2,q_{11}=0.3,q_{22}=0.1\)。剩下的第一边缘质量全部在 \(0\)，第二边缘分别缺少 \(0.2\) 于 \(1,2\)，故取 \(q_{01}=q_{02}=0.2\)，其余为零。逐行求和得到 \(\mu\)，逐列求和得到 \(\nu\)，而非对角总质量为 \(0.4\)。耦合不等式说明任何耦合都不能更小；这个构造因此达到最优，称为最大耦合（maximal coupling）。

习题 12.4-3 · 周期链的精确时间平均

确定性交替链从 \(0\) 出发，设 \(f(0)=a,f(1)=b\)。计算前 \(n\) 项时间平均的误差，说明为何分布不收敛仍可获得一致估计。若改成 \(P=I\)，仍选 \(\pi=(1/2,1/2)\)，同样的结论是否成立？

解

前 \(n\) 项有 \(\lceil n/2\rceil\) 个 \(a\) 与 \(\lfloor n/2\rfloor\) 个 \(b\)。当 \(n\) 为偶数，平均恰为 \((a+b)/2\)；当 \(n\) 为奇数，平均等于 \((a+b)/2+(a-b)/(2n)\)。误差至多 \(|a-b|/(2n)\)，故必趋零，而每个时刻的状态仍为确定值，分布到 \(\pi\) 的总变差距离一直为 \(1/2\)。若 \(P=I\)，两个单点都是闭类，从 \(0\) 出发始终得到 \(a\)；除非 \(a=b\)，它不等于 \(\pi f\)。后者失去的是不可约性，不能套用遍历平均定理。

习题 12.4-4 · 无需归一化常数的可逆构造

有限状态空间上给定正权重 \(w_i\)，设 \(\pi_i=w_i/Z\)、\(Z=\sum_iw_i\)。令 \(Q=(q_{ij})\) 是对称转移矩阵，且正概率边组成的图连通。对 \(i\ne j\) 定义 \(p_{ij}=q_{ij}\min\{1,w_j/w_i\}\)，并以 \(p_{ii}=1-\sum_{j\ne i}p_{ij}\) 补齐行和。证明 \(P\) 可逆，并给出保证逐时收敛的简单修改。

解

因接受概率不超过 \(1\)，非对角行和至多为 \(1\)，所以 \(P\) 是合法转移矩阵。对 \(i\ne j\)，\(\pi_ip_{ij}=Z^{-1}q_{ij}\min(w_i,w_j)=Z^{-1}q_{ji}\min(w_j,w_i)=\pi_jp_{ji}\)，对角等式自动成立。因此 \(\pi\) 平稳且 \(P\) 可逆，转移计算只需权重比，无需知道 \(Z\)。正权重使每条提议边的接受概率为正，连通性保证不可约。取惰性化矩阵 \(\widetilde P=(I+P)/2\)，它保留 \(\pi\) 与详细平衡，并令每个自环概率至少为 \(1/2\)，故有限链从任意起点都收敛到 \(\pi\)。原链及惰性化链都正常返，其时间平均均收敛到 \(\sum_iw_if(i)/Z\)。

关键术语

详细平衡: 平稳质量乘以一步转移概率，在每对状态的两个方向相等。
可逆性: 平稳起点下的有限路径与倒序路径同分布。
生灭链: 在相邻整数状态间转移，并允许停留的链。
总变差距离: 两种分布对同一事件给出的概率差的最大绝对值。
耦合: 保持各边缘分布，将随机对象放到同一联合概率模型中。
Doeblin 条件: 所有起点在固定步数后的转移分布都含有统一的正质量分量。
混合时间: 从任意初始分布出发，达到指定总变差精度所需的最少步数。
遍历平均: 沿一条路径平均函数值；本节在不可约正常返与平稳可积条件下证明其极限。
惰性化: 在原有转移之外加入固定的停留概率，以消除周期性。

参考文献

Durrett, R. (2019). Probability: Theory and Examples, 5th ed. 作者公开版本，§5.5 的可逆测度与时间逆转，§5.6 的耦合收敛、引理 5.6.5 及习题 5.6.5。后者给出可积函数强大数定律的返回区段路线，本页展开了末段控制。
Polyanskiy, Y. (2018). MIT 6.436J / 15.085J, Lecture 23: Markov Chains III，周期性、共同构造两条链及有限状态混合；本页通过式 (12.4-8) 的共同分量给出显式几何界。