马尔可夫链时间平均遍历定理

形式陈述

设 $(X_n)_{n\ge0}$ 是可数状态空间 $S$ 上的不可约、正常返 Markov 链，唯一平稳分布为 $\pi$ 。若 $f:S\to\mathbb R$ 满足

\sum_{x\in S}|f(x)|\pi(x)<\infty,

则对任意初始状态，以下收敛按几乎必然的意义成立：

\frac1n\sum_{k=0}^{n-1}f(X_k) \longrightarrow \sum_{x\in S}f(x)\pi(x).

特别地，取 $f=1_{\{x\}}$ 可得状态 $x$ 的经验访问频率趋于 $\pi(x)$ 。这条时间平均结论不要求非周期性。逐时刻边际分布是否趋稳是另一条Markov 链平稳收敛定理，需要额外排除周期振荡。

把返回周期化成独立样本

固定状态 $a$ 。不可约常返性保证从任一初态几乎必然首次到达 $a$ ，这之前只有有限段路径。每次回到 $a$ 后，到下一次返回前的完整路径块独立同分布：将返回时刻分解为事件“时刻等于 $m$ ”，在每个事件上应用确定时刻的 Markov 条件式，再对 $m$ 求和，便得到未来从 $a$ 重新开始且不依赖此前历史。这说明为何这里可以在随机返回时刻重启，而不只是把独立性作为直觉。

从 $a$ 出发，记 $T=T_a^+$ ，单周期占用量为

\nu(j)=\mathbb E_a\sum_{k=0}^{T-1}\mathbf1_{\{X_k=j\}}, \qquad \ell=\mathbb E_aT<\infty.

Tonelli 定理在概率测度与可数计数测度上给出 $\sum_j\nu(j)=\ell$ 。对每个 $k$ ，事件 $\{T>k\}$ 由前 $k$ 步决定，故用条件期望的一步 Markov 公式，

(\nu P)(j) =\mathbb E_a\sum_{k=0}^{T-1}P(X_k,j) =\mathbb E_a\sum_{k=0}^{T-1}\mathbf1_{\{X_{k+1}=j\}} =\nu(j).

最后一个等号来自 $X_T=X_0=a$ ，首尾贡献相消。归一化后的 $\nu/\ell$ 是平稳概率，唯一性给出 $\nu(j)=\ell\pi(j)$ 。因此对 $f\ge0$ ，单周期总观测 $R=\sum_{k=0}^{T-1}f(X_k)$ 满足 $\mathbb E_aR=\ell\sum_jf(j)\pi(j)<\infty$ 。

对各周期长度 $L_r$ 与观测和 $R_r$ 分别应用 IID 强大数律。若 $\tau_r$ 为首次到达 $a$ 之后第 $r$ 个完整周期的终点，则 $\tau_r/r\to\ell$ ，而 $r^{-1}\sum_{q=1}^rR_q\to\ell\pi(f)$ 。令 $N(n)$ 为时刻 $n$ 前完成的周期数，由 $\tau_{N(n)}\le n<\tau_{N(n)+1}$ 得 $N(n)/n\to1/\ell$ 。因为 $f\ge0$ ，截至 $n$ 的累计观测夹在前 $N(n)$ 与前 $N(n)+1$ 个完整周期总和之间，加上有限的起始段；两端除以 $n$ 都趋于 $\pi(f)$ 。一般可积 $f$ 分别对 $f^+$ 、 $f^-$ 应用此论证。这一证明没有使用非周期性。

直觉

遍历性把“沿一条长轨道观察”与“按平稳分布在全体状态上平均”连接起来。不可约性保证轨道不会永久困在互不沟通的区域，正常返性保证回访周期有有限平均长度；这些条件共同让早期状态的影响在时间平均中被稀释。这里平均的是同一条路径上前 $n$ 步的观测，不是只看第 $n$ 步位于哪里。

例子与边界

有限不可约链自动正常返，所以时间平均总成立。二状态确定性交替链 $0\leftrightarrow1$ 的平稳分布为 $(1/2,1/2)$ ，经验频率确实趋于一半，但从 $0$ 出发时 $X_n$ 的分布在两个点之间交替，说明分布收敛还需非周期性。整数上的简单对称随机游走不可约且常返，却是零常返，没有平稳概率分布，不能套用上述定理。结论是几乎必然的轨道平均，不等于各项 $f(X_n)$ 本身逐点收敛。

对至少有一条边的有限连通无向图上的随机游走，取 $f(v)=\mathbf1_{\{v=u\}}$ ，遍历定理给出访问顶点 $u$ 的长期频率为 $\deg(u)/(2|E|)$ 。二分图上的简单随机游走具有周期二，单步分布会在两侧来回振荡，但访问频率仍可收敛。这一区分解释了为什么 MCMC 常额外加入自环来消除周期性。

推论与应用

定理以Markov 链和平稳分布为对象，是依赖样本版本的大数律。不可约性与正常返性保证时间平均的标准结论。MCMC 用轨道平均估计期望，而混合时间回答有限步边缘分布距离稳态还有多远，两者不能互相替代。

同一时间平均也能解释排队系统的长期利用率、随机游走的访问比例和 PageRank 型估计。若要给有限样本误差条带，还需进一步研究自相关、中心极限定理或浓缩界；遍历定理本身只给长期极限。

若能找出访问后使整个未来重新开始的时刻，还可用再生过程把长期占用率写成单周期占用积分除以平均周期长度。这要求完整周期独立同分布及有限平均周期，不能仅凭返回同一个状态便省略再生性的证明。

参考资料

David Aldous，Markov Chains, Stat 205B lecture notes，Lecture 12 的周期占用量与非负累计观测夹逼；配合本页的一步条件期望计算。
J. R. Norris, Markov Chains, Cambridge University Press, 1997，Ch. 1, invariant distributions, recurrence and ergodic theorem。
Rick Durrett, Probability: Theory and Examples, 5th ed., Cambridge University Press, 2019，Ch. 6, Markov-chain ergodic theorems and stationary processes。

形式陈述 ​

把返回周期化成独立样本 ​

反向链接

形式陈述

把返回周期化成独立样本