12.2 常返、平稳分布与长期行为

能否返回一个状态、平均多久返回，以及每个时刻的分布是否稳定，是不同的问题。本节以可数状态马尔可夫链为对象，从访问次数判据区分常返与暂留，用返回期间的占用测度证明平稳分布与平均返回时间的关系。有限链、整数随机游走和反射生灭链展示这些条件的边界，周期二状态链则说明平稳分布存在为何仍不足以保证逐时收敛。

12.2.1 互通类与返回时间

固定有限或可数状态集 \(S\) 上的离散时间齐次马尔可夫链，转移矩阵记为 \(P=(p_{ij})\)，\(p_{ij}^{(n)}=(P^n)_{ij}\)。以 \(P_i,E_i\) 表示从 \(X_0=i\) 出发的概率与期望。转移机制与强马尔可夫性质见 12.1 节。

若某个 \(n\ge0\) 满足 \(p_{ij}^{(n)}>0\)，记 \(i\to j\)；若两个方向都可达，称 \(i,j\) 互通（communicate）。互通关系把 \(S\) 分成等价类。只有一个互通类时称链不可约（irreducible）。类 \(C\) 闭合是指从中不能一步离开，即 \(p_{ij}=0\) 对所有 \(i\in C,j\notin C\) 成立。

定义 · 常返、暂留与平均返回时间

首次到达时间与首次返回时间分别为 \(H_i=\inf\{n\ge0:X_n=i\}\)、\(T_i^+=\inf\{n\ge1:X_n=i\}\)，空集的下确界取 \(\infty\)。定义 \(f_i=P_i(T_i^+<\infty)\)、\(m_i=E_iT_i^+\)。

\(f_i=1\)：状态 \(i\) 常返（recurrent）；\(f_i<1\)：状态 \(i\) 暂留（transient）。
常返且 \(m_i<\infty\)：正常返（positive recurrent）；常返且 \(m_i=\infty\)：零常返（null recurrent）。

在 \(P_i\) 下，\(H_i=0\)，所以返回必须从 \(n=1\) 开始计时。暂留状态也有 \(m_i=\infty\)，原因是 \(T_i^+=\infty\) 具有正概率；不能仅凭“平均返回时间无穷”就称为零常返。

在不可约链中，状态的常返类型相同。对存在正时间返回可能的状态，周期定义为 \(d_i=\gcd\{n\ge1:p_{ii}^{(n)}>0\}\)，同一不可约链各点具有相同周期；\(d_i=1\) 称非周期（aperiodic）。只要不可约链中有一个 \(p_{ii}>0\)，全链就非周期，但这个条件并非必要条件。

12.2.2 访问次数判据与类性质

定理 · Green 和判据

记从时刻 \(0\) 起对 \(i\) 的总访问次数为 \(V_i=\sum_{n\ge0}\mathbf1_{\{X_n=i\}}\)。则

\[G_{ii}:=\sum_{n=0}^{\infty}p_{ii}^{(n)}=E_iV_i=\begin{cases}(1-f_i)^{-1},&f_i<1,\\\infty,&f_i=1.\end{cases}\]

(12.2-1)

因此常返等价于 \(G_{ii}=\infty\)。在 \(P_i\) 下，常返时访问次数几乎必然无穷；暂留时访问次数几乎必然有限。

证明

每次返回 \(i\) 后，由强马尔可夫性质，下一次仍能返回的概率都是 \(f_i\)。计入时刻 \(0\) 的访问，对 \(r\ge1\) 有 \(P_i(V_i\ge r)=f_i^{r-1}\)。尾和公式和 Tonelli 定理分别给出 \(E_iV_i=\sum_{r\ge1}f_i^{r-1}\) 与 \(E_iV_i=\sum_{n\ge0}p_{ii}^{(n)}\)，得到式 (12.2-1)。取 \(r\to\infty\) 也得到访问次数的两种几乎必然结论。

