Lecture 6 - Limit Behaviour & Ergodic Theory
本节课接着常返性的内容，考虑 \(n\to\infty\) 的情形，继续研究随时间推移,Markov 链转移的规律。由上一节课中 Corollary 5.12，若状态 \(j\) 是暂留的，那么对任意状态
\[P_{ij}^{(n)}\to0,\quad n\to\infty \]
所以本节课我们只考虑常返状态。
弱遍历定理
平均返回时间和正常返
假设状态 \(i\) 是常返的，那么 \(f_{ii}=\sum\limits_{n=1}^{\infty}f_{ii}^{(n)}=1\)，把 \(\left\{ f_{ii}^{(n)} \right\}\) 看成 \(\mathbb{N}^{+}\) 上的一个分布，我们可以定义返回状态 \(i\) 的平均转移次数
Definition 6.1(平均返回时间)
对于常返状态 \(i\) 的平均返回时间定义为
\[\mu_{ii}\overset{\Delta}{=}\sum\limits_{n=1}^{\infty} nf_{ii}^{(n)}\]
利用平均返回时间可以进一步对常返状态分类
Definition 6.2(正常返)
假设状态 \(i\) 常返，如果它的平均返回时间是有限的，也就是 \(\mu_{ii}<\infty\)，就称状态 \(i\) 是正常返的(Positive recurrent)，否则，\(M_{ii}=\infty\)，我们则称 \(i\) 为零常返(Null recurrent)
弱遍历定理
Theorem 6.3(弱遍历定理)
设 \(\left\{ X_{n} \right\}\) 是不可约常返 Markov 链，那么对 \(\forall i,j\) 状态
\[\lim\limits_{ n \to \infty } \frac{1}{n}\sum\limits_{k=0}^{n-1} P_{ij}^{(k)}= \frac{1}{\mu_{jj}}\]
Proof.
先给出一个引理(不加证明)
Lemma 6.4(Hardy&Littlewood)
设 \(\forall n ,a_{n}\geqslant 0\)，记幂级数 \(A(z)\) 为 \(\sum\limits_{n=0}^{\infty}a_{n}z^{n},0\leqslant z<1\)
则有
\[\lim\limits_{ n \to \infty } \frac{1}{n}\sum\limits_{k=0}^{n-1} a_{k}=\lim\limits_{ z \to 1^{-} }(1-z)A(z)\]
设 \(P_{ij}(z)\overset{\Delta}{=}\sum\limits_{n=0}^{\infty}P_{ij}^{(n)}z^{n}\)，由引理得
\[
\lim\limits_{ n \to \infty } \frac{1}{n}\sum\limits_{k=0}^{n-1}P_{ij}^{(k)}=\lim\limits_{ z \to 1^{-} }(1-z)\sum\limits_{n=0}^{\infty} P_{ij}^{(k)}z^{n}
\]
回顾 Theorem 5.11 的证明中
\[
\sum\limits_{n=0}^{\infty} P_{ij}^{(n)}z^{n}=\delta_{ij}+\sum\limits_{k=1}^{\infty} \left( f_{ij}^{(k)}z^{k} \right) \sum\limits_{k=0}^{\infty} \left( P_{ij}^{(k)}z^{k} \right)
\]
设 \(F_{ij}(z)\overset{\Delta}{=}\sum\limits_{n=1}^{\infty}f_{ij}^{(n)}z^{n}\)，当 \(i\neq j\) 时，由 Abel 定理可得
\[
F_{ij}(1^{-})=\lim\limits_{ z \to 1^{-} } \sum\limits_{n=1}^{\infty} f_{ij}^{(n)}z^{n}=\sum\limits_{n=1}^{\infty} f_{ij}^{(n)}=1
\]
所以
\[
\begin{aligned}
\lim\limits_{ z \to 1^{-} } (1-z)F_{ij}(z)P_{jj}(z)&=\lim\limits_{ z \to 1^{-} } P_{jj}(z)\\
&=\lim\limits_{ z \to 1^{-} } \frac{1-z}{1-F_{jj}(z)}
\end{aligned}
\]
当 \(i=j\) 时，直接有
\[
\lim\limits_{ z \to 1^{-} } (1-z)P_{jj}(z)=\lim\limits_{ z \to 1^{-} } \frac{1-z}{1-F_{jj}(z)}
\]
无论是否有 \(i=j\)，即 \(\forall i\) 都有
\[
\begin{aligned}
\lim\limits_{ z \to 1^{-} } (1-z)P_{ij}(z)=\lim\limits_{ z \to 1^{-} } \frac{1-z}{1-F_{jj}(z)}\\
\overset{L'Hospital}{=}\lim\limits_{ z \to 1^{-} } \frac{1}{F_{jj}'(z)}
\end{aligned}
\]
由 Abel 定理(结合上面的所有等式可得)
\[
\lim\limits_{ n \to \infty } \frac{1}{n}\sum\limits_{k=0}^{n-1} P_{ij}^{(k)}=\lim\limits_{ z \to 1^{-} } \frac{1}{\sum\limits_{n=1}^{\infty} nf_{jj}^{(n)}z^{n-1}}=\frac{1}{\mu_{jj}}
\]
注. \(\dfrac{1}{n}\sum\limits_{k=0}^{n-1}P_{ij}^{(k)}\) 具有明确的概率含义(概率转化为示性函数的期望)，
\[\begin{aligned}
\frac{1}{n}\sum_{k=0}^{n-1}P_{ij}^{(k)}& =\frac{1}{n}\sum_{k=0}^{n-1}\mathbb{E}(\mathbf{I}_{[X_{k}=j|X_{0}=i]}) \\
&=\frac1n\mathbb{E}(\#\{n>k\geqslant0:X_{k}=j|X_{0}=i\})
\end{aligned}\]
其中#A 表示集合 A 中元素的个数。所以 \(\dfrac{1}{n}\sum\limits_{k=0}^{n-1}P_{ij}^{(k)}\) 表示在 \(n-1\) 步转移中，处于状态 \(j\) 的次数与记录状态总数 \(n\) 的比值。
正常返的简单性质
和常返性一样，正常返也具有类的性质，即下面命题：
Proposition 6.5
若 \(i\) 正常返,\(i\to j\),那么 \(j\) 也正常返。
Proof
由于 \(i\to j\)，那么存在 \(m\)，使得 \(P_{ij}^{(m)}>0\) ，由 CK 方程，
\[P_{kj}^{(l+m)}=\sum_{s\in E}P_{ks}^{(l)}P_{sj}^{(m)}\geqslant P_{ki}^{(l)}P_{ij}^{(m)}\]
不等式两端对 \(l\) 求和平均，
\[\frac{1}{n}\sum\limits_{l=0}^{n-1}P_{kj}^{(l+m)}\geqslant\frac{1}{n}\sum\limits_{l=0}^{n-1}P_{ki}^{(l)}P_{ij}^{(m)}\]
两端同时令 \(n\to\infty\) 取极限，利用弱遍历定理：
\[\frac{1}{\mu_{jj}}\geqslant\frac{P_{ij}^{(m)}}{\mu_{ii}}>0\]
故 \(\mu_{jj}<\infty\)，所以 \(j\) 正常返。
进一步，如果 Markov 链的状态是有限的，和常返性一样，有下面结论：
Proposition 6.6
有限状态 Markov 链必然存在正常返态
Proof
反证法，若命题不成立。设状态空间 \(E=\{1,2,\ldots,N\}\)，则所有状态都是暂留的或者零常返的。固定状态 \(i\)，对任意 \(j\)，由弱遍历定理，
\[\frac{1}{n}\sum\limits_{k=0}^{n-1}P_{ij}^{(k)}\to0,\quad n\to\infty \]
那么对有限的 N，
\[\begin{aligned}\sum_{j=1}^N\frac{1}{n}\sum_{k=0}^{n-1}P_{ij}^{(k)}\to0,\quad n\to\infty\end{aligned}\]
然而，由概率转移矩阵的性质：对任意 \(k\)，\(\sum\limits_{j=1}^{N}P_{ij}^{(k)}=1\)
\[\begin{aligned}\frac{1}{n}\sum_{j=1}^{N}\sum_{k=0}^{n-1}P_{ij}^{(k)}=1\end{aligned}\]
矛盾(按假设应当趋于 0)！故命题成立。
注.结合推论 6.5 可知，状态有限的不可约 Markov 链，所有状态都是正常返态。
不变分布的存在唯一性
基本问题
本节我们利用弱遍历定理回答关于不变分布的问题：
1.如果不变分布存在，什么条件下具有唯一性？
便于研究随机动力系统
2.不变分布在什么条件下存在？
3.如果存在且唯一那么那个 Markov 链的收敛速度有多快？如何刻画这个速度？(Next Lecture)
不变分布的唯一性
首先回答第一个问题，即下面定理(仍然研究不可约常返的 Markov 链)
Theorem 6.7
设 \(\{X_n\}\) 是不可约常返的 Markov 链， \(\pi\) 是 \(P\) 的一个不变分布，即满足不变方程 \(\pi=\pi P\)，则对任意状态 \(j\)，都有 \(\pi_j>0\)，且
\[\pi_j=\frac{1}{\mu_{jj}}\]
Proof.
先给出一个引理-有界收敛定理(实际是控制收敛定理的一个特例，M 也就是控制函数，控制收敛定理可以在实变函数中得到证明，但有界收敛定理只需要初等概率论的知识)
Lemma 6.8(有界收敛定理)
设 \(X_{1},X_{2},\ldots\).为随机变量序列，依概率收敛于 \(X\)。若存在 \(M>\) 0，使得对任意 \(n\geq1\)，\(P(|X_n|\leq M)=1\)，那么
\[\lim\limits_{n\to\infty}\mathbb{E}[X_n]=\mathbb{E}[\lim\limits_{n\to\infty}X_n]=\mathbb{E}[X]\]
依概率收敛，记为 \(X_n\stackrel{\mathrm{P}}{\longrightarrow}X\)，如果对于 \(\varepsilon>0\)
\[\mathrm{P}(\omega:|X_n(\omega)-X(\omega)|>\varepsilon)\to0,n\to\infty.\]
Proof
首先，由于 \(X_{n}\) 依概率收敛于 \(X\) ，且 \(P(|X_{n}|\leq M)=1\) ，所以对任意 \(\epsilon>0\)
\[P(|X|>M+\epsilon)\leq P(|X_n-X|>\epsilon)\to0\]
即 \(P(|X|\leq M)=1\) ．其次，对任意 \(\varepsilon>0\)
\[\begin{aligned}
\mathbb{E}[|X_{n}-X|]& =\mathbb{E}[\left|X_{n}-X\right|\mathbf{I}_{\left|X_{n}-X\right|>\varepsilon}]+\mathbb{E}[\left|X_{n}-X\right|\mathbf{I}_{\left|X_{n}-X\right|\leqslant\varepsilon}] \\
&\leq\mathbb{E}[(|X_{n}|+|X|)\mathbf{I}_{|X_{n}-X|>\varepsilon}]+\varepsilon \\
&\leqslant2MP\left(|X_{n}-X|>\varepsilon\right)+\varepsilon.
\end{aligned}\]
最后，令 \(n\to\infty\) 可得，
\[\lim\sup\limits_{n\to\infty}\mathbb{E}|X_n-X|\leqslant\varepsilon \]
再令 \(\varepsilon\rightarrow0\) 即证。
回到原命题，对任意状态 \(i\)，由于 \(\sum\limits_{s\in E}\pi_{s}=1\)，所以存在 \(j\in S\)，使得 \(\pi_j>0\)。对于任意状态 \(i\)，由于 \(\{X_n\}\) 不可约，所以 \(j\to i\)，故存在 \(n\) ，使得 \(P_{ji}^{(n)}>0\)，那么根据不变方程：
\[\pi_i=\sum_{k\in E}\pi_kP_{ki}^{(n)}\ge\pi_jP_{ji}^{(n)}>0\]
命题第一部分得证(\(\forall i,\pi_{i}>0\))。
不妨考虑 \(\{X_{n}\}\) 初始分布为 \(\pi\)，由于 \(\pi\) 是不变分布，所以对任意 \(k\)， \(P(X_{k}=j)=\pi_{j}\) ，那么
\[\begin{aligned}
\mathbb{E}_{X_{0}\sim\pi}\left[{\frac{1}{n}}\sum_{k=0}^{n-1}P_{ij}^{(k)}\right]& =\mathbb{E}_{X_{0}\sim\pi}\left[\frac{1}{n}\sum_{k=0}^{n-1}\mathbb{E}[\mathbf{I}_{X_{k}=j|X_{0}=i}]\right] \\
&=\frac{1}{n}\sum_{k=0}^{n-1}P(X_{k}=j)=\pi_{j}
\end{aligned}\]
由于 \(0\leqslant\dfrac{1}{n}\sum\limits_{k=0}^{n-1}P_{ij}^{(k)}\leqslant 1\)，所以由有界收敛定理+弱遍历定理
\[\begin{aligned}
\pi_{j}& =\lim_{n\to\infty}\mathbb{E}_{X_{0}\sim\pi}\left[\frac{1}{n}\sum_{k=0}^{n-1}P_{ij}^{(k)}\right] \\
&=\mathbb{E}_{X_{0}\sim\pi}\left[\operatorname*{lim}_{n\to\infty}\frac{1}{n}\sum_{k=0}^{n-1}P_{ij}^{(k)}\right]=\mathbb{E}_{X_{0}\sim\pi}\left[\frac{1}{\mu_{jj}}\right]=\frac{1}{\mu_{jj}}
\end{aligned}\]
注．上面的命题表明，对于不可约常返 Markov 链，不变分布如果存在，则是唯一的，并 \(\exists\pi_{j}=\frac{1}{\mu_{jj}}>0\) ，那么对任意状态 \(j\)
\[\mu_{jj}=\frac{1}{\pi_{j}}<\infty \]
这说明：如果不变分布存在，就有所有状态都是正常返的。
下面我们证明其逆命题，也就是若 \(\mu_{jj}<\infty\) ，令 \(\pi_{i}=\frac{1}{\mu_{jj}}\) ，则 \(\pi\) 就是不变分布，这回答了：不变分布在什么条件下存在？
不变分布的存在性
Theorem 6.9
不可约正常返的 Markov 链存在平稳分布。
Proof
由弱遍历定理，对不可约正常返 Markov 链中的任意状态 \(i,j\)
\[\begin{aligned}\lim_{n\to\infty}\frac{1}{n}\sum_{k=0}^{n-1}P_{ij}^{(k)}=\frac{1}{\mu_{jj}}\triangleq p_j>0\end{aligned}\]
我们下面证明 \(p=(p_{0},p_{1},\ldots)\) 为一个不变分布，即满足不变方程 \(p=pP\) ，且是一个概率分布。
先证不变方程 \(p=pP\) 成立。由 C-K 方程
\[\begin{aligned}\frac{1}{n}\sum_{k=0}^{n-1}P_{ij}^{(k+1)}=\sum_{l\in E}\left(\frac{1}{n}\sum_{k=0}^{n-1}P_{il}^{(k)}\right)P_{lj}\end{aligned}\]
由于 \(\frac{1}{n}(P_{ij}^{(n)}-P_{ij}^{(0)})\to0\) \(n\to\infty\)
\[\begin{aligned}p_j=\lim_{n\to\infty}\frac{1}{n}\sum_{k=0}^{n-1}P_{ij}^{(k)}=\lim_{n\to\infty}\frac{1}{n}\sum_{k=0}^{n-1}P_{ij}^{(k+1)}\end{aligned}\]
由于 \(0\leqslant\frac{1}{n}\sum\limits_{k=0}^{n-1}P_{ij}^{(k)}\leqslant1\) ，所以由有界收敛定理
\[\lim\limits_{n\to\infty}\frac{1}{n}\sum\limits_{k=0}^{n-1}P_{ij}^{(k+1)}=\sum\limits_{l\in E}\left(\lim\limits_{n\to\infty}\frac{1}{n}\sum\limits_{k=0}^{n-1}P_{il}^{(k)}\right)P_{lj}\]
即得不变方程
\[\begin{aligned}p_j=\sum_{l\in E}p_lP_{lj}\end{aligned}\]
再证 \(p\) 是一个概率分布，即 \(\sum_{l\in E}p_{l}=1\) ．由于对任意 \(k\)
\[p=pP\Longrightarrow p=pP^k\]
所以
\[p_j=\sum_{l\in E}p_l\left(\frac{1}{n}\sum_{k=0}^{n-1}P_{lj}^{(k)}\right)\]
由于 \(0\leq\frac{1}{n}\sum_{k=0}^{n-1}P_{ij}^{(k)}\leq1\) ，所以由有界收敛定理
\[\begin{aligned}
\text{p} &=\lim_{n\to\infty}p_{j}=\lim_{n\to\infty}\sum_{l\in E}p_{l}\left(\frac{1}{n}\sum_{k=0}^{n-1}P_{lj}^{(k)}\right) \\
&=\sum_{l\in E}p_{l}\left(\operatorname*{lim}_{n\to\infty}\frac{1}{n}\sum_{k=0}^{n-1}P_{lj}^{(k)}\right)=p_{j}\sum_{l\in E}p_{l}
\end{aligned}\]
所以 \(\sum\limits_{l\in E}p_{l}=1\)
弱遍历定理的另一形式
我们已经知道了弱遍历极限和不变分布的关系，可以得到弱遍历定理的另一个形式
Theorem 6.10(弱遍历定理)
设 \(\{X_{n}\}\) 是不可约正常返的 Markov 链，\(\pi\) 是不变分布，那么对任意状态 \(i,j\)，
\[\lim\limits_{n\to\infty}\frac{1}{n}\sum\limits_{k=0}^{n-1}P_{ij}^{(k)}=\pi_j\]
平均遍历定理
更一般地，可以得到下面的(平均)遍历定理(证明比较复杂课上略过)
Theorem 6.11(遍历定理）
设 \(\{X_n\}\) 是不可约常返的 Markov 链， \(\pi\) 是不变分布， \(f\) 是 \(E\) 上的函数，满足 \(\sum\limits_{i\in E}\pi_{i}|f(i)|<\infty\)，则
\[\lim\limits_{n\to\infty}\frac{1}{n}\sum\limits_{k=0}^{n-1}f(X_k)=\sum\limits_{i\in E}\pi_if(i)\]
Proof
参考《应用随机过程》，陈大岳、章复熹，北京大学出版社，2023，P118，P124-P128.
注 1.遍历定理说明了长时间尺度下，函数 \(f\) 的时间平均，等于在空间上平均。这意味着系统的长期统计行为可以由其稳态分布完全描述。此外，在计算数学中，经常会处理高维空间上积分计算的问题，即 \(E\) 是高维空间，那么由遍历定理，即可通过构造随机动力系统(遍历的 Markov 过程)，通过计算时间上的一维积分，取极限得到高维积分的结果。
Addition：刘军 -《科学计算中的蒙特卡洛策略》- 科学出版社
注 2.遍历定理可以视为大数定律在 Markov 依赖结构下的推广。大数定律适用于独立同分布的随机变量，表明样本均值收敛到期望：而遍历定理适用于具有 Markov 性的序列，表明时间平均收敛到平稳分布下的期望。两者都揭示了“平均行为的稳定性”，但遍历定理处理的是更一般的 Markov 依赖的情况。
回顾大数定律：
\[
\begin{aligned}
\frac{1}{n}\sum\limits_{i=1}^{n} X_{i}\overset{p}{\to}E\left[ X_{i} \right]\\
\frac{1}{n}\sum\limits_{i=1}^{n} X_{i}\overset{a.s.}{\to}E\left[ X_{i} \right]
\end{aligned}
\]
强遍历定理
常返性和弱遍历定理虽然给出了随 Markov 链转移状态的渐近规律，但是当 \(n\rightarrow\infty\) 时，转移概率 \(P_{ij}^{(n)}\) 的极限情况我们仍然不清楚。先看一个例子。
Example 6.12(两状态的 Markov 链 III)
考虑 Markov 链，状态空间为 \(\{0,1\}\) ，转移矩阵为
\[P=\left(\begin{array}{cc}1-\alpha&\alpha\\\beta&1-\beta\end{array}\right)\]
其中 \(\alpha,\beta\in(0,1)\)
\[P^n=\frac{1}{\alpha+\beta}\left(\begin{array}{cc}\beta&\alpha\\\beta&\alpha\end{array}\right)+\frac{(1-\alpha-\beta)^n}{\alpha+\beta}\left(\begin{matrix}\alpha&-\alpha\\-\beta&\beta\end{matrix}\right)\]
转移概率的极限：
\[\lim\limits_{n\to\infty}P^{(n)}=\frac{1}{\alpha+\beta}\left(\begin{array}{cc}\beta&\alpha\\\beta&\alpha\end{array}\right)=\left(\begin{array}{c}\pi\\\pi\end{array}\right),\]
即 \(\lim\limits_{ n \to \infty }P_{ij}^{(n)}=\pi_{j}\).但是，如果 \(\alpha=\beta=1\)，即
\[P=\left(\begin{array}{cc}0&1\\1&0\end{array}\right)\]
计算容易发现规律
\[P_{00}^{(n)}=P_{11}^{(n)}=\left\{\begin{array}{ll}1,&n=2k\\[6pt]0,&n=2k-1\end{array}\right.\]
有
\[\lim\limits_{n\to\infty}\frac{1}{n}\sum\limits_{k=0}^{n-1}P_{00}^{(n)}=\lim\limits_{n\to\infty}\frac{1}{n}\sum\limits_{k=0}^{n-1}P_{11}^{(n)}=\frac{1}{2}\]
该 Markov 链正常返，平均返回时间为 2。然而，\(\lim\limits_{ n \to \infty }P_{00}^{(n)}\) 和 \(\lim\limits_{ n \to \infty }P_{11}^{(n)}\) 都不存在
这个例子说明了弱遍历性无法得到 \(P_{ij}^{(n)}\) 的极限性质，即
\[\lim\limits_{n\to\infty}\frac{1}{n}\sum\limits_{k=0}^{n-1}P_{ij}^{(n)}=\pi_j\nRightarrow\lim\limits_{n\to\infty}P_{ij}^{(n)}=\pi_j\]
也就是说，对于正常返的 Markov 链，\(P_{ij}^{(n)}\) 的极限也可能不存在。事实上，状态的周期性对于转移概率的极限是否存在起着关键作用。
这个定理的证明将使用到概率论中的耦合方法(Very Important)
Theorem 6.13(强遍历定理)
设 \(\{X_{n}\}\) 是不可约非周期的 Markov 链，若 \(\pi\) 是 \(P\) 的不变分布， 那么
\[\lim\limits_{n\to\infty}\sum\limits_{j\in E}\lvert P_{ij}^{(n)}-\pi_{j}\lvert=0,\quad\forall i\in E.\]
那么自然有
\[\lim\limits_{n\to\infty}P_{ij}^{(n)}=\pi_j\]
Proof
设 \(\{X_{n}:n\geqslant0\}\) 和 \(\{Y_{n}:n\geqslant0\}\) 是 \(E\) 上以 \(P\) 为转移矩阵的相互独立的 Markov 链，初分布分别为 \(\mu\) 和 \(\nu\) 令
Remark：\(Y_{n}\) 的存在性需要保证，但是存在性证明比较复杂所以跳过
下面这个构造方法叫做耦合方法(概率论研究的常用方法)：
\[\{Z_n=(X_n,Y_n):n\geqslant0\}\]
则它为 \(E\times E\) 上以 \(\mu\times\nu\) 为初分布的马氏链，转移矩阵记为
Remark：\(\mu \times \nu\) 是乘积测度(Measure Theory)
\[\overline{P}\triangleq P\otimes P,\]
\[A\otimes B=\begin{bmatrix}a_{11}B&\cdots&a_{1n}B\\\vdots&\ddots&\vdots\\a_{m1}B&\cdots&a_{mn}B\end{bmatrix}.\]
其中 \(\otimes\) 表示 Kronecker 积，即
\[\overline{P}_{(i,j)(k,l)}=P_{ik}P_{jl}\quad\forall(i,j)(k,l)\in E\times E\]
自行验证 \(\overline{P}_{(i,j)(k,l)}^{(n)}=P_{ik}^{(n)}P_{jl}^{(n)}\)
Step1. 证明 \(Z_{n}\) 不可约非周期
由于 \(P\) 不可约，所以存在 \(N_{1},N_{2}\),使得 \(\forall(i,j)(k,l)\in E\times E\)
\[P_{ik}^{(n_1)}>0,\:P_{jl}^{(n_2)}>0,\quad\forall n_1>N_1,\:n_2>N_2\]
当 \(n>\max\{N_{1},N_{2}\}\) 时，
\[\overline{P}_{(i,j)(k,l)}^{(n)}=P_{ik}^{(n)}P_{jl}^{(n)}>0\]
即 \(\overline{P}\) 不可约。
由于 \(P\) 非周期，所以对任意 \(i,j\in E\)
\[\gcd\{n:P_{ii}^{(n)}>0\}=1,\quad\gcd\{n:P_{jj}^{(n)}>0\}=1\]
那么
\[\gcd\{n:\overline{P}_{(i,j)(i,j)}^{(n)}=P_{ii}^{(n)}P_{jj}^{(n)}>0\}=1\]
即 \(\bar{P}\) 非周期。
Step2. \(\overline{P}\) 的不变分布为
\[\overline{\pi}_{(i,j)}=\pi_i\pi_j\]
不难自行验证。
Step3. 证明 \(\{X_{n}:n\geqslant0\}\) 与 \(\{Y_{n}:n\geqslant0\}\) 迟早相遇。
因为 \(P\) 不可约且存在不变分布，那么 \(Z_{n}\) 是常返的。令
\[\tau=\inf\{n\geqslant0:X_n=Y_n\}.\]
它是 \(\{X_{n}:n\geqslant0\) 与 \(\{Y_{n}:n\geqslant0\}\) 的相遇时刻，即 \(\{Z_{n}:n\geqslant0\}\) 首达对角线
\[\overline D\triangleq\{(i,i):i\in E\}\]
的时间，他不会超过 \(Z_{n}\) 首达某个具体状态 \((i,i)\) 的时间，即
\[\tau\leqslant\tau_{(i,i)}\triangleq\inf\{n\geq0:Z_n=(i,i)\}\]
由于 \(Z_n\) 常返，所以
\[P(\tau_{(i,i)}<\infty)=1.\]
那么 \(P(\tau<\infty)=1\)
Step4. 证明在 \(\{X_{n}:n\geqslant0\}\) 与 \(\{Y_{n}:n\geqslant0\}\) 相遇之后，它们有同样的分布(unbelievable)，即
\[P(X_n=j,\tau\leqslant n)=P(Y_n=j,\tau\leqslant n)\]
假设 \(\{X_{n}:n\geqslant0\}\) 与 \(\{Y_{n}:n\geqslant0\}\) 在时刻 \(m\) 相遇于状态 \(i\)。
直观上，那么从时刻 \(m\) 开始重新计时的话，它们都是从 \(i\) 出发以 \(P\) 为转移矩阵的马氏链，从而它们在任何时刻有相同的分布。严格的证明如下：
\[\begin{aligned}
P(X_{n}=j,\tau\leqslant n)& =\sum_{m=0}^{n}\sum_{i\in E}P(X_{n}=j,\tau=m,Z_{m}=(i,i)) \\
&=\sum_{m=0}^n\sum_{i\in E}P(\tau=m,Z_m=(i,i))P(X_n=j|\tau=m,Z_m=(i,i)).
\end{aligned}\]
注意到
\[\{\tau=m,Z_m=(i,i)\}=\{Z_0,\cdots,Z_{m-1}\notin\overline D,Z_m=(i,i)\}.\]
把 \(m\) 视为现在的时间，由 \(Z_{n}\) 的 Markov 性
\[\begin{aligned}
P(X_{n}=j|\tau=m,Z_{m}=(i,i))& =P(X_{n}=j|Z_{m}=(i,i)) \\
&=P(X_{n}=j|X_{m}=i,Y_{m}=i) \\
&=P(X_{n}=j|X_{m}=i)=P_{ij}^{(n-m)}.\quad(X_{n},Y_{n}\text{独立})
\end{aligned}\]
所以
\[P(X_n=j,\tau\leqslant n)=\sum_{m=0}^n\sum_{i\in E}P(\tau=m,Z_m=(i,i))P_{ij}^{(n-m)}.\]
同理，
\[\begin{aligned}
P(Y_{n}=j,\tau\leqslant n)&=\sum_{m=0}^{n}\sum_{i\in E}P(\tau=m,Z_{m}=(i,i))P(Y_{n}=j|Z_{m}=(i,i))\\
&=\sum_{m=0}^{n}\sum_{i\in E}P(\tau=m,Z_{m}=(i,i))P_{ij}^{(n-m)}.\end{aligned}\]
因此 \(P(X_{n}=j,\tau\leqslant n)=P(Y_{n}=j,\tau\leqslant n).\)
Step5. 注意到
\[\begin{aligned}
P(X_n=j)&=P(X_n=j,\tau\leq n)+P(X_n=j,\tau>n)\\
P(Y_n=j)&=P(Y_n=j,\tau\leq n)+P(Y_n=j,\tau>n)
\end{aligned}\]
于是
\[\begin{aligned}
\sum_{j\in E}\lvert P(X_{n}=j)-P(Y_{n}=j)\rvert & =\sum_{j\in E}\lvert P(X_{n}=j,\tau>n)-P(Y_{n}=j,\tau>n)\rvert \\
&\leqslant\sum_{j\in E}(P(X_{n}=j,\tau>n)+P(Y_{n}=j,\tau>n)) \\
&=2P(\tau>n)\overset{n\to\infty}{\longrightarrow}0.\quad(\text{由于}P(\tau<\infty)=1)
\end{aligned}\]
特别地，取 \(X_{n}\) 和 \(Y_{n}\) 的初分布分别为 \(\mu=\delta_{i}(Dirac\ mass)\) 和 \(\nu=\pi\)，那么
\[P(X_n=j)=P_{ij}^{(n)},\quad P(Y_n=j)=\pi_j.\]
定理即证。
注 1.不可约 Markov 链中，非周期正常返的状态称为遍历态 (Ergodic state)
注 2.这里构造 \(Z_{n}\) 的方法称为耦合方法 (Coupling Method)，是概率论中非常重要的证明方法，由于 \(X_{n}\) 和 \(Y_n\) 是独立的，这种特殊的耦合称为独立耦合。一般地，两个概率分布 \(\mu\) 和 \(\nu\) 的耦合 (Coupling) 定义为同一个概率空间上的一对随机变量 \((X,Y)\) ，满足
\[P\{X=x\}=\mu(x),\quad P\{Y=y\}=\nu(y).\]
注 3.还可以通过更新定理证明，参考《随机过程及其应用》，陆大䋮，张颢，清华大学出版社 定理 7.3。
定理 6.13 讨论了正常返、非周期情形 \(P_{ij}^{(n)}\) 的极限，对于其他情况可以总结为下面定理。
Theorem 6.14
\(\{X_{n}\}\) 是不可约常返的 Markov 链，那么
(1) 若 j 是零常返状态，则
\[\lim_{n\to\infty}P_{ij}^{(n)}=0;\]
(2) 若 \(j\) 是正常返周期状态，周期为 \(d_{j}\) ，则
\[\begin{aligned}\lim_{n\to\infty}P_{ij}^{(nd_j)}=\frac{d_j}{\mu_{jj}}\end{aligned}\]
其中 \(\mu_{jj}\triangleq\sum\limits_{n=1}^{\infty}nf_{ij}^{(n)}\) 为平均返回时间。
书上的例子留作阅读学习作业。
不可约 Markov 链的分类总结如下：
- 不可约
- 常返
- 正常返 \(\iff\) 有不变分布
- \(P_{ij}^{(n)}\to \pi_{j}\)（非周期）
- \(\frac{1}{n}\sum\limits_{k=0}^{n}P_{ij}^{(k)}\to \pi_{j}\)（周期）
- 零常返：\(P_{ij}^{(n)}\to 0\)
- 非常返：\(P_{ij}^{(n)}\to 0\)