有限状态离散时间时齐马尔可夫链(FSDTMC)

转移矩阵与边缘演化

设时间 $n\in {\mathbb{Z}}_{\ge 0}$，状态空间为有限集 $E=\{1,\dots ,K\}$，自然信息流为 ${\mathcal{F}}_n^X:=\sigma (X_0,\dots ,X_n)$。随机过程 $(X_n{)}_{n\ge 0}$ 称为时齐有限状态离散时间马尔可夫链（FSDTMC），如果存在矩阵 $Q=(Q_{ij}{)}_{K\times K}$，使得对任意 $n\in {\mathbb{Z}}_{\ge 0}$ 与 $j\in E$，

$$\mathbb{P}(X_{n+1}=j\mid {\mathcal{F}}_n^X)=\mathbb{P}(X_{n+1}=j\mid X_n)=Q_{X_n,j}\mathbb{P}\text{-a.s.}$$

flowchart LR
    X0["$$X_0$$"] -->|"$$Q$$"| X1["$$X_1$$"]
    X1 -.-> Xnm1["$$X_{n-1}$$"]
    Xnm1 -->|"$$Q$$"| Xn["$$X_n$$"]

当 $\mathbb{P}(X_n=i)>0$ 时，$Q_{ij}=\mathbb{P}(X_{n+1}=j\mid X_n=i)$。转移矩阵 $Q$ 是行随机矩阵：

$$Q_{ij}\ge 0,\sum _{j=1}^K{Q}_{ij}=1,Q1=1,$$

其中 $1=(1,\dots ,1{)}^{\top }\in {\mathbb{R}}^K$。

由 Markov 性，有限维联合分布为

$$\mathbb{P}(X_0=i_0,\dots ,X_n=i_n)=\mathbb{P}(X_0=i_0)\prod _{k=1}^n{Q}_{i_{k-1},i_k}.$$

将时刻 $n$ 的边缘分布写成行向量 ${\nu }_n\in {\mathbb{R}}^{1\times K}$，$({\nu }_n{)}_i=\mathbb{P}(X_n=i)$。由全概率公式

$$\mathbb{P}(X_n=j)=\sum _{i=1}^K\mathbb{P}(X_{n-1}=i)Q_{ij},$$

得

$${\nu }_n={\nu }_{n-1}Q,{\nu }_n={\nu }_0{Q}^n.$$

平稳分布

记概率单纯形为

$${\Delta }_{K-1}:=\{\nu \in {\mathbb{R}}^{1\times K}:{\nu }_i\ge 0,\nu 1=1\}.$$

若行向量 $\pi \in {\Delta }_{K-1}$ 满足

$$\pi Q=\pi ,$$

则称 $\pi$ 为 $Q$ 的平稳分布。当初始分布 ${\nu }_0=\pi$ 时，对任意 $n\ge 0$ 有 ${\nu }_n=\pi Q^n=\pi$。

可达、沟通类与周期

若存在 $n\ge 0$ 使 $(Q^n{)}_{ij}>0$，称 $j$ 由 $i$ 可达，记作 $i\to j$（当 $i\ne j$ 时，因 $(Q^0{)}_{ij}=I_{ij}=0$，必有 $n\ge 1$）。若 $i\to j$ 且 $j\to i$，称 $i$ 与 $j$ 沟通，记作 $i\leftrightarrow j$。

命题。 沟通关系 $\leftrightarrow$ 是 $E$ 上的等价关系。

证明

• 自反性：对任意 $i\in E$，取 $n=0$，有 $(Q^0{)}_{ii}=I_{ii}=1>0$，故 $i\to i$，从而 $i\leftrightarrow i$。

• 对称性：若 $i\leftrightarrow j$，则 $i\to j$ 且 $j\to i$，由定义即有 $j\leftrightarrow i$。

• 传递性：设 $i\leftrightarrow j$ 且 $j\leftrightarrow k$。由 $i\to j$ 与 $j\to k$，存在 $m,n\ge 0$ 使 $(Q^m{)}_{ij}>0$ 且 $(Q^n{)}_{jk}>0$。由矩阵乘法及 $Q$ 的非负性

  $$(Q^{m+n}{)}_{ik}=\sum _{\ell =1}^K(Q^m{)}_{i\ell }(Q^n{)}_{\ell k}\ge (Q^m{)}_{ij}(Q^n{)}_{jk}>0,$$

  故 $i\to k$。同理，由 $k\to j$ 与 $j\to i$ 可得 $k\to i$。因此 $i\leftrightarrow k$。

综上，$\leftrightarrow$ 满足自反性、对称性与传递性，是 $E$ 上的等价关系。$\square$

等价关系 $\leftrightarrow$ 将 $E$ 划分为互不相交的等价类，称为沟通类。当 $E$ 只有一个沟通类时，称链不可约。

沟通类 $C$ 称为闭沟通类，如果

$$i\in C,j\notin C⟹Q_{ij}=0.$$

若存在 $j\in C$ 使 $i\to j$（由类内状态互通及传递性，这等价于对任意 $j\in C$ 均有 $i\to j$），称状态 $i$ 可到达沟通类 $C$。

命题。 有限状态链至少存在一个闭沟通类，且每个状态都能到达某个闭沟通类。

证明

任取初始状态 $y_0\in E$，记其所在的沟通类为 $C^{(0)}$。按如下方式归纳构造状态序列 $y_0,y_1,\dots$ 及其所在的沟通类 $C^{(0)},C^{(1)},\dots$：

设已得到 $y_0,y_1,\dots ,y_k$ 及沟通类 $C^{(0)},C^{(1)},\dots ,C^{(k)}$（$y_p\in C^{(p)}$），满足

$$y_0\to y_1\to \cdots \to y_k.$$

• 若 $C^{(k)}$ 是闭沟通类，则构造终止。此时由可达关系的传递性有 $y_0\to y_k\in C^{(k)}$，即 $y_0$ 可到达闭沟通类 $C^{(k)}$。
• 若 $C^{(k)}$ 不是闭沟通类，由定义知存在 $x_k\in C^{(k)}$ 与 $y_{k+1}\notin C^{(k)}$ 使 $Q_{x_k{y}_{k+1}}>0$（从而 $x_k\to y_{k+1}$）。记 $y_{k+1}$ 所在的沟通类为 $C^{(k+1)}$。因 $y_k,x_k\in C^{(k)}$，有 $y_k\to x_k$，故 $y_k\to y_{k+1}$。