若 \(i\leftrightarrow j\)，取 \(r,s\) 使 \(p_{ij}^{(r)}p_{ji}^{(s)}>0\)。Chapman–Kolmogorov 公式给出 \(p_{jj}^{(s+n+r)}\ge p_{ji}^{(s)}p_{ii}^{(n)}p_{ij}^{(r)}\)。对 \(n\) 求和便知：\(i\) 常返则 \(j\) 也常返；交换二者得到类性质。

常返类一定闭合。若从常返点 \(j\) 沿一条不再经过 \(j\) 的正概率路径到达 \(i\)，而从 \(i\) 有正概率永不到达 \(j\)，拼接这两个事件就使 \(j\) 有正概率不返回，矛盾。这个论证也说明：在不可约常返链中，从任意状态到达任意指定状态的时间几乎必然有限。无限状态空间中的闭类却可能全部暂留，不能把有限链的图形判别直接照搬过来。

周期的类性质也来自路径拼接。沿上述 \(j\to i\to j\) 的路径，\(r+s\) 是 \(j\) 的可能返回步数；若 \(n\) 是 \(i\) 的可能返回步数，\(r+n+s\) 也是 \(j\) 的可能返回步数。于是 \(d_j\) 同时整除这两数，进而整除 \(n\)，故 \(d_j\mid d_i\)。反向得到 \(d_i\mid d_j\)，所以 \(d_i=d_j\)。

12.2.3 不变测度、平稳分布与 Kac 公式

定义 · 总质量是否有限

非零向量 \(\nu=(\nu_j)\)，其中 \(0\le\nu_j<\infty\)，若满足 \(\nu_j=\sum_i\nu_i p_{ij}\)，称为不变测度（invariant measure）。它的总质量可以无穷。若另有 \(\sum_j\nu_j=1\)，则称为平稳分布（stationary distribution），通常记为 \(\pi\)。从 \(\pi\) 出发时，各时刻的边缘分布都为 \(\pi\)。

定理 · 可数不可约链的平稳分布判据

对可数不可约链，某个状态正常返、所有状态正常返、存在平稳分布这三个条件等价。此时平稳分布唯一，且每个 \(\pi_i>0\)，满足平均返回时间公式

\[\pi_i=\frac1{E_iT_i^+}=\frac1{m_i}.\]

(12.2-2)

这是单个状态形式的 Kac 公式。该结论不要求非周期。参见文献 [1] 定理 5.5.7、5.5.10–5.5.12。

第一步 · 一次返回前的访问次数给出不变测度

固定常返点 \(i\)，令 \(T=T_i^+\)，定义 \(\nu_j=E_i\sum_{n=0}^{T-1}\mathbf1_{\{X_n=j\}}\)。因为 \(T<\infty\) 几乎必然，起点和终点都是 \(i\)。由非负求和与条件期望，

\[(\nu P)_j=E_i\sum_{n=0}^{T-1}p_{X_nj}=E_i\sum_{n=1}^{T}\mathbf1_{\{X_n=j\}}=E_i\sum_{n=0}^{T-1}\mathbf1_{\{X_n=j\}}=\nu_j.\]

(12.2-3)

最后一步是逐路径计数：删去最初的 \(i\)，加入最后的 \(i\)，各状态次数不变。还可核实每个 \(\nu_j\) 有限：\(\nu_i=1\)，而不可约性给出某个 \(r\) 使 \(p_{ji}^{(r)}>0\)，故 \(1=(\nu P^r)_i\ge\nu_jp_{ji}^{(r)}\)。同时 \(\sum_j\nu_j=E_iT=m_i\)。若 \(m_i<\infty\)，归一化 \(\nu/m_i\) 即得平稳分布。

第二步 · 平稳概率排除暂留

反过来，设已有平稳分布 \(\pi\)。先取一个 \(\pi_k>0\) 的点，再沿正概率路径使用 \(\pi=\pi P^r\)，即得所有 \(\pi_i>0\)。若 \(i\) 暂留，从任意 \(k\) 出发，首次到达 \(i\) 后的期望总访问次数为 \(G_{ii}\)，故 \(G_{ki}=P_k(H_i<\infty)G_{ii}\le G_{ii}<\infty\)。但平稳性和 Tonelli 定理要求

