平稳分布与遍历性

前置

• 离散时间马尔可夫链

平稳分布

设有限状态时齐马尔可夫链的状态空间为 $E=\{1,\dots ,K\}$，转移矩阵为行随机矩阵 $Q$。若行向量

$$\pi =({\pi }_1,\dots ,{\pi }_K)$$

满足

$${\pi }_i\ge 0,\pi 1=1,\pi Q=\pi ,$$

则称 $\pi$ 为 $Q$ 的平稳分布（stationary distribution）。若链的初始分布是 ${\nu }_0$，则 ${\nu }_n={\nu }_0{Q}^n$；因此 ${\nu }_0=\pi$ 时，每个时刻的边缘分布都等于 $\pi$。

平稳分布与平稳过程不是同一个概念

随机过程 $(X_n{)}_{n\ge 0}$ 称为严格平稳过程，如果对任意 $m\ge 1$、任意 $0\le n_1<\cdots <n_m$ 和任意平移 $r\ge 0$，

$$(X_{n_1},\dots ,X_{n_m})\stackrel{d}{=}(X_{n_1+r},\dots ,X_{n_m+r}).$$

“$Q$ 有平稳分布”是转移机制的性质；“$(X_n)$ 是平稳过程”还取决于初始分布。对时齐马尔可夫链，若 $X_0\sim \pi$ 且 $\pi Q=\pi$，则

$$\mathbb{P}(X_0=i_0,\dots ,X_m=i_m)={\pi }_{i_0}{Q}_{i_0{i}_1}\cdots Q_{i_{m-1}{i}_m},$$

从任意时刻开始都有同一表达式，所以整个过程严格平稳。反之，若该马尔可夫链严格平稳，其共同单时刻边缘分布 $\pi$ 必满足 $\pi Q=\pi$。仅仅知道 $Q$ 存在平稳分布，并不能推出从任意 ${\nu }_0$ 出发的链已经平稳。

可达、不可约与周期

若存在 $n\ge 0$ 使 $(Q^n{)}_{ij}>0$，则称 $j$ 可由 $i$ 到达，记作 $i\to j$。若任意 $i,j\in E$ 都满足 $i\to j$ 且 $j\to i$，则称链不可约。对不同状态，所需的步数自动满足 $n\ge 1$。

对状态 $i$，定义

$$d(i):=\gcd \{n\ge 1:(Q^n{)}_{ii}>0\}.$$

它是所有可能返回步数的最大公约数，称为状态 $i$ 的周期。若 $d(i)=1$，则 $i$ 非周期；若 $d(i)>1$，则 $i$ 是周期状态。

在不可约有限链中，每个状态都能返回，而且所有状态周期相同。事实上，若 $(Q^r{)}_{ij}>0$、$(Q^s{)}_{ji}>0$，则 $i$ 的任意返回回路可以与这两段路径拼接成 $j$ 的返回回路，反向亦然；由这些回路长度的整除关系可得 $d(i)=d(j)$。共同周期记为 $d$；$d=1$ 时称链非周期。

周期会阻止逐时刻分布收敛。例如二状态交替链

$$Q=\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)$$

不可约且有唯一平稳分布 $(1/2,1/2)$，但从状态 $1$ 出发的分布在两个点质量之间振荡。

有限状态链平稳分布的存在性

命题。 每个有限状态行随机矩阵 $Q$ 都至少有一个平稳分布。

证明。 因为

$$Q1=1,$$

$1$ 是 $Q$ 的右特征值，也就是 $Q^{\top }$ 的特征值。故存在非零实行向量 $\mathbf{v}$ 满足

$$\mathbf{v}Q=\mathbf{v}.$$

对第 $j$ 个分量使用三角不等式和 $Q_{ij}\ge 0$：

$$|v_j|=\left|\sum _{i=1}^K{v}_i{Q}_{ij}\right|\le \sum _{i=1}^K|v_i|Q_{ij}.$$

因此逐分量有

$$|\mathbf{v}|\le |\mathbf{v}|Q.$$

两边右乘 $1$，利用 $Q1=1$，得到

$$|\mathbf{v}|1\le |\mathbf{v}|Q1=|\mathbf{v}|1.$$

上面的逐分量差均非负而其总和为零，所以每个分量都取等号：

$$|\mathbf{v}|Q=|\mathbf{v}|.$$

令 ${\mathbf{v}}^{+}=|\mathbf{v}|$。它非零、逐分量非负，而且仍是特征值 $1$ 的左特征向量。置

$$S:={\mathbf{v}}^{+}1=\sum _{i=1}^K{v}_i^{+}>0,\pi :=\frac{1}{S}{\mathbf{v}}^{+}.$$

于是

$${\pi }_i\ge 0,\pi 1=1,\pi Q=\pi .$$

故 $\pi$ 是平稳分布。$\square$

唯一性、收敛与遍历性

有限状态 Perron—Frobenius 理论给出以下精确区分。

1. 若 $Q$ 不可约，则平稳分布 $\pi$ 唯一，并且每个 ${\pi }_i>0$。
2. 若 $Q$ 不可约且非周期，则 $$Q^n⟶1\pi ,$$ 因而对任意初始行分布 ${\nu }_0$， $${\nu }_0{Q}^n⟶\pi .$$
3. 若 $Q$ 不可约但有周期，逐时刻分布不一定收敛；其 Cesàro 平均仍满足 $$\frac{1}{N}\sum _{n=0}^{N-1}{\nu }_0{Q}^n⟶\pi .$$

前两条可由 Perron—Frobenius 定理直接说明：不可约性使特征值 $1$ 的非负左特征向量在归一化后唯一；再加非周期性时，有限不可约非负矩阵是本原矩阵，除 $1$ 外的全部特征值都严格位于单位圆内。对 Jordan 标准形取幂便得到 $Q^n\to 1\pi$。周期情形会保留单位圆上的其他特征值，Cesàro 平均则消去这些非 $1$ 的振荡项。

“遍历性”还常指样本时间平均。对有限不可约链，不论是否非周期，对任意函数 $f:E\to \mathbb{R}$ 都有

$$\frac{1}{N}\sum _{n=0}^{N-1}f(X_n)\underset{N\to \infty }{\overset{\text{a.s.}}{\to }}\sum _{i=1}^K{\pi }_{i}f(i).$$

其理由是：固定一个状态作为再生点，相邻返回时刻之间的路径段在首次返回后构成独立同分布的循环；对每个循环累计 $f$ 并应用强大数定律，所得“每循环平均奖励/每循环平均长度”恰为平稳平均 ${\sum }_i{\pi }_{i}f(i)$。有限不可约性保证返回时间均值有限。周期性影响固定时刻的相位，却不影响这种长期占用比例。

因此应分别使用三个条件：不可约性保证唯一平稳分布，非周期性额外保证 ${\nu }_0{Q}^n$ 的逐步收敛，而时间平均的遍历结论在有限不可约情形已经成立。