下证新沟通类 $C^{(k+1)}$ 与已有的 $C^{(0)},\dots ,C^{(k)}$ 均不相同。若存在 $0\le p\le k$ 使 $C^{(k+1)}=C^{(p)}$，则 $y_{k+1}$ 与 $y_p$ 属于同一沟通类，故 $y_{k+1}\to y_p$；结合 $y_p\to \cdots \to y_k$ 得 $y_{k+1}\to y_k$。又已知 $y_k\to y_{k+1}$，故 $y_k\leftrightarrow y_{k+1}$，即 $y_{k+1}\in C^{(k)}$，与 $y_{k+1}\notin C^{(k)}$ 的选取矛盾。

因此，构造每延续一步都会产生一个新的沟通类。由于有限集 $E=\{1,\dots ,K\}$ 至多划分为 $K$ 个互不相交的沟通类，该构造至多进行 $K-1$ 步必终止于某个闭沟通类 $C^{(r)}$（$0\le r\le K-1$），且 $y_0\to y_r\in C^{(r)}$。

由 $y_0\in E$ 的任意性，每个状态都能到达某个闭沟通类；特别地，因 $E\ne \varnothing$，至少存在一个闭沟通类。$\square$

记全部闭沟通类为 $C_1,\dots ,C_m$（$m\ge 1$），其余状态构成的集合

$$T:=E\setminus \bigcup _{k=1}^m{C}_k$$

称为暂态集，$T$ 中的状态称为暂态。

对状态 $i$，若返回步数集合 $\{n\ge 1:(Q^n{)}_{ii}>0\}$ 非空，定义其周期为

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

$d(i)=1$ 时称 $i$ 非周期，$d(i)>1$ 时称 $i$ 为周期状态。在有限不可约链中，每个状态的返回步数集合都非空（$|E|=1$ 时 $Q_{11}=1$；$|E|\ge 2$ 时取 $j\ne i$，由 $i\to j\to i$ 即得正长度返回路径）。

命题。 同一沟通类中的状态具有相同的周期。

证明

设 $i\leftrightarrow j$，且 $i$ 的返回步数集合非空。取 $r,s\ge 1$ 使 $(Q^r{)}_{ij}>0$、$(Q^s{)}_{ji}>0$。因 $Q$ 的各次幂均为非负矩阵，由矩阵乘法 $Q^{s+r}=Q^s{Q}^r$ 并只保留求和中的 $k=i$ 项，得

$$(Q^{s+r}{)}_{jj}=\sum _{k=1}^K(Q^s{)}_{jk}(Q^r{)}_{kj}\ge (Q^s{)}_{ji}(Q^r{)}_{ij}>0,$$

故 $j$ 的返回步数集合非空，且 $d(j)\mid (s+r)$。对任意满足 $(Q^n{)}_{ii}>0$ 的 $n\ge 1$，由 $Q^{s+n+r}=Q^s{Q}^n{Q}^r$ 并只保留双重求和中的 $(k,\ell )=(i,i)$ 项，有

$$\begin{array}{rl}(Q^{s+n+r}{)}_{jj}& =\sum _{\ell =1}^K(Q^{s+n}{)}_{j\ell }(Q^r{)}_{\ell j}\\ & =\sum _{k=1}^K\sum _{\ell =1}^K(Q^s{)}_{jk}(Q^n{)}_{k\ell }(Q^r{)}_{\ell j}\\ & \ge (Q^s{)}_{ji}(Q^n{)}_{ii}(Q^r{)}_{ij}>0,\end{array}$$

故 $d(j)\mid (s+n+r)$。结合 $d(j)\mid (s+r)$ 得 $d(j)\mid n$。由 $n$ 的任意性知 $d(j)\mid d(i)$。交换 $i,j$ 得 $d(i)\mid d(j)$，故 $d(i)=d(j)$。$\square$

不可约链的所有状态具有共同周期 $d$；$d=1$ 时称链非周期。

例如二状态交替链

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

不可约，周期 $d=2$，由 $\pi Q=\pi$ 与 $\pi 1=1$ 得唯一平稳分布 $\pi =(1/2,1/2)$。对任意初始分布 ${\nu }_0=(a,b)$（$a,b\ge 0$，$a+b=1$），有

$${\nu }_1={\nu }_{0}Q=(a,b)\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)=(b,a),{\nu }_2={\nu }_{1}Q=(b,a)\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)=(a,b).$$

一般地，${\nu }_{2k}=(a,b)$，${\nu }_{2k+1}=(b,a)$。当 $a\ne b$ 时，${\nu }_n$ 在 $(a,b)$ 与 $(b,a)$ 之间交替，极限不存在。

平稳分布的存在性

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

证明一：左特征向量

由 $Q1=1$ 知 $\det (Q-I)=0$，从而 $\det (Q^{\top }-I)=0$。故存在非零实向量 $\mathbf{v}\in {\mathbb{R}}^{1\times K}$ 满足

$$\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}|=(|v_1|,\dots ,|v_K|)$，则逐分量有 $|\mathbf{v}|\le |\mathbf{v}|Q$。两边右乘 $1$，由 $Q1=1$ 得

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

因 $|\mathbf{v}|Q-|\mathbf{v}|$ 各分量非负且分量之和为 $0$，故

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

由 $\mathbf{v}\ne 0$ 知 $S:=|\mathbf{v}|1>0$。令 $\pi :=S^{-1}|\mathbf{v}|$，则 $\pi \in {\Delta }_{K-1}$ 且 $\pi Q=\pi$。$\square$

证明二：Cesàro 平均

任取 ${\nu }_0\in {\Delta }_{K-1}$，定义

$${\bar{\nu }}_N:=\frac{1}{N}\sum _{n=0}^{N-1}{\nu }_0{Q}^n\in {\Delta }_{K-1}.$$

右乘 $Q$ 作差：

$$\begin{array}{rl}{\bar{\nu }}_{N}Q-{\bar{\nu }}_N& =\frac{1}{N}\sum _{n=0}^{N-1}({\nu }_0{Q}^{n+1}-{\nu }_0{Q}^n)\\ & =\frac{1}{N}({\nu }_0{Q}^N-{\nu }_0).\end{array}$$

因 ${\nu }_0{Q}^N,{\nu }_0\in {\Delta }_{K-1}$，对每个分量 $j$ 有

$$|({\bar{\nu }}_{N}Q-{\bar{\nu }}_N{)}_j|=\frac{1}{N}|({\nu }_0{Q}^N{)}_j-({\nu }_0{)}_j|\le \frac{1}{N},$$

故 ${\bar{\nu }}_{N}Q-{\bar{\nu }}_N\to 0$。由于 ${\Delta }_{K-1}$ 是 ${\mathbb{R}}^{1\times K}$ 中的有界闭集（紧集），序列 $({\bar{\nu }}_N)$ 存在收敛子列 ${\bar{\nu }}_{N_k}\to \pi \in {\Delta }_{K-1}$（$k\to \infty$）。沿该子列取极限，由矩阵乘法的连续性得