\[\sum_k\pi_kG_{ki}=\sum_{n=0}^{\infty}\sum_k\pi_kp_{ki}^{(n)}=\sum_{n=0}^{\infty}\pi_i=\infty,\]

(12.2-4)

与左侧不超过 \(G_{ii}\) 矛盾。因此全链常返。

第三步 · 平稳路径上的尾概率求和

在初始分布为 \(\pi\) 的链上，令 \(a_n=P_\pi(X_0\ne i,\ldots,X_n\ne i)\)。对 \(n\ge1\)，平稳性给出 \(\pi_iP_i(T_i^+>n)=a_{n-1}-a_n\)：右侧正是 \(X_0=i\)、随后 \(n\) 步都不在 \(i\) 的概率。加上 \(n=0\) 项后望远镜求和，得到

\[\pi_i m_i=\pi_i+\sum_{n=1}^{\infty}(a_{n-1}-a_n)=\pi_i+a_0-\lim_na_n=1.\]

(12.2-5)

最后使用不可约常返链从任一点最终到达 \(i\)，故 \(a_n\downarrow0\)。于是每个 \(m_i=1/\pi_i<\infty\)，且所有平稳分布的每个坐标都由返回时间唯一确定。这同时完成正常返的等价性、唯一性与式 (12.2-2) 的证明。平稳路径求和的论证也可对照文献 [2]。

12.2.4 有限链：存在唯一与周期反例

定理 · 有限不可约链必正常返

有限状态链至少有一个平稳分布；若再不可约，则平稳分布唯一且各状态正常返。

证明 · 对分布作时间平均

任取初始分布 \(\alpha\)，置 \(\mu_N=N^{-1}\sum_{n=0}^{N-1}\alpha P^n\)。有限维概率单纯形紧，故有子列 \(\mu_{N_r}\to\pi\)。另一方面，\(\mu_NP-\mu_N=(\alpha P^N-\alpha)/N\to0\)，在子列极限中得到 \(\pi P=\pi\)。不可约时再应用上一小节的定理。这里有限性保证极限仍有总质量 \(1\)；无限状态链的逐点极限可能把全部质量丢失。

例 1 · 两状态链：平稳与逐时极限分别计算

对 \(0<a,b\le1\)，取状态 \(S=\{0,1\}\) 及转移矩阵

\[P=\begin{pmatrix}1-a&a\\b&1-b\end{pmatrix},\qquad \pi=\left(\frac b{a+b},\frac a{a+b}\right),\qquad m_0=\frac{a+b}{b},\quad m_1=\frac{a+b}{a}.\]

(12.2-6)

平稳方程为 \(\pi_0a=\pi_1b\)，再加归一化即可解出 \(\pi\)；平均返回时间由 Kac 公式给出。从 \(0\) 出发，记 \(u_n=P_0(X_n=0)\)。递推 \(u_{n+1}=b+(1-a-b)u_n\)、\(u_0=1\) 给出

\[u_n=\frac b{a+b}+\frac a{a+b}(1-a-b)^n.\]

(12.2-7)

当 \(a=b=1\) 时，链每步必换状态，周期为 \(2\)，\(u_{2n}=1,u_{2n+1}=0\)，尽管 \(\pi=(1/2,1/2)\) 唯一，仍无逐时极限。若至少一个参数小于 \(1\)，链有自环且非周期，\(|1-a-b|<1\)，于是 \(u_n\to\pi_0\)。无论周期如何，若一开始按 \(\pi\) 抽取状态，每个时刻的分布都已是 \(\pi\)。

图 12.2-1 · 根据式 (12.2-7) 绘制 \(P_0(X_n=0)\) 的精确离散数值，连线仅便于识别相邻时刻。两条链的平稳概率均为 \(1/2\)，虚线标出这一水平；橙色链始终振荡。

12.2.5 无限状态的边界：随机游走与生灭链

例 2 · 整数上的简单随机游走

在 \(\mathbb Z\) 上，每步以概率 \(p\in(0,1)\) 向右、以 \(q=1-p\) 向左。链不可约，周期为 \(2\)。奇数时刻不能回到原点，偶数时刻则有 \(p_{00}^{(2n)}=\binom{2n}{n}(pq)^n\)。

若 \(p=q=1/2\)，Stirling 公式给出 \(p_{00}^{(2n)}\sim1/\sqrt{\pi n}\)，其和发散，所以常返。若存在平稳概率，则 \(\pi_j=(\pi_{j-1}+\pi_{j+1})/2\)，意味着相邻差 \(\pi_{j+1}-\pi_j\) 为常数；在整条 \(\mathbb Z\) 上非负迫使该常数为零，剩下的常数序列无法归一化。由第 12.2.3 小节的判据，它是零常返链。

若 \(p\ne q\)，则 \(p_{00}^{(2n)}\le(4pq)^n\)，而 \(4pq<1\)，故 Green 和有限，链暂留。对所有这些参数，计数测度 \(\nu_j=1\) 都满足 \(\nu P=\nu\)，但总质量无穷。因此不变测度存在，既不保证存在平稳概率，也不保证常返。

例 3 · 在零点反射的生灭链

改取 \(S=\{0,1,2,\ldots\}\)。对 \(n\ge1\)，令 \(p_{n,n+1}=p,\ p_{n,n-1}=q=1-p\)，而 \(p_{0,1}=p,\ p_{0,0}=q\)，其中 \(0<p<1\)。这条链不可约且非周期。平稳方程从边界给出 \(\nu_0p=\nu_1q\)，其余方程使 \(\nu_np-\nu_{n+1}q\) 保持为零，故 \(\nu_n=\nu_0\rho^n\)，其中 \(\rho=p/q\)。这一模型及其平稳方程见文献 [3] §2。

若 \(p<q\)，几何级数可归一化，所以链正常返，且

\[\pi_n=(1-\rho)\rho^n,\qquad E_0T_0^+=\frac1{\pi_0}=\frac q{q-p}.\]

(12.2-8)

要区分另两种情形，考察从 \(1\le i<N\) 出发先到达 \(0\) 还是 \(N\)。令 \(h_i^{(N)}=P_i(H_0<H_N)\)，首步分解给出 \(h_i=ph_{i+1}+qh_{i-1}\)，边界为 \(h_0=1,h_N=0\)。相邻差满足 \(h_{i+1}-h_i=(q/p)(h_i-h_{i-1})\)，求和得

\[h_i^{(N)}=\begin{cases}\displaystyle\frac{(q/p)^i-(q/p)^N}{1-(q/p)^N},&p\ne q,\\1-i/N,&p=q.\end{cases}\]

(12.2-9)

事件 \(\{H_0<H_N\}\) 随 \(N\) 增大趋于 \(\{H_0<\infty\}\)：有限时间到达 \(0\) 的路径只访问有限高度。于是 \(p=q\) 时从任意 \(i\) 都必到达 \(0\)，链常返，但几何权重无法归一化，故零常返。若 \(p>q\)，则 \(P_1(H_0<\infty)=q/p\)，从 \(0\) 出发的返回概率为 \(f_0=q+p(q/p)=2q<1\)，链暂留。非周期条件在三种情形都成立，不能代替正常返条件。

图 12.2-2 · 上图为例 3 的转移机制，边界处向左的一步变成自环。下图给出 \(p=1/3,q=2/3\) 时 \(\pi_n=2^{-n-1}\) 的前五项；柱高按概率同比例绘制，其余项仍有正质量。

12.2.6 时间平均与逐时分布收敛

定理 · 两种长期结论的条件

设可数链不可约、正常返，平稳分布为 \(\pi\)。对任意初始分布、每个固定状态 \(j\)，

\[\frac1N\sum_{n=0}^{N-1}\mathbf1_{\{X_n=j\}}\longrightarrow\pi_j\quad\text{几乎必然},\qquad \frac1N\sum_{n=0}^{N-1}p_{ij}^{(n)}\longrightarrow\pi_j.\]