$$0=\underset{k\to \infty }{\lim }({\bar{\nu }}_{N_k}Q-{\bar{\nu }}_{N_k})=\left(\underset{k\to \infty }{\lim }{\bar{\nu }}_{N_k}\right)Q-\underset{k\to \infty }{\lim }{\bar{\nu }}_{N_k}=\pi Q-\pi ,$$

即 $\pi Q=\pi$。$\square$

平稳分布的唯一性

定理。 若 $Q$ 不可约，则平稳分布 $\pi$ 唯一，并且对所有 $i\in E$ 有 ${\pi }_i>0$。

证明

平稳分布的存在性已由上一节命题保证。先证一个基本性质：若非负行向量 $\mathbf{u}\in {\mathbb{R}}^{1\times K}$（$\mathbf{u}\ge 0$）满足 $\mathbf{u}Q=\mathbf{u}$，且存在 $i\in E$ 使 $u_i>0$，则对所有 $j\in E$ 均有 $u_j>0$。事实上，由 $\mathbf{u}Q=\mathbf{u}$ 归纳可得对任意 $n\ge 0$ 有 $\mathbf{u}{Q}^n=\mathbf{u}$。对任意 $j\in E$，由不可约性（$i\to j$）存在 $n\ge 0$ 使 $(Q^n{)}_{ij}>0$。因 $\mathbf{u}$ 与 $Q^n$ 的各分量均非负，只保留求和中的 $k=i$ 项即得

$$u_j=(\mathbf{u}{Q}^n{)}_j=\sum _{k=1}^K{u}_k(Q^n{)}_{kj}\ge u_i(Q^n{)}_{ij}>0.$$

换言之，满足 $\mathbf{u}\ge 0$ 与 $\mathbf{u}Q=\mathbf{u}$ 的向量要么恒为 $0$，要么每个分量严格为正。

• 严格正性：设 $\pi \in {\Delta }_{K-1}$ 是平稳分布，则 $\pi \ge 0$ 且 $\pi Q=\pi$。由 ${\sum }_{i=1}^K{\pi }_i=1$ 知 $\pi \ne 0$，故由上述性质得对所有 $i\in E$ 有 ${\pi }_i>0$。

• 唯一性：设 $\pi ,\tilde{\pi }\in {\Delta }_{K-1}$ 均为平稳分布。由严格正性知对所有 $i\in E$ 有 ${\tilde{\pi }}_i>0$，又 $E$ 为有限集，故可定义

  $$c:=\underset{i\in E}{\max }\frac{{\pi }_i}{{\tilde{\pi }}_i}>0,\mathbf{u}:=c\tilde{\pi }-\pi .$$

  对任意 $i\in E$，由 $c\ge {\pi }_i/{\tilde{\pi }}_i$ 及 ${\tilde{\pi }}_i>0$ 知 $u_i=c{\tilde{\pi }}_i-{\pi }_i\ge 0$，即 $\mathbf{u}\ge 0$；且存在达到最大值的指标 $j\in E$ 使 $u_j=0$。同时由线性性有

  $$\mathbf{u}Q=(c\tilde{\pi }-\pi )Q=c\tilde{\pi }Q-\pi Q=c\tilde{\pi }-\pi =\mathbf{u}.$$

  若 $\mathbf{u}\ne 0$，由开头所证性质必有对所有 $i\in E$ 成立 $u_i>0$，这与 $u_j=0$ 矛盾。因此 $\mathbf{u}=0$，即 $\pi =c\tilde{\pi }$。两边右乘 $1$，由 $\pi 1=\tilde{\pi }1=1$ 得 $c=1$，故 $\pi =\tilde{\pi }$。$\square$

定理。 设闭沟通类为 $C_1,\dots ,C_m$，$T$ 为暂态集。

1. 每个 $C_k$ 上的限制子矩阵 $Q_k$ 是有限不可约行随机矩阵，有唯一且处处为正的平稳分布 ${\pi }^{(k)}$。将其在 $C_k$ 外补 $0$，得到全空间上的平稳分布 ${\tilde{\pi }}^{(k)}$。
2. $Q$ 的全体平稳分布为 $$\pi =\sum _{k=1}^m{\alpha }_k{\tilde{\pi }}^{(k)},{\alpha }_k\ge 0,\sum _{k=1}^m{\alpha }_k=1,$$ 其中系数 ${\alpha }_k={\sum }_{i\in C_k}{\pi }_i$ 由 $\pi$ 唯一确定。
3. 平稳分布唯一当且仅当 $m=1$。

证明

按 $T,C_1,\dots ,C_m$ 排列状态。因闭沟通类 $C_k$ 无流出边（$i\in C_k,j\notin C_k⟹Q_{ij}=0$），在 $C_k$ 所在行块中，除对角块 $Q_k:=(Q_{ij}{)}_{i,j\in C_k}$ 外其余块均为 $0$，转移矩阵呈分块上三角形式：

$$Q=\left(\begin{array}{ccccc}{Q}_{TT}& A_1& A_2& \cdots & A_m\\ 0& Q_1& 0& \cdots & 0\\ 0& 0& Q_2& \cdots & 0\\ ⋮& ⋮& ⋮& \ddots & ⋮\\ 0& 0& 0& \cdots & Q_m\end{array}\right),$$

其中 $Q_{TT}=(Q_{ij}{)}_{i,j\in T}$，$A_k=(Q_{ij}{)}_{i\in T,j\in C_k}$。以下依次证明定理的三项结论：

证明结论 1： 固定 $k\in \{1,\dots ,m\}$。

• $Q_k$ 是行随机矩阵：对任意 $i\in C_k$，有 $(Q_k{)}_{ij}=Q_{ij}\ge 0$（$\forall j\in C_k$）；又当 $j\notin C_k$ 时 $Q_{ij}=0$，故

  $$\sum _{j\in C_k}(Q_k{)}_{ij}=\sum _{j\in C_k}{Q}_{ij}+\sum _{j\notin C_k}{Q}_{ij}=\sum _{j\in E}{Q}_{ij}=1.$$

• $Q_k$ 不可约：由分块结构归纳可知，对任意 $n\ge 0$，$Q^n$ 在 $C_k\times C_k$ 上的子块恰为 $Q_k^n$，即 $(Q_k^n{)}_{ij}=(Q^n{)}_{ij}$（$\forall i,j\in C_k$）。因 $C_k$ 是沟通类，对任意 $i,j\in C_k$ 存在 $n\ge 0$ 使 $(Q^n{)}_{ij}>0$，从而 $(Q_k^n{)}_{ij}>0$，故 $Q_k$ 不可约。

• ${\pi }^{(k)}$ 的存在唯一性与 ${\tilde{\pi }}^{(k)}$ 的平稳性：由不可约链的唯一性定理，有限不可约行随机矩阵 $Q_k$ 存在唯一平稳分布 ${\pi }^{(k)}\in {\mathbb{R}}^{1\times |C_k|}$，满足 ${\pi }^{(k)}{Q}_k={\pi }^{(k)}$、${\pi }^{(k)}{1}_{|C_k|}=1$ 且对所有 $i\in C_k$ 有 ${\pi }_i^{(k)}>0$。定义补零行向量 ${\tilde{\pi }}^{(k)}\in {\mathbb{R}}^{1\times K}$：在分块顺序 $(T,C_1,\dots ,C_m)$ 下，其第 $k$ 个闭类分块为 ${\pi }^{(k)}$，其余分块均为 $0$，即

  $${\tilde{\pi }}^{(k)}:=(0,0,\dots ,{\pi }^{(k)},\dots ,0).$$

  显然 ${\tilde{\pi }}_i^{(k)}\ge 0$（$\forall i\in E$），且 ${\tilde{\pi }}^{(k)}1={\pi }^{(k)}{1}_{|C_k|}=1$，故 ${\tilde{\pi }}^{(k)}\in {\Delta }_{K-1}$。按分块矩阵乘法计算 ${\tilde{\pi }}^{(k)}Q$：

  • 在 $T$ 分块上为 $0Q_{TT}=0$；
  • 在 $C_{\ell }$（$\ell \ne k$）分块上为 $0A_{\ell }+0Q_{\ell }=0$；
  • 在 $C_k$ 分块上为 $0A_k+{\pi }^{(k)}{Q}_k={\pi }^{(k)}$。

  因此 ${\tilde{\pi }}^{(k)}Q={\tilde{\pi }}^{(k)}$，即 ${\tilde{\pi }}^{(k)}$ 是 $Q$ 的平稳分布。结论 1 得证。

证明结论 2： 分“必要性（任意平稳分布均可表为凸组合）”、“充分性（任意凸组合均为平稳分布）”与“系数唯一性”三步。

• 必要性：设 $\pi =(\mathbf{x},{\mathbf{y}}_1,\dots ,{\mathbf{y}}_m)\in {\Delta }_{K-1}$ 是 $Q$ 的任一平稳分布，其中 $\mathbf{x}=({\pi }_i{)}_{i\in T}$，${\mathbf{y}}_k=({\pi }_i{)}_{i\in C_k}$。展开 $\pi Q=\pi$ 得块方程组

  $$\mathbf{x}=\mathbf{x}{Q}_{TT},{\mathbf{y}}_k=\mathbf{x}{A}_k+{\mathbf{y}}_k{Q}_k(k=1,\dots ,m).$$

  先证 $\mathbf{x}=0$（若 $T=\varnothing$ 则无需此步）。设 $T\ne \varnothing$，由 $\mathbf{x}=\mathbf{x}{Q}_{TT}$ 归纳可得对任意 $n\ge 1$ 有 $\mathbf{x}=\mathbf{x}{Q}_{TT}^n$。对每个 $i\in T$，由前文命题知 $i$ 可到达某个闭类，设到达 $T^{\mathrm{c}}:={\bigcup }_{k=1}^m{C}_k$ 的最短正概率路径为 $i=i_0\to i_1\to \cdots \to i_{n_i}\in T^{\mathrm{c}}$。由最短性，$i_0,\dots ,i_{n_i-1}$ 均在 $T$ 内且两两不同，故步数满足 $1\le n_i\le |T|$，且

  $${\delta }_i:=\sum _{j\notin T}(Q^{n_i}{)}_{ij}\ge (Q^{n_i}{)}_{i,i_{n_i}}>0.$$

  取 $N:=|T|$。因闭类无返回 $T$ 的边，当 $j\notin T$ 时，第 $j$ 行的非零元全在 $T^{\mathrm{c}}$ 中，故对任意 $r\ge 0$ 有 ${\sum }_{\ell \notin T}(Q^r{)}_{j\ell }=1$。由 $Q^N=Q^{n_i}{Q}^{N-n_i}$ 得

  $$\begin{array}{rl}\sum _{\ell \notin T}(Q^N{)}_{i\ell }& =\sum _{j\in E}(Q^{n_i}{)}_{ij}\sum _{\ell \notin T}(Q^{N-n_i}{)}_{j\ell }\\ & \ge \sum _{j\notin T}(Q^{n_i}{)}_{ij}\underset{=1}{\underbrace{\sum _{\ell \notin T}(Q^{N-n_i}{)}_{j\ell }}}\\ & ={\delta }_i.\end{array}$$

  由分块上三角乘法知 $Q^N$ 的左上块恰为 $Q_{TT}^N$，故 $Q_{TT}^N$ 的第 $i$ 行和满足

  $$(Q_{TT}^N{1}_{|T|}{)}_i=\sum _{\ell \in T}(Q^N{)}_{i\ell }=1-\sum _{\ell \notin T}(Q^N{)}_{i\ell }\le 1-{\delta }_i.$$

  令 $\epsilon :={\min }_{i\in T}{\delta }_i>0$，则 $\Vert Q_{TT}^N{\Vert }_{\infty }={\max }_{i\in T}(Q_{TT}^N{1}_{|T|}{)}_i\le 1-\epsilon <1$。结合 $\mathbf{x}=\mathbf{x}{Q}_{TT}^N$ 与 $\mathbf{x}\ge 0$，两边右乘 $1_{|T|}$ 得

  $$\mathbf{x}{1}_{|T|}=\mathbf{x}{Q}_{TT}^N{1}_{|T|}=\sum _{i\in T}{x}_i(Q_{TT}^N{1}_{|T|}{)}_i\le (1-\epsilon )\mathbf{x}{1}_{|T|}.$$

  因 $\epsilon >0$ 且 $\mathbf{x}{1}_{|T|}\ge 0$，必有 $\mathbf{x}{1}_{|T|}=0$，故 $\mathbf{x}=0$。

  将 $\mathbf{x}=0$ 代入块方程组，得 ${\mathbf{y}}_k={\mathbf{y}}_k{Q}_k$（$k=1,\dots ,m$）。对每个 $k$，定义

  $${\alpha }_k:={\mathbf{y}}_k{1}_{|C_k|}=\sum _{i\in C_k}{\pi }_i\ge 0.$$
  • 若 ${\alpha }_k=0$，由 ${\mathbf{y}}_k\ge 0$ 知 ${\mathbf{y}}_k=0={\alpha }_k{\pi }^{(k)}$；
  • 若 ${\alpha }_k>0$，令 ${\hat{\mathbf{y}}}_k:={\alpha }_k^{-1}{\mathbf{y}}_k$，则 ${\hat{\mathbf{y}}}_k\ge 0$、${\hat{\mathbf{y}}}_k{1}_{|C_k|}=1$ 且 ${\hat{\mathbf{y}}}_k{Q}_k={\hat{\mathbf{y}}}_k$，即 ${\hat{\mathbf{y}}}_k$ 是 $Q_k$ 的平稳分布。由结论 1 中 ${\pi }^{(k)}$ 的唯一性得 ${\hat{\mathbf{y}}}_k={\pi }^{(k)}$，故亦有 ${\mathbf{y}}_k={\alpha }_k{\pi }^{(k)}$。

  因此

  $$\pi =(0,{\alpha }_1{\pi }^{(1)},\dots ,{\alpha }_m{\pi }^{(m)})=\sum _{k=1}^m{\alpha }_k{\tilde{\pi }}^{(k)},$$

  且由 $\pi 1=1$ 与 $\mathbf{x}=0$ 得

  $$\sum _{k=1}^m{\alpha }_k=\sum _{k=1}^m\sum _{i\in C_k}{\pi }_i+\sum _{i\in T}{\pi }_i=\sum _{i\in E}{\pi }_i=1.$$