(12.2-10)

这两项时间平均结论不要求非周期。如果再加非周期，则任意初始分布 \(\alpha\) 都满足

\[\|\alpha P^n-\pi\|_{\mathrm{TV}}:=\frac12\sum_{j\in S}|(\alpha P^n)_j-\pi_j|\longrightarrow0.\]

(12.2-11)

时间平均的证明

从 \(j\) 出发，连续返回 \(j\) 之间的时间 \(\tau_1,\tau_2,\ldots\) 独立同分布，均值为 \(m_j<\infty\)。令 \(R_r=\tau_1+\cdots+\tau_r\)，由强大数定律，\(R_r/r\to m_j\)。截至 \(N\) 的返回次数 \(K_N\) 满足 \(R_{K_N}\le N<R_{K_N+1}\)，故 \(K_N/N\to1/m_j=\pi_j\)。从任意其他状态出发，首次到达 \(j\) 的时间几乎必然有限，删去这段有限前缀不改变极限。访问频率介于 \(0,1\) 之间，控制收敛再给出期望形式的时间平均。

逐时收敛的证明思路与省略范围

不可约且非周期保证对任意两点，充分大的步数都有正概率连通。于是两条独立链组成的乘积链不可约，且有平稳分布 \(\pi\otimes\pi\)，由前面的判据可知它正常返，因而两坐标几乎必然在有限时间相遇。让一条从 \(\alpha\) 出发、另一条从 \(\pi\) 出发，并在相遇后使用相同转移，可得总变差距离不超过“截至 \(n\) 尚未相遇”的概率，后者趋于零。返回步数的数论引理及这一耦合构造的细节不在本页展开，完整证明见文献 [1] 引理 5.6.5、定理 5.6.6，耦合方法另见 12.4 节。

不可约零常返链虽会无限次访问每个状态，对每个固定状态的访问频率却为零。对返回间隔先作 \(\tau_r\wedge L\) 截断，由强大数定律得 \(\liminf R_r/r\ge E(\tau_1\wedge L)\)；令 \(L\uparrow\infty\) 得 \(R_r/r\to\infty\)，从而 \(K_N/N\to0\)。无限次返回与零时间比例可以同时成立。

12.2.7 习题与详解

习题 12.2-1 · 有限可约链的平稳分布为何不唯一？

在 \(S=\{0,1,2\}\) 上，设 \(p_{00}=p_{01}=1/2,\ p_{11}=p_{22}=1\)，其余转移为零。分类各状态，求全部平稳分布，并求从 \(0\) 出发的分布极限。

解

互通类为三个单点，\(\{1\},\{2\}\) 闭合。状态 \(0\) 一旦转到 \(1\) 就不再返回，故 \(f_0=1/2\)，是暂留状态，且 \(E_0T_0^+=\infty\)。状态 \(1,2\) 吸收，返回时间恒为 \(1\)，均正常返。

平稳方程要求 \(\pi_0=\pi_0/2\)，故全部解为 \((0,t,1-t)\)，\(0\le t\le1\)。从 \(0\) 出发，时刻 \(n\) 的分布是 \((2^{-n},1-2^{-n},0)\)，趋于 \((0,1,0)\)；从 \(2\) 出发始终为 \((0,0,1)\)。有限性保证存在，不保证唯一或各初始分布具有同一极限。

习题 12.2-2 · 两状态链的返回时间与收敛误差

在例 1 中取 \(a=1/3,b=1/2\)，计算平稳分布、两状态的平均返回时间，以及从 \(0\) 出发与平稳分布的总变差距离。距离首次不超过 \(10^{-3}\) 是第几步？

解

\(a+b=5/6\)，故 \(\pi=(3/5,2/5)\)，\(m_0=5/3,\ m_1=5/2\)。递推的另一特征因子为 \(1-a-b=1/6\)，所以 \(P_0(X_n=0)=3/5+(2/5)6^{-n}\)。