• 充分性：任取满足 ${\alpha }_k\ge 0$ 与 ${\sum }_{k=1}^m{\alpha }_k=1$ 的系数，令 $\pi :={\sum }_{k=1}^m{\alpha }_k{\tilde{\pi }}^{(k)}$。由 ${\tilde{\pi }}^{(k)}\ge 0$ 及 ${\alpha }_k\ge 0$ 知 $\pi \ge 0$；同时

  $$\pi 1=\sum _{k=1}^m{\alpha }_k({\tilde{\pi }}^{(k)}1)=\sum _{k=1}^m{\alpha }_k=1,\pi Q=\sum _{k=1}^m{\alpha }_k({\tilde{\pi }}^{(k)}Q)=\sum _{k=1}^m{\alpha }_k{\tilde{\pi }}^{(k)}=\pi ,$$

  故 $\pi$ 是 $Q$ 的平稳分布。

• 系数唯一性：设 $\pi ={\sum }_{\ell =1}^m{\alpha }_{\ell }{\tilde{\pi }}^{(\ell )}$。因当 $i\in C_k$ 时，对所有 $\ell \ne k$ 有 ${\tilde{\pi }}_i^{(\ell )}=0$，而 ${\tilde{\pi }}_i^{(k)}={\pi }_i^{(k)}$，故在 $C_k$ 上对分量求和得

  $$\sum _{i\in C_k}{\pi }_i=\sum _{\ell =1}^m{\alpha }_{\ell }\sum _{i\in C_k}{\tilde{\pi }}_i^{(\ell )}={\alpha }_k\sum _{i\in C_k}{\pi }_i^{(k)}={\alpha }_k.$$

  因此系数 ${\alpha }_k={\sum }_{i\in C_k}{\pi }_i$ 由 $\pi$ 唯一确定。结论 2 得证。

证明结论 3：

• 充分性（$m=1⟹$ 平稳分布唯一）：若 $m=1$，由结论 2 知任意平稳分布 $\pi$ 必满足 $\pi ={\alpha }_1{\tilde{\pi }}^{(1)}$ 且 ${\alpha }_1=1$，故 $Q$ 有唯一平稳分布 ${\tilde{\pi }}^{(1)}$。
• 必要性（平稳分布唯一 $⟹m=1$）：若 $m\ge 2$，由结论 1 知 ${\tilde{\pi }}^{(1)}$ 与 ${\tilde{\pi }}^{(2)}$ 均为 $Q$ 的平稳分布。取 $i\in C_1$，因 $C_1\cap C_2=\varnothing$，有 ${\tilde{\pi }}_i^{(1)}={\pi }_i^{(1)}>0$ 而 ${\tilde{\pi }}_i^{(2)}=0$，故 ${\tilde{\pi }}^{(1)}\ne {\tilde{\pi }}^{(2)}$，平稳分布不唯一（事实上，对任意 $\alpha \in [0,1]$，$\alpha {\tilde{\pi }}^{(1)}+(1-\alpha ){\tilde{\pi }}^{(2)}$ 均为互不相同的平稳分布）。

因此平稳分布唯一当且仅当 $m=1$。结论 3 得证。$\square$

当 $m=1$ 且 $T\ne \varnothing$ 时，平稳分布唯一但在暂态上取 $0$。例如

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

中，$C_1=\{1\}$，$T=\{2\}$，唯一平稳分布为 $(1,0)$。而

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

有两个闭类 $C_1=\{1\}$、$C_2=\{2\}$，平稳分布全体为 $(\alpha ,1-\alpha )$（$0\le \alpha \le 1$）。

分布的收敛

非负方阵 $Q$ 称为本原矩阵，如果存在整数 $m\ge 1$ 使 $Q^m$ 的所有元素严格为正（记作 $Q^m>0$）。

引理。 有限不可约非周期行随机矩阵是本原矩阵。

证明

固定 $i\in E$，令 $G:=\{n\ge 1:(Q^n{)}_{ii}>0\}$。由有限不可约性知 $G$ 非空，且对加法封闭（$a,b\in G⟹a+b\in G$）。由非周期性知 $\gcd (G)=1$，故存在有限个 $g_1,\dots ,g_{\ell }\in G$ 使 $\gcd (g_1,\dots ,g_{\ell })=1$，从而存在整数 $z_1,\dots ,z_{\ell }$ 使 ${\sum }_{s=1}^{\ell }{z}_s{g}_s=1$。令

$$G_{+}:=\sum _{z_s>0}{z}_s{g}_s,G_{-}:=\sum _{z_s<0}(-z_s)g_s,$$

则 $G_{+}=G_{-}+1\ge 1$。

若 $G_{-}=0$，则 $1\in G$，从而一切正整数均属于 $G$。若 $G_{-}\ge 1$，则 $G_{+},G_{-}\in G$ 且 $G_{+}\equiv 1(\mathrm{mod}{G}_{-})$。对任意整数 $n\ge \max \{1,(G_{-}-1)G_{+}\}$，取 $r=n\mathrm{mod}{G}_{-}\in \{0,\dots ,G_{-}-1\}$，则 $r{G}_{+}\equiv n(\mathrm{mod}{G}_{-})$，且

$$n-r{G}_{+}\ge n-(G_{-}-1)G_{+}\ge 0.$$

记 $s:=(n-r{G}_{+})/G_{-}\ge 0$，则 $n=r{G}_{+}+s{G}_{-}\in G$。

因此存在 $N_i\ge 1$，使一切 $n\ge N_i$ 均满足 $(Q^n{)}_{ii}>0$。对每个 $j\in E$，取 $r_j\ge 0$ 使 $(Q^{r_j}{)}_{ij}>0$（其中 $r_i=0$），令 $R_i:={\max }_{j\in E}{r}_j$。当 $m\ge N_i+R_i$ 时，对任意 $j\in E$ 有 $m-r_j\ge N_i$，故

$$(Q^m{)}_{ij}\ge (Q^{m-r_j}{)}_{ii}(Q^{r_j}{)}_{ij}>0.$$

取 $m:={\max }_{i\in E}(N_i+R_i)$，即得 $Q^m>0$。$\square$

定理。 设 $Q$ 恰好有一个闭沟通类，且该闭类非周期，$\pi$ 为唯一平稳分布。则

$$Q^n⟶1\pi .$$

从而对任意初始分布 ${\nu }_0\in {\Delta }_{K-1}$，都有 ${\nu }_0{Q}^n\to \pi$。

证明

先设 $Q$ 不可约且非周期（即 $T=\varnothing$）。由上引理知 $Q$ 为本原矩阵。由 $Q1=1$ 及 $\Vert Q{\Vert }_{\infty }=1$ 知谱半径 $\rho (Q)=1$。由本原非负矩阵的 Perron—Frobenius 定理，特征值 $1$ 的代数重数为 $1$，且其余特征值均满足 $|\lambda |<1$。特征值 $1$ 的右特征向量为 $1$，左特征向量为 $\pi$，且 $\pi 1=1$，故对应的谱投影为 $1\pi$。对任一满足 $|\lambda |<1$ 的 $r$ 阶 Jordan 块 $J=\lambda I+N$（$N^r=0$），有

$$J^n=\sum _{s=0}^{r-1}\left(\genfrac{}{}{0ex}{}{n}{s}\right){\lambda }^{n-s}{N}^s⟶0(n\to \infty ),$$

故 $Q^n\to 1\pi$。左乘 ${\nu }_0$ 得 ${\nu }_0{Q}^n\to {\nu }_{0}1\pi =\pi$。

再设唯一闭沟通类 $C_1$ 非周期，而 $T$ 可能非空。限制矩阵 $Q_1$ 不可约且非周期，故对每个 $j\in C_1$，

$${\delta }_n:=\underset{i\in C_1}{\max }|(Q_1^n{)}_{ij}-{\pi }_j^{(1)}|⟶0.$$

由前面暂态逃逸的估计，存在 $N\ge 1$ 与 $\epsilon \in (0,1]$ 使 $\Vert Q_{TT}^N{\Vert }_{\infty }\le 1-\epsilon$，故 $\Vert Q_{TT}^{kN}{\Vert }_{\infty }\le (1-\epsilon {)}^k$，从而 $Q_{TT}^n\to 0$。当 $j\in T$ 时，${\pi }_j=0$，且对任意 $i\in E$ 有 $(Q^n{)}_{ij}\le {\mathbb{P}}_i(X_n\in T)\to 0={\pi }_j$。

当 $j\in C_1$ 时，若 $i\in C_1$，则 $(Q^n{)}_{ij}=(Q_1^n{)}_{ij}\to {\pi }_j$。若 $i\in T$，记进入 $C_1$ 的首达时为 $\sigma$，则

$${\mathbb{P}}_i(X_n=j)=\sum _{t=1}^n\sum _{a\in C_1}{\mathbb{P}}_i(\sigma =t,X_t=a)(Q_1^{n-t}{)}_{aj}.$$

因 $\{\sigma >n\}=\{X_n\in T\}$，有 ${\mathbb{P}}_i(\sigma >kN)\le (1-\epsilon {)}^k$，故 ${\mathbb{P}}_i(\sigma >n)\to 0$。又

$$|{\mathbb{P}}_i(X_n=j)-{\pi }_j{\mathbb{P}}_i(\sigma \le n)|\le \sum _{t=1}^n{\mathbb{P}}_i(\sigma =t){\delta }_{n-t}.$$

对任意 $\eta >0$，取 $M$ 使 $n\ge M$ 时 ${\delta }_n<\eta$，再取 $n>M$ 使 ${\mathbb{P}}_i(\sigma >n-M)<\eta$。由于 ${\delta }_{n-t}\le 1$，将和式按 $t\le n-M$ 与 $t>n-M$ 拆开可得上式右端小于 $2\eta$，且 ${\pi }_j{\mathbb{P}}_i(\sigma >n)<\eta$。故当 $n$ 充分大时 $|(Q^n{)}_{ij}-{\pi }_j|<3\eta$，即 $(Q^n{)}_{ij}\to {\pi }_j$。因此 $Q^n\to 1\pi$。$\square$

算例：均匀重置链

设 $E=\{1,\dots ,K\}$，$\alpha \in (0,1)$。每一步以概率 $1-\alpha$ 留在当前状态，以概率 $\alpha$ 从 $E$ 中均匀抽取下一状态：