两点概率向量的总变差距离等于任一坐标差的绝对值，因此距离为 \((2/5)6^{-n}\)。第 \(3\) 步为 \(1/540>10^{-3}\)，第 \(4\) 步为 \(1/3240<10^{-3}\)，首次满足条件的是第 \(4\) 步。

习题 12.2-3 · 同一生灭机制的两侧参数

在例 3 中先取 \(p=2/5,q=3/5\)，求 \(\pi_2\)、\(E_0T_0^+\)、\(E_2T_2^+\) 与 \(P_\pi(X_0\ge5)\)。再交换 \(p,q\)，求从 \(0\) 出发的返回概率和总访问次数的期望。

解

第一种情形 \(\rho=2/3\)，所以 \(\pi_n=(1/3)(2/3)^n\)，\(\pi_2=4/27\)。Kac 公式给出 \(E_0T_0^+=3\)、\(E_2T_2^+=27/4\)。几何尾和为 \(P_\pi(X_0\ge5)=(2/3)^5=32/243\)。

交换后 \(p=3/5,q=2/5\)。从 \(1\) 命中 \(0\) 的概率是 \(q/p=2/3\)，故 \(f_0=q+p(q/p)=4/5\)。由访问次数判据，计入初始时刻的期望总访问次数为 \(G_{00}=1/(1-f_0)=5\)，链暂留。形式权重 \((3/2)^n\) 不能归一化为平稳概率。

习题 12.2-4 · Kac 公式中的不可约条件

设两状态链的转移矩阵为单位矩阵，选平稳分布 \(\pi=(1/3,2/3)\)。核查 \(m_i=1/\pi_i\) 是否成立。再设一般链有闭合不可约类 \(C\)，平稳分布满足 \(\pi(C)>0\)，推导该类内正确的返回时间关系。

解

两状态都吸收，故 \(m_0=m_1=1\)，而 \(1/\pi_0=3,\ 1/\pi_1=3/2\)。直接套用全链不可约时的公式会出错。

闭合性使类内质量无法向外流出。由平稳性，类外流入 \(C\) 的总质量也为零；因此限制并归一化后的 \(\widehat\pi_i=\pi_i/\pi(C)\)，\(i\in C\)，是类内链的平稳分布。对这个不可约链使用已证定理，得到 \(m_i=1/\widehat\pi_i=\pi(C)/\pi_i\)。吸收单点类中 \(\pi(C)=\pi_i\)，便恢复 \(m_i=1\)。

关键术语

互通类：彼此可沿正概率路径到达的状态所组成的等价类。
闭类：进入后不能转移到类外的互通类。
常返与暂留：从某点出发，最终返回该点的概率分别等于或小于 \(1\)。
正常返与零常返：常返状态的平均返回时间分别有限或无穷。
不变测度：满足 \(\nu P=\nu\)、总质量允许无穷的测度。
平稳分布：总质量为 \(1\) 的不变测度。
Kac 公式：不可约正常返链中，平稳概率等于平均返回时间的倒数。
周期：所有可能正返回步数的最大公约数。
总变差距离：可数状态概率向量之间差的绝对值之和的一半。

参考文献与延伸阅读

Durrett, R. (2019). Probability: Theory and Examples, 5th ed. §5.3 讨论访问次数与常返；§5.5 的定理 5.5.7、5.5.10–5.5.12 给出返回占用测度及正常返判据；§5.6 的定理 5.6.1、5.6.6 分别处理访问频率与非周期收敛。Duke University 作者版 PDF。
Polyanskiy, Y. (2018). Fundamentals of Probability, MIT 6.436J / 15.085J, Lecture 22, “Markov Chains II”。有限链平稳分布的返回时间表示与平稳路径上的尾概率求和证明。MIT 官方讲义 22。
Polyanskiy, Y. (2018). 同一课程 Lecture 24, “Infinite Markov Chains; Continuous Time Markov Chains”，§2 讨论无限状态链的返回概率定义及零点反射随机游走的平稳方程。MIT 官方讲义 24。