$$Q_{ij}=\{\begin{array}{ll}1-\alpha +\alpha /K& j=i,\\ \alpha /K& j\ne i.\end{array}$$

令 $J:=\frac{1}{K}11^{\top }$，则 $Q=(1-\alpha )I+\alpha J$。由 $1^{\top }1=K$ 知 $J^2=J$，$(I-J{)}^2=I-J$，且 $J(I-J)=(I-J)J=0$。将 $Q$ 写为互补投影之和

$$Q=J+(1-\alpha )(I-J),$$

则对任意 $n\ge 1$，

$$Q^n=(J+(1-\alpha )(I-J){)}^n=J^n+(1-\alpha {)}^n(I-J{)}^n=J+(1-\alpha {)}^n(I-J).$$

均匀分布 $\pi =\frac{1}{K}{1}^{\top }$ 满足 $\pi J=\pi$，故 $\pi Q=(1-\alpha )\pi +\alpha \pi =\pi$。对任意初始分布 ${\nu }_0\in {\Delta }_{K-1}$，由 ${\nu }_{0}1=1$ 得

$${\nu }_{0}J=\frac{1}{K}({\nu }_{0}1)1^{\top }=\pi ,{\nu }_0(I-J)={\nu }_0-\pi ,$$

从而

$${\nu }_n={\nu }_0{Q}^n=\pi +(1-\alpha {)}^n({\nu }_0-\pi )\underset{n\to \infty }{\to }\pi .$$

算例：环上惰性随机游走

设 $K\ge 3$，$\alpha \in (0,1)$，状态空间取环 $E={\mathbb{Z}}_K=\{0,1,\dots ,K-1\}$。每一步以概率 $1-\alpha$ 停留原地，以概率 $\alpha /2$ 移至左邻或右邻：

$$Q_{ij}=\{\begin{array}{ll}1-\alpha & j=i,\\ \alpha /2& j\equiv i\pm 1(\mathrm{mod}K),\\ 0& \text{其他}.\end{array}$$

$Q$ 由首行 $(1-\alpha ,\alpha /2,0,\dots ,0,\alpha /2)$ 循环生成，故为双随机矩阵（行和与列和均为 $1$），均匀分布 $\pi =\frac{1}{K}{1}^{\top }$ 满足 $\pi Q=\pi$。沿环逐步转移可到达任意状态，故链不可约；又 $Q_{ii}=1-\alpha >0$，故周期 $d=1$。由收敛定理知 $Q^n\to 1\pi$，对任意初始分布 ${\nu }_0$ 均有 ${\nu }_n\to \pi$。

Cesàro 平均收敛

当唯一闭沟通类有周期时，${\nu }_n={\nu }_0{Q}^n$ 未必逐时刻收敛，但其 Cesàro 平均仍然收敛。

定理。 若 $\pi$ 是 $Q$ 的唯一平稳分布，则对任意 ${\nu }_0\in {\Delta }_{K-1}$，

$$\frac{1}{N}\sum _{n=0}^{N-1}{\nu }_0{Q}^n⟶\pi .$$

证明

记 ${\bar{\nu }}_N:=N^{-1}{\sum }_{n=0}^{N-1}{\nu }_0{Q}^n\in {\Delta }_{K-1}$。由存在性证明二知 $\Vert {\bar{\nu }}_{N}Q-{\bar{\nu }}_N{\Vert }_{\infty }\le 1/N$。对 ${\bar{\nu }}_N$ 的任一收敛子列 ${\bar{\nu }}_{N_k}\to \mu$，有 $\mu \in {\Delta }_{K-1}$ 且 $\mu Q=\mu$；由平稳分布唯一性得 $\mu =\pi$。

若 ${\bar{\nu }}_N$ 不收敛于 $\pi$，则存在 $\epsilon >0$ 及子列使 $\Vert {\bar{\nu }}_{N_k}-\pi {\Vert }_{\infty }\ge \epsilon$。因 ${\Delta }_{K-1}$ 紧，该子列存在收敛子列，其极限与 $\pi$ 的距离至少为 $\epsilon$，矛盾。故 ${\bar{\nu }}_N\to \pi$。$\square$

从谱上看，周期链在单位圆上除 $1$ 外的特征值 $\lambda$（$|\lambda |=1,\lambda \ne 1$）满足

$$\frac{1}{N}\sum _{n=0}^{N-1}{\lambda }^n=\frac{1-{\lambda }^N}{N(1-\lambda )}⟶0,$$

Cesàro 平均消去了单位圆上非 $1$ 特征值对应的振荡分量。

样本路径的时间平均

定理（遍历定理）。 设链有限且不可约，$\pi$ 为唯一平稳分布。则对任意函数 $f:E\to \mathbb{R}$ 和任意初始分布 ${\nu }_0$，

$$\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=1_{\{j\}}$，得状态 $j$ 的长期访问频率：

$$\frac{1}{N}\sum _{n=0}^{N-1}{1}_{\{X_n=j\}}\underset{N\to \infty }{\overset{\text{a.s.}}{\to }}{\pi }_j.$$

证明

记 ${\mathbb{P}}_i$、${\mathbb{E}}_i$ 为从 $X_0=i$ 出发的概率与期望。固定状态 $r\in E$，定义首次正返回时

$$\tau :=\inf \{n\ge 1:X_n=r\}.$$

先证 ${\mathbb{E}}_r[\tau ]<\infty$。由不可约性，对每个 $i\ne r$ 存在步数 $n_i\le K-1$ 使 ${\mathbb{P}}_i(X_{n_i}=r)>0$；对 $r$ 存在最短正返回路径，步数 $n_r\le K$，满足 ${\mathbb{P}}_r(\tau \le n_r)>0$。取 $\ell :={\max }_{i\in E}{n}_i\le K$，并令

$$\epsilon :=\min (\{{\mathbb{P}}_r(\tau \le \ell )\}\cup \{{\mathbb{P}}_i(X_{n_i}=r):i\ne r\})>0,$$

则对任意 $i\ne r$，由 $1\le n_i\le \ell$ 知 ${\mathbb{P}}_i(\exists m\in \{1,\dots ,\ell \},X_m=r)\ge {\mathbb{P}}_i(X_{n_i}=r)\ge \epsilon$。因 $\{\tau >n\}=\{X_1\ne r,\dots ,X_n\ne r\}\in {\mathcal{F}}_n^X$，且在事件 $\{\tau >k\ell \}$（$k\ge 1$）上有 $X_{k\ell }\ne r$，由 Markov 性知在该事件上

$${\mathbb{P}}_r(\tau >(k+1)\ell |{\mathcal{F}}_{k\ell }^X)\le 1-\epsilon .$$

两边取期望并结合 $k=0$ 时的 ${\mathbb{P}}_r(\tau >\ell )\le 1-\epsilon$，归纳得 ${\mathbb{P}}_r(\tau >k\ell )\le (1-\epsilon {)}^k$（$\forall k\ge 0$）。故 ${\mathbb{P}}_r(\tau <\infty )=1$，且

$${\mathbb{E}}_r[\tau ]=\sum _{n=0}^{\infty }{\mathbb{P}}_r(\tau >n)\le \sum _{k=0}^{\infty }\ell {\mathbb{P}}_r(\tau >k\ell )\le \frac{\ell }{\epsilon }<\infty .$$

定义单循环内各状态的期望访问次数 $\mathbf{m}=(m_1,\dots ,m_K)$：

$$m_j:={\mathbb{E}}_r\left[\sum _{n=0}^{\tau -1}{1}_{\{X_n=j\}}\right]=\sum _{n=0}^{\infty }{\mathbb{P}}_r(X_n=j,\tau >n).$$

显然 $m_r=1$，且 ${\sum }_{j=1}^K{m}_j={\mathbb{E}}_r[\tau ]$。由 $\{\tau >n\}\in {\mathcal{F}}_n^X$ 及 Markov 性，

$${\mathbb{P}}_r(X_n=i,\tau >n,X_{n+1}=j)={\mathbb{P}}_r(X_n=i,\tau >n)Q_{ij}.$$

对 $i$ 与 $n$ 求和得

$$\sum _{i=1}^K{m}_i{Q}_{ij}=\sum _{n=0}^{\infty }{\mathbb{P}}_r(\tau >n,X_{n+1}=j)=\sum _{n=1}^{\infty }{\mathbb{P}}_r(\tau \ge n,X_n=j).$$

当 $j\ne r$ 时，$X_n=j$ 蕴含 $\tau \ne n$，且 $X_0=r\ne j$，故右端等于 ${\sum }_{n=0}^{\infty }{\mathbb{P}}_r(\tau >n,X_n=j)=m_j$；当 $j=r$ 时，$n\ge 1$ 且 $X_n=r$ 蕴含 $\tau \le n$，故 $\{\tau \ge n,X_n=r\}=\{\tau =n\}$，右端等于

$$\sum _{n=1}^{\infty }{\mathbb{P}}_r(\tau =n)={\mathbb{P}}_r(\tau <\infty )=1=m_r.$$

因此 $\mathbf{m}Q=\mathbf{m}$。由平稳分布唯一性及 $m1={\mathbb{E}}_r[\tau ]$，得

$$m_j={\pi }_j{\mathbb{E}}_r[\tau ].$$

令 $R:={\sum }_{n=0}^{\tau -1}f(X_n)$，则 ${\mathbb{E}}_r|R|\le \Vert f{\Vert }_{\infty }{\mathbb{E}}_r[\tau ]<\infty$，且

$${\mathbb{E}}_r[R]=\sum _{j=1}^{K}f(j)m_j={\mathbb{E}}_r[\tau ]\sum _{j=1}^K{\pi }_{j}f(j).$$

设 $X_0=r$，定义依次返回 $r$ 的停时列 ${\tau }_0:=0$，${\tau }_{k+1}:=\inf \{n>{\tau }_k:X_n=r\}$，以及循环长度 $L_k:={\tau }_k-{\tau }_{k-1}$、循环累计和 $R_k:={\sum }_{n={\tau }_{k-1}}^{{\tau }_k-1}f(X_n)$。由强 Markov 性，$(L_k,R_k{)}_{k\ge 1}$ 在 ${\mathbb{P}}_r$ 下独立同分布，且与 $(\tau ,R)$ 同分布。由强大数定律，在 ${\mathbb{P}}_r$ 下几乎必然有

$$\frac{1}{M}\sum _{k=1}^M{R}_k⟶{\mathbb{E}}_r[R],\frac{1}{M}\sum _{k=1}^M{L}_k⟶{\mathbb{E}}_r[\tau ],$$

从而

$$\frac{{\sum }_{k=1}^M{R}_k}{{\sum }_{k=1}^M{L}_k}⟶\sum _{j=1}^K{\pi }_{j}f(j).$$

对时刻 $N$，令 $M(N):=\max \{M\ge 0:{\tau }_M\le N\}$，$S_M:={\sum }_{k=1}^M{L}_k={\tau }_M$。则 $S_{M(N)}\le N<S_{M(N)+1}$，$M(N)\to \infty$（${\mathbb{P}}_r$-a.s.），且

$$\sum _{n=0}^{N-1}f(X_n)=\sum _{k=1}^{M(N)}{R}_k+{\rho }_N,|{\rho }_N|\le \Vert f{\Vert }_{\infty }{L}_{M(N)+1}.$$

由 $S_M/M\to {\mathbb{E}}_r[\tau ]$ 及 $S_{M(N)}\le N<S_{M(N)+1}$ 得 $N/M(N)\to {\mathbb{E}}_r[\tau ]$，$S_{M(N)}/N\to 1$。又 $L_M/M=S_M/M-S_{M-1}/M\to 0$，故

$$\frac{|{\rho }_N|}{N}\le \Vert f{\Vert }_{\infty }\frac{L_{M(N)+1}}{M(N)+1}\cdot \frac{M(N)+1}{N}⟶0.$$

于是

$$\frac{1}{N}\sum _{n=0}^{N-1}f(X_n)=\frac{S_{M(N)}}{N}\cdot \frac{{\sum }_{k=1}^{M(N)}{R}_k}{S_{M(N)}}+\frac{{\rho }_N}{N}\underset{N\to \infty }{\overset{{\mathbb{P}}_r\text{-a.s.}}{\to }}\sum _{j=1}^K{\pi }_{j}f(j).$$

若 $X_0=i\ne r$，令首达时 $\sigma :=\inf \{n\ge 0:X_n=r\}$，同样有 ${\mathbb{P}}_i(\sigma >k\ell )\le (1-\epsilon {)}^k$，故 $\sigma <\infty$（${\mathbb{P}}_i$-a.s.）。$\sigma$ 之前的有限和满足 $|{\sum }_{n=0}^{\sigma -1}f(X_n)|/N\le \Vert f{\Vert }_{\infty }\sigma /N\to 0$；对 $N>\sigma$，

$$\frac{1}{N}\sum _{n=\sigma }^{N-1}f(X_n)=\frac{N-\sigma }{N}\cdot \frac{1}{N-\sigma }\sum _{t=0}^{N-\sigma -1}f(X_{\sigma +t})\underset{N\to \infty }{\overset{{\mathbb{P}}_i\text{-a.s.}}{\to }}\sum _{j=1}^K{\pi }_{j}f(j).$$

对一般初始分布 ${\nu }_0$，由 ${\mathbb{P}}_{{\nu }_0}={\sum }_{i=1}^K({\nu }_0{)}_i{\mathbb{P}}_i$ 即得结论。$\square$

若链恰有一个闭沟通类 $C_1$（允许暂态集 $T\ne \varnothing$），由于从任意状态进入 $C_1$ 的首达时几乎必然有限，且唯一平稳分布 $\pi$ 在 $T$ 上为 $0$，上述遍历定理对任意初始分布仍然成立。

条件汇总

对有限状态离散时间时齐马尔可夫链（转移矩阵 $Q$ 行随机）：

1. 平稳分布存在：无额外条件。每个闭沟通类 $C_k$ 对应唯一一个支撑在 $C_k$ 上的平稳分布 ${\tilde{\pi }}^{(k)}$，全体平稳分布为其凸组合，暂态上的平稳概率恒为 $0$。
2. 平稳分布唯一：当且仅当闭沟通类恰好有一个（$m=1$）。若链不可约（$m=1$ 且 $T=\varnothing$），则唯一平稳分布满足 ${\pi }_i>0$（$\forall i\in E$）。
3. Cesàro 平均与样本时间平均收敛：当 $m=1$ 时，对任意初始分布 ${\nu }_0$ 有 $\frac{1}{N}{\sum }_{n=0}^{N-1}{\nu }_0{Q}^n\to \pi$，且对任意 $f:E\to \mathbb{R}$ 有 $\frac{1}{N}{\sum }_{n=0}^{N-1}f(X_n)\stackrel{\text{a.s.}}{\to }{\sum }_{i=1}^K{\pi }_{i}f(i)$（无需非周期）。
4. 逐时刻分布收敛：当 $m=1$ 且该唯一闭沟通类非周期时，$Q^n\to 1\pi$，从而对任意初始分布 ${\nu }_0$ 有 ${\nu }_0{Q}^n\to \pi$。