一、马尔可夫链
1.1. 马尔可夫假设
考虑一组随机变量 $X_1,X_2,\dots,X_n$。我们要完全把握这组随机变量，就需要了解其联合分布。由于联合分布可能非常复杂，一个常用的技巧是引入条件概率：
\[\begin{equation} \begin{aligned} P(X_1,X_2,\dots,X_n) &= P(X_n\mid X_{n-1},\dots,X_1) P(X_{n-1},\dots,X_1)\\ &= P(X_n\mid X_{n-1},\dots,X_1) P(X_{n-1}\mid X_{n-2},\dots,X_1) P(X_{n-2},\dots,X_1)\\ &=\cdots\\ &= P(X_1) \prod_{k=2}^{n} P(X_k\mid X_{k-1},\dots,X_1) \end{aligned} \end{equation}\]这样就把一个 $n$ 元联合分布转换为了 $n$ 个一元条件概率的乘积。看似问题变得简单了，但实际上这只是把复杂性转移到了条件上，而求解条件概率往往比原问题更加困难。
想要真正降低难度，只有引入假设。因此，我们这里引入著名的马尔可夫假设：
\[\begin{equation} P(X_k\mid X_{k-1},\dots,X_1)=P(X_k\mid X_{k-1}) \end{equation}\]即无论有多少个条件，要分析的随机变量都只与【在某个维度上最近】的那个条件相关。
因此，在马尔可夫假设下，我们有：
\[\begin{equation} \begin{aligned} P(X_1,X_2,\dots,X_n) &= P(X_1) \prod_{k=2}^{n} P(X_k\mid X_{k-1}) \end{aligned} \end{equation}\]这样就把 $n$ 元关联转为二元关联，这才是真正的降低了问题的复杂性。
1.2. 马尔可夫过程
考虑一个离散时间、离散状态的随机过程 $X_n$ 。我们称 $X_n$ 为马尔可夫过程（马尔可夫链），或 $X_n$ 具有马尔可夫性，当且仅当任取 $n$ 都有：
\[\begin{equation} P(X_{n+1}\mid X_{n},X_{\lt n})=P(X_{n+1}\mid X_{n}) \label{eq:markov-1} \end{equation}\]马尔可夫性是指：未来的状态 $X_{n+1}$ 只与当前的状态 $X_{n}$ 相关，与过去的状态 $X_{\lt n}$ 无关。从另一个角度来看，在现在的状态已知的条件下，过去和未来的状态是条件独立的：
\[\begin{equation} P(X_{n+1},X_{\lt n}\mid X_n)= P(X_{n+1}\mid X_n) P(X_{\lt n}\mid X_n) \label{eq:markov-2} \end{equation}\]附录1中给出了马尔可夫性两种表述的等价性证明。
1.3. 平稳性假设
上面我们已经知道，在马尔可夫假设下，一个 $n$ 元联合分布可以被简化为 $n$ 个二元条件分布的乘积：
\[\begin{equation} P(X_{n_k},X_{n_{k-1}},\dots,X_{n_1}) = P(X_{n_k}\mid X_{n_{k-1}})\cdots P(X_{n_2}\mid X_{n_1})P(X_{n_1}) \end{equation}\]我们现在来讨论如何计算这些二元条件分布。
为了简洁起见，下面的讨论中我们假设状态空间 $S$ 为正整数集 $\mathbb{Z}^+$。
定义转移概率为：
\[\begin{equation} P_{ij}(m,n):= P(X_n=j\mid X_m=i) \end{equation}\]并引入如下的平稳性假设。平稳马尔可夫链是指：
\[\begin{equation} P_{ij}(m,n)=P_{ij}(n-m) \end{equation}\]即转移概率只依赖于两个时刻的差值 $n-m$。
从状态转移图的角度来看，马尔可夫链的平稳性是指：从任意两个结点之间的转移概率只与转移路径的步数有关，而与具体的路径无关。
1.4. Chapman-Kolmogorov 方程
因此，我们想要完整地了解一个马尔可夫链，就是要求解下面的转移概率：
\[\begin{equation} P_{ij}(n) \end{equation}\]这表示经过 $n$ 步后从状态 $i$ 到状态 $j$ 的概率。
Chapman-Kolmogorov 方程很好地解决了这个问题。C-K 方程表明，上述转移概率可以被如下分解：
\[\begin{equation} P_{ij}(m+n) = \sum_{k\in S} P_{ik}(m) P_{kj}(n) \end{equation}\]C-K 方程的证明放在附录2中。
C-K 方程的证明很简单，但其思想是非常深刻的。C-K 方程考虑了从 $i$ 到 $j$ 的路径上的任一个中间结点 $k$，并把所有在【给定步数】内到达中间结点的路径全部收缩为一条路径。这是一种基于空间分解 (Spatial Decomposition) 的思想，根据不同路径之间的某种共性（同一步数达到同一结点）来合并，从而逐步简化问题（长度缩短、条数变小），直到容易求解。
从数学形式上看 C-K 方程，这正好是矩阵乘法的形式。因此，C-K 方程更本质的表达形式是利用下述的状态转移矩阵：
\[\begin{equation} P(m+n)=\left( P_{i,j}(m+n) \right)_{ S\times S} \end{equation}\]在矩阵形式下，C-K 方程表达为：
\[\begin{equation} P(m+n)=P(m)P(n) \end{equation}\]也就是说，我们有：
\[\begin{equation} P(n) = P(n-1)P(1) = \cdots = P^n(1) \label{eq:c-k-matrix} \end{equation}\]其中，$P(1)$ 是一步转移矩阵。这个矩阵满足：
- 非负性：$P_{ij}(1)\geq 0$。
- 行和为 1：$\sum_{j\in S} P_{ij}(1)=1$。
至此，我们就顺利求解了 $P(n)$ 的形式。
二、马尔可夫链的常返性
下面我们将深入探讨马尔可夫链中一种被称为常返性的重要性质。
为什么我们要关注常返态？下面我们将指出，当转移步数 $n\to\infty$ 时，马尔可夫链几乎不可能访问非常返态。
2.1. 基础概念定义
首先我们定义一些新的概念。
可达性 (Reachability) 我们称状态 $i$ 可达状态 $j$，当且仅当存在转移步数 $n$，使得 $P_{ij}(n) \gt 0$。显然，可达性是具有传递性的。
相通性 (Commutativity) 我们称状态 $i$ 和状态 $j$ 是相通的，当且仅当 $i$ 可达 $j$ 且 $j$ 可达 $i$。显然，相通性也是传递关系。
闭集 (Closed Set) 我们称某个状态子集 $C\subseteq S$ 是闭集，当且仅当任取 $i\in C,j\notin C$，都有 $i$ 不可达 $j$。
也就是说不存在转移路径从闭集内的状态转移到闭集外的状态，即一旦进去闭集里就再也出不来了。
利用闭集，我们可以对马尔可夫链进行约化 (Reduction)，因为闭集中的状态独自构成一个独立的马尔可夫链。在对闭集研究清楚之后，我们就可以在某种意义上把整个闭集看作一个状态，再放到原来的状态集合中进行研究。
不可约 (Irreducible) 我们称一个马尔可夫链是不可约的，有两种等价的定义：
- $S$ 没有闭的真子集。
- $S$ 中的任意两个状态都是相通的。
附录3中展示了这两种定义的等价性。
更进一步地，如果一个马尔可夫链是可约的，那么它的一步转移矩阵 $P(1)$ 可以通过一些对称的行列交换操作（合同变换）转换为如下的分块矩阵：
\[\begin{equation} P(1)\simeq \begin{pmatrix} P&R\\0&Q \end{pmatrix} \end{equation}\]左下角的零矩阵对应的行下标就是闭集，因为闭集中的状态不能出去。
常返态 (Recurrent State) 我们称状态 $i$ 是常返的，当且仅当
\[\begin{equation} \sum_{n=1}^{\infty} f_{ii}(n)=1 \end{equation}\]其中，$f$ 表示首达概率。
首达概率 (First Passage Probability) 从状态 $i$ 经过 $n$ 步转移到达状态 $j$ 的首达概率定义为：
\[\begin{equation} f_{ij}(n) = P(X_n=j,j\notin X_{[1:n-1]}\mid X_0=i) \end{equation}\]对于固定的起点和终点，首达概率的求和同时有上界和下界：
\[\begin{equation} 0\leq \sum_{n}^{\infty}f_{ij}(n)\leq 1 \end{equation}\]但对于转移概率来说，只有：
\[\begin{equation} 0\leq \sum_{n}^{\infty}P_{ij}(n)\leq \infty \end{equation}\]2.2. 首达概率和转移概率
首达概率和转移概率存在如下关系：
\[\begin{equation} P_{ij}(n)= \sum_{k=1}^n f_{ij}(k)P_{jj}(n-k) \label{eq:transition-first} \end{equation}\]这个公式是比较好理解的。因为从 $i$ 转移到 $j$ 的所有路径，就是首达概率对应的路径加上从 $j$ 到 $j$ 上兜圈的路径。这是一种时间分解 (Temporal Decomposition) 的思想，按照首达路径的长度对所有的转移路径进行分类处理。公式的证明放在附录4。
观察公式 \eqref{eq:transition-first}，不难发现这是一个卷积的结构。因此，我们可以通过生成函数来在变换域上分析这个问题。
定义 $P_{ij}(0)=\mathbb{I}(i=j)$，则生成函数为：
\[\begin{equation} \begin{aligned} P_{ij}(z) &= \sum_{n=0}^{\infty} P_{ij}(n)z^n\\ &= P_{ij}(0)+ \sum_{n=1}^{\infty} P_{ij}(n)z^n\\ &= \mathbb{I}(i=j)+ \sum_{n=1}^{\infty} \sum_{k=1}^n f_{ij}(k) P_{jj}(n-k) z^n\\ &= \mathbb{I}(i=j)+ \sum_{k=1}^{\infty} \sum_{n=k}^{\infty} f_{ij}(k) P_{jj}(n-k) z^n\\ &= \mathbb{I}(i=j)+ \sum_{k=1}^{\infty} f_{ij}(k) z^{k} \sum_{n=k}^{\infty} P_{jj}(n-k) z^{n-k}\\ &= \mathbb{I}(i=j)+ \sum_{k=1}^{\infty} f_{ij}(k) z^{k} \sum_{n=0}^{\infty} P_{jj}(n) z^{n} \end{aligned} \end{equation}\]定义首达概率的生成函数为：
\[\begin{equation} F_{ij}(z) = \sum_{k=1}^{\infty} f_{ij}(k) z^{k} \end{equation}\]则有
\[\begin{equation} P_{ij}(z) = \mathbb{I}(i=j)+ F_{ij}(z) P_{jj}(z) \label{eq:transition-first-z} \end{equation}\]当 $i=j$ 时，我们有：
\[\begin{equation} \begin{aligned} P_{ii}(z) &= 1+ F_{ii}(z) P_{ii}(z) \end{aligned} \end{equation}\]解得
\[\begin{equation} P_{ii}(z)=\frac{1}{1-F_{ii}(z)} \end{equation}\]当 $z\to 1^{-}$，上式变为：
\[\begin{equation} \sum_{n=0}^{\infty} P_{ii}(n) = \frac{1}{1-\sum_{n=1}^{\infty} f_{ii}(n)} \end{equation}\]当状态 $i$ 是常返态时，上式右侧的分母为 0。因此我们可以通过判断等式左侧这个正项级数的敛散性来判断 $i$ 是否是常返态，即如果级数发散：
\[\begin{equation} \sum_{n=0}^{\infty} P_{ii}(n)= \infty \end{equation}\]则状态 $i$ 是常返态。反之亦然。
2.3. $n$ 维随机游动的常返性
2.3.1. 一维随机游动
考虑一个粒子从零点开始，在整数轴上进行随机游动。每一步以概率 $p$ 向右移动 1，以概率 $q=1-p$ 向左移动 1。我们希望考察零点的常返性。
首先，当 $n$ 为奇数时，粒子不可能位于零点。当 $n$ 为偶数时，粒子回到零点表示向左和向右各走了 $n/2$ 步。
也就是说，转移概率为
\[\begin{equation} P_{00}(n)= \begin{cases} 0,&n=2k+1\\ \binom{2k}{k}p^kq^k,&n=2k \end{cases} \end{equation}\]因此，我们希望判断无穷级数：
\[\begin{equation} \sum_{k=0}^{\infty}\binom{2k}{k}p^kq^k \end{equation}\]的敛散性。
根据斯特林公式，我们有下面的同阶量：
\[\begin{equation} n! \sim \left(\frac{n}{e}\right)^n \sqrt{2\pi n} \end{equation}\]因此，
\[\begin{equation} \begin{aligned} \sum_{k=0}^{\infty} \binom{2k}{k}p^kq^k &= \sum_{k=0}^{\infty} \frac{(2k)!}{k!\cdot k!} p^kq^k\\ &\sim \sum_{k=0}^{\infty} \frac{ \left(\frac{2k}{e}\right)^{2k} \sqrt{4\pi k} }{ \left(\frac{k}{e}\right)^{2k} (2\pi k) } p^kq^k\\ &\sim \sum_{k=0}^{\infty} \frac{1}{\sqrt{k}}(4pq)^k\\ \end{aligned} \end{equation}\]由均值不等式，
\[\begin{equation} 4pq\leq (p+q)^2=1 \end{equation}\]因此，当 $4pq=1$，即 $p=q=\frac{1}{2}$ 时，原级数
\[\begin{equation} \sum_{k=0}^{\infty}\frac{1}{\sqrt{k}}=\infty \end{equation}\]发散，即零点是常返态。
否则，原级数收敛，此时零点不是常返态。
2.3.2. 二维随机游动
我们仅考虑平衡情况，即每一步中粒子以 $p=\frac{1}{4}$ 的概率向上/下/左/右移动。
和一维的情况相同，当步数为奇数时，粒子不可能回到零点，因此我们只需考虑步数为 $2n$ 的情况。
除了整体步数要是偶数，想要回到零点还要求向左=向右、向上=向下。我们设向左/右走了 $k$ 步，则向上/下分别走了 $n-k$ 步。因此，回到零点的转移概率为：
\[\begin{equation} \begin{aligned} P_{00}(2n) &= \sum_{k=0}^{n} \frac{(2n)!}{k!k!(n-k)!(n-k)!} p^{2n}\\ &= p^{2n} \frac{(2n)!}{(n!)^2} \sum_{k=0}^{n} \left(\frac{n!}{k!(n-k)!}\right)^2\\ &= p^{2n} \binom{2n}{n} \sum_{k=0}^{n} \binom{n}{k}^2\\ &= p^{2n} \binom{2n}{n} \sum_{k=0}^{n} \binom{n}{k} \binom{n}{n-k}\\ &= p^{2n} \binom{2n}{n} \binom{2n}{n}\\ &= p^{2n} \binom{2n}{n}^2\\ \end{aligned} \end{equation}\]上面我们已经求出了这个组合数的阶：
\[\begin{equation} \binom{2n}{n}\sim \frac{4^n}{\sqrt{n}} \end{equation}\]因此，这个转移概率的阶为：
\[\begin{equation} \begin{aligned} P_{00}(2n) &= p^{2n} \binom{2n}{n}^2\\ &\sim \left(\frac{1}{4}\right)^{2n} \left(\frac{4^n}{\sqrt{n}}\right)^2\\ &\sim \frac{1}{n} \end{aligned} \end{equation}\]因此，级数
\[\begin{equation} \sum_{n=0}^{\infty} P_{00}(2n) = \sum_{n=0}^{\infty} \frac{1}{n} = \infty \end{equation}\]发散，即零点是二阶随机游动的常返态。
2.3.3. 高维随机游动
在三维的情况下，转移概率的阶为
\[\begin{equation} P_{ii}(2n)\sim n^{-\frac{3}{2}} \end{equation}\]级数收敛，此时零点已经不是常返态了。
更高维的情况也是这样。只有在一维和二维的等概率游走时，零点才是常返态。
2.4. 非常返态的性质
通过上面的结论我们可以知道，如果状态 $j$ 是非常返的 (Transient)，那么其转移概率的无穷级数
\[\begin{equation} \sum_{n=0}^{\infty} P_{jj}(n)\leq \infty \end{equation}\]这意味着转移概率有如下的渐进行为：
\[\begin{equation} \lim_{n\to\infty}P_{jj}(n)=0 \end{equation}\]我们希望将这个结论继续往前推进一些。这个转移概率的起点和终点都是状态 $j$，我们希望探究，如果状态 $j$ 是非常返的，那么从任意的起点 $i$ 到 $j$ 的转移概率是否也有类似的渐进性质。
答案是肯定的。
事实上，由公式 \eqref{eq:transition-first-z}，当 $i\neq j$ 时，我们有：
\[\begin{equation} P_{ij}(z) = F_{ij}(z) P_{jj}(z) \end{equation}\]当 $z\to 1^{-}$ 时，我们有：
\[\begin{equation} \sum_{n=0}^{\infty} P_{ij}(n) = \sum_{n=1}^{\infty} f_{ij}(n) \sum_{n=0}^{\infty} P_{jj}(n) \end{equation}\]由于等式右侧的两个级数均收敛，因此等式左侧的级数也是收敛的：
\[\begin{equation} \sum_{n=0}^{\infty} P_{ij}(n) \lt\infty \end{equation}\]也就是说，如果终点 $j$ 非常返，那么任取起点 $i$ 都有
\[\begin{equation} \lim_{n\to\infty}P_{ij}(n)=0 \label{eq:transient} \end{equation}\]也就是说，当 $n$ 充分大之后，非常返的状态就几乎不会被访问到。
2.5. 相通状态的常返性
下面我们将证明，如果状态 $i$ 和状态 $j$ 是相通的，那么它们具有相同的常返性。
如果 $i$ 和 $j$ 相通，根据定义，一定能够找到两个步数 $m,n\in\mathbb{N}$，使得：
\[\begin{equation} P_{ij}(m)\gt 0,P_{ji}(n)\gt 0 \end{equation}\]考虑从 $i$ 出发经过 $m+n+k$ 步回到 $i$ 的转移概率，根据 C-K 方程，我们有：
\[\begin{equation} P_{ii}(m+n+k) \geq P_{ij}(m) P_{jj}(k) P_{ji}(n) \end{equation}\]等式两端对 $k$ 求和得：
\[\begin{equation} \sum_{k=0}^{\infty} P_{ii}(m+n+k) \geq \sum_{k=0}^{\infty} P_{ij}(m) P_{jj}(k) P_{ji}(n) \end{equation}\]如果 $j$ 是常返态，此时
\[\begin{equation} \sum_{k=0}^{\infty}P_{jj}(k)=\infty \end{equation}\]由于上式右端的剩下两项都大于0，因此右端发散，所以上式左端也发散。
又由于
\[\begin{equation} \sum_{n'=0}^{\infty}P_{ii}(n')\geq \sum_{k=0}^{\infty}P_{ii}(m+n+k)=\infty \end{equation}\]因此 $i$ 也是常返的。
反之亦然。
一个直接的推论是，如果一个状态集 $S$ 是不可约的，那么其中的每个状态都是相通的，也就是说这些状态的常返性都相同。
2.6. 有限状态马尔可夫链的常返性
下面我们考虑有限状态的马尔可夫链，即状态空间为：
\[\begin{equation} S=\lbrace 1,2,\dots,N\rbrace \end{equation}\]中每个状态的常返性。
我们希望证明，有限状态的马尔可夫链一定存在常返态。
任取步数 $n$ 和起点 $i$，我们一定有：
\[\begin{equation} \sum_{j=1}^{N} P_{ij}(n)=1 \end{equation}\]也就是说，当 $n\to\infty$ 时，上式的极限也是1:
\[\begin{equation} \begin{aligned} 1 &= \lim_{n\to\infty}\sum_{j=1}^{N} P_{ij}(n)\\ &= \sum_{j=1}^{N} \lim_{n\to\infty} P_{ij}(n)\\ \end{aligned} \end{equation}\]如果所有的状态都是非常返的，由公式 \eqref{eq:transient}，上面求和里的极限为 0。求和又只有有限项，因此
\[\begin{equation} 1=\sum_{j=1}^{N} \lim_{n\to\infty} P_{ij}(n)=0 \end{equation}\]矛盾。因此有限状态的马尔可夫链一定存在常返态。
更进一步地，我们得到了如下的重要结论：
一个【有限状态】且【不可约】的马尔可夫链中，所有状态都是常返态。
这是判断常返性的一个非常方便的方法。我们不需要去考察无穷级数的敛散性，不用计算任何的首达概率和转移概率，只需要看看转移图是不是不可约的，就能直接判断常返态。
2.7. 常返态的返回次数
记随机变量 $T_i$ 为从 $i$ 出发后返回 $i$ 的次数：
\[\begin{equation} T_i= \sum_{n=1}^{\infty} \mathbb{I}(X_n=i) \end{equation}\]我们来考察这个访问次数的期望：
\[\begin{equation} \begin{aligned} \mathbb{E}\left[ T_i \right] &= \mathbb{E}\left[ \sum_{n=1}^{\infty} \mathbb{I}(X_n=i) \mid X_0=i \right]\\ &= \sum_{n=1}^{\infty} \mathbb{E}\left[ \mathbb{I}(X_n=i) \mid X_0=i \right]\\ &= \sum_{n=1}^{\infty} P\left( X_n=i \mid X_0=i \right)\\ &= \sum_{n=1}^{\infty} P_{ii}(n) \end{aligned} \end{equation}\]因此，如果状态 $i$ 是常返的，那么 $T_i$ 的期望为 $\infty$。
我们还可以从另外一个角度来计算这个期望。考察随机事件 $T_i=k$ 的概率 $P(T_i=k)$。这个随机事件表示从 $i$ 出发后，还有 $k$ 次返回 $i$，后面就再也不会返回 $i$。
我们先考虑 $k=1$ 的场景，即从 $i$ 出发后，只返回一次 $i$。返回一次的概率就是首达概率的求和：
\[\begin{equation} f_{ii}=\sum_{n=1}^{\infty}f_{ii}(n) \end{equation}\]而在第一次之后再也不返回 $i$ 的概率就是 $1-f_{ii}$。因此，当 $k=1$ 时我们有
\[\begin{equation} P(T_i=1)=f_{ii}(1-f_{ii}) \end{equation}\]进一步，当 $k=2$ 时，由于马尔可夫性，第一次返回 $i$ 后面的过程就和 $k=1$ 时相同。因此
\[\begin{equation} P(T_i=2)=f_{ii}^2(1-f_{ii}) \end{equation}\]以此类推，我们有：
\[\begin{equation} \begin{aligned} P(T_i=k) &=f_{ii}^k(1-f_{ii})\\ &=f_{ii}\cdot f_{ii}^{k-1}(1-f_{ii}) \end{aligned} \end{equation}\]因此，$T_i$ 服从参数为 $1-f_{ii}$ 的几何分布（前面还有个常数 $f_{ii}$）。因此其期望为
\[\begin{equation} \begin{aligned} \mathbb{E}\left[ T_i \right] &= \frac{f_{ii}}{1-f_{ii}} \end{aligned} \end{equation}\]当 $i$ 为常返态时，
\[\begin{equation} f_{ii}=\sum_{n=1}^{\infty}f_{ii}(n)=1 \end{equation}\]此时均值为 $\infty$。
进一步地，定义 $g_{ij}(m)$ 为从 $i$ 出发后至少 $m$ 次经过 $j$ 的概率。因此，至少有 $m$ 次返回 $i$ 的概率就是：
\[\begin{equation} g_{ii}(m)=P(T_i\geq m) \end{equation}\]我们已经知道了 $P(T_i=k)$，要算这个概率是很简单的。但我们这里向读者展示了一种新的计算方法，从时间分解的角度来看待返回次数。
\[\begin{equation} \begin{aligned} g_{ii}(m) &=P(T_i\geq m)\\ &= \sum_{n=1}^{\infty} f_{ii}(n) P(T_i\geq m-1)\\ &= f_{ii}\cdot g_{ii}(m-1)\\ &=\cdots\\ &= f_{ii}^m \end{aligned} \end{equation}\]当返回次数 $m\to\infty$ 时，有极限：
\[\begin{equation} g_{ii}=P(T_i=\infty)=\lim_{m\to\infty}g_{ii}(m)= \begin{cases} 1,f_{ii}=1\\ 0,f_{ii}\lt 1 \end{cases} \end{equation}\]也就是说，如果 $i$ 是常返态，那么必然会无限次地返回，否则返回次数必然是有限的。这个结果在概率论中称为 0-1 率，即概率只有0和1两种取值。这类概率其实并不多见。
以上的三个结论都体现出了常返性的“常”，即马尔可夫链中会无限次返回常返态 $i$。
2.8. 常返态只会连接常返态
我们有如下的结论成立。
如果状态 $i$ 是常返态，且 $i$ 可达 $j$，那么 $j$ 也一定可达 $i$，也就是 $i$ 和 $j$ 是相通的。这个结论表明：从常返态出发无论走多远，最终都会回来。
更进一步，由于相通状态的常返性相通，因此 $j$ 也是常返态。这也就是说，【常返态只会连接常返态】。
这是一个非常强的结论，可以帮助我们快速地判断一个状态是否是常返态。我们用下面这个例子来说明。
- 左侧：有限状态+不可约（两两连通），因此全部都是常返态。
- 中间：右上角结点出去了就回不来了，不是常返态。其他的都是常返态。
- 右侧：离开下面三个结点就回不去了，都不是常返态。右上角的结点是常返态。
下面我们从空间分解的角度来证明这个结论。
由于 $i$ 可达 $j$，因此存在 $n\in\mathbb{N}$，使得 $P_{ij}(n)\gt 0$。
考虑从 $j$ 出发，无穷多次到达 $i$ 的概率：
\[\begin{equation} \begin{aligned} g_{ji} &= \sum_{k\in S} P_{jk}(n) g_{ki} \end{aligned} \end{equation}\]即从 $j$ 出发经过 $n$ 步到达某个中间状态 $k$，再从 $k$ 无穷多次回到 $i$。
当 $j=i$ 时，得
\[\begin{equation} \begin{aligned} 1&=g_{ii}\\ &= \sum_{k\in S} P_{ik}(n) g_{ki} \end{aligned} \end{equation}\]又因为
\[\begin{equation} \sum_{k\in S}P_{ik}(n)=1 \end{equation}\]因此，
\[\begin{equation} \sum_{k\in S}P_{ik}(n) = \sum_{k\in S}P_{ik}(n)g_{ki} \end{equation}\]这意味着
\[\begin{equation} \sum_{k\in S}(g_{ki}-1)P_{ik}(n)=0 \end{equation}\]注意到
\[\begin{equation} \begin{aligned} g_{ki}-1&\leq 0\\ P_{ik}(n)&\geq 0 \end{aligned} \end{equation}\]因此二者乘积非正。要想求和为0，只可能是每一项都为0。即任取 $k\in S$，都有
\[\begin{equation} (g_{ki}-1)P_{ik}(n)=0 \end{equation}\]考虑 $k=j$ 的那一项，由于 $P_{ij}(n)\gt 0$，说明只能是前面那一项为0，即
\[\begin{equation} g_{ji}=1 \end{equation}\]这不仅说明 $j$ 可达 $i$，更进一步地说明 $j$ 必然会无穷多次地到达 $i$。结论得证。
2.9. 吸收概率与平均命中时间
我们再延伸介绍一下吸收概率与平均命中时间。
考虑某个状态集合 $A$，命中时间定义为
\[\begin{equation} T_i^A=\min \lbrace n:X_n\in A\mid X_0=i \rbrace \end{equation}\]吸收概率定义为
\[\begin{equation} P_i^A=P(T_i^A\lt\infty) \end{equation}\]根据马尔可夫性，我们可以对吸收概率进行空间分解：
\[\begin{equation} P_i^A=\sum_j P_{ij}P_j^A \end{equation}\]因此，写为矩阵形式就是：
\[\begin{equation} \pi^A=P\cdot \pi^A \end{equation}\]平均命中时间就是命中时间的期望：
\[\begin{equation} \begin{aligned} \mathbb{E}[T_i^A] &= \sum_j P_{ij} \mathbb{E}[T_j^A] +1 \end{aligned} \end{equation}\]2.9.1. 赌徒破产问题
我们用著名的赌徒破产问题 (Gambler Ruin Problem) 作为例子来说明。
考虑一个赌徒带着 $n$ 元进入赌场。每场赌局他都有 $p$ 的概率赢 $1$ 元，有 $q$ 的概率输 $1$ 元。我们希望求赌徒破产的概率 $P_{n}$。
显然，这个问题是一个无限状态的马尔可夫链。我们不难写出下面的差分方程：
\[\begin{equation} P_n=p\cdot P_{n+1}+(1-p)\cdot P_{n-1} \end{equation}\]我们先考虑有限状态的情况，即赌徒赢到 $N$ 元时就停止。在这种情况下的通解为：
\[\begin{equation} P_n=\frac{r^n-r^N}{1-r^N} \end{equation}\]其中 $r=q/p$。
令 $N\to\infty$ 得：
- 公平赌局 ($p=q=0.5$)：$P_n=1$，必然破产。
- 不利赌局 ($p\lt q$)：$P_n=1$，必然破产。
- 有利赌局 ($p\gt q$)：$P_n=r^n$，破产概率随着初始资金 $n$ 指数衰减。
三、转移概率的渐近行为
在前面的内容中，我们通过已经对马尔可夫链的常返性建立了较为深入的认识。
下面，我们希望研究马尔可夫链中转移概率的渐近行为：当 $n\to\infty$ 时，$P_{ij}(n)$ 的收敛性是怎么样的。如果收敛，这个收敛值 $P_{ij}$ 与什么有关？
根据马尔可夫假设，过去是可以被忽略的，因此我们可以合理地猜测：收敛值与起点 $i$ 无关，只与终点 $j$ 相关。这样一来，在渐进的意义下，转移概率的过程性就会逐渐消失，变为一个只与终点有关的随机变量，这是一种很深刻的认识。
3.1. 一个简单的例子
考虑只有两个状态的马尔可夫链：$S=\lbrace 0,1\rbrace$，其一步转移概率矩阵为：
\[\begin{equation} P(1)= \begin{pmatrix} 0&1\\1&0 \end{pmatrix} \end{equation}\]我们来分析这个马尔可夫链的转移概率的渐近行为。我们有：
\[\begin{equation} \begin{aligned} P_{00}(n)&=P_{11}(n)=\mathbb{I}(n \text{ is even})\\ P_{01}(n)&=P_{10}(n)=\mathbb{I}(n \text{ is odd}) \end{aligned} \end{equation}\]显然，任何一个转移概率都不存在极限。
3.2. 弱遍历性定理
马尔可夫链的弱遍历性定理 (Weak Ergodic Theorem) 指出，考虑一个不可约马尔可夫链，若终点 $j$ 是常返态，那么任取起点 $i$，转移概率的 Cesaro 平均存在极限：
\[\begin{equation} \lim_{n\to\infty} \frac{1}{n} \sum_{k=1}^{n} P_{ij}(k) = \pi_j \end{equation}\]其中，
\[\begin{equation} \pi_j=\frac{1}{\mathbb{E}[T_i\mid X_0=j]}=\frac{1}{\sum_{n=1}^{\infty}nf_{jj}(n)} \end{equation}\]为平均首次返回时间的倒数。
在上面的例子中，平均首次返回时间均为 2，因此转移概率虽然本身不存在极限，但其 Cesaro 平均存在极限 $\frac{1}{2}$。
- 如果某个状态的 $\pi_j\gt 0$，则我们称该状态是正常返 (positive recurrent) 的。
- 如果 $\pi_j= 0$，我们称该状态是零常返 (null recurrent) 的。
3.3. 强遍历性定理
弱遍历性定理指出，对于不可约但常返的马尔可夫链，转移概率的 Cesaro 平均存在极限。
那么在什么条件下，转移概率本身也是收敛的呢？
3.3.1. 状态的周期
某个状态 $i$ 的周期定义为：
\[\begin{equation} d_i=\gcd\lbrace k\geq 1\mid P_{ii}(k)\gt 0 \rbrace \end{equation}\]特别的，
- 如果 $d_i=1$，我们称状态 $i$ 是非周期 (aperiodic) 的。
- 若集合为空（永远回不来），定义 $d_i=0$。
对周期的直观理解就是：从状态 $i$ 出发，返回 $i$ 的步数必须是周期 $d_i$ 的整数倍。
关于状态的周期我们有如下两个结论成立：
- 如果状态 $i$ 是非周期的，那么存在 $N\in\mathbb{N}$，任取步数 $n\geq N$，都有 $P_{ii}(n)\gt 0$。也就是说，如果状态是非周期的，那么在超过一定步数之后，就每一步都能返回。
- 如果两个状态 $i$ 和 $j$ 是相通的，那么 $d_i=d_j$。（证明见附录5）
3.3.2. 不可约+非周期=收敛
有了周期这个铺垫，下面我们就可以介绍强遍历定理 (Strong Ergodic Theorem)。
强遍历定理指出，在一个不可约的马尔可夫链中，若终点 $j$ 是非周期的，那么任取起点 $i$，转移概率本身存在极限：
\[\begin{equation} \lim_{n\to\infty}P_{ij}(n)=\pi_j \end{equation}\]这个极限只依赖于终点 $j$，且与 Cesaro 平均的极限相同（这是 Cesaro 平均的正则性）。
3.4. 收敛值的分析
现在我们来分析这个收敛值 $\pi_j$。
我们的起点是矩阵形式的 C-K 方程。公式 \eqref{eq:c-k-matrix} 表明，$n$ 步转移方程有如下的递推表示：
\[\begin{equation} P(n)=P(n-1)P(1) \end{equation}\]在等式两边令 $n\to\infty$ 得：
\[\begin{equation} \Pi=\Pi P(1) \end{equation}\]强遍历定理告诉我们，$P_{ij}(n)$ 的极限 $\pi_j$ 与行无关，因此 $\Pi$ 的每一行都是一样的：
\[\begin{equation} \Pi= \begin{pmatrix} \pi_1&\pi_2&\cdots&\pi_n\\ \pi_1&\pi_2&\cdots&\pi_n\\ \vdots&\vdots&\ddots&\vdots\\ \pi_1&\pi_2&\cdots&\pi_n \end{pmatrix} \end{equation}\]因此我们只需要关注某一行即可：
\[\begin{equation} \begin{pmatrix} \pi_1&\pi_2&\cdots&\pi_n \end{pmatrix} = \begin{pmatrix} \pi_1&\pi_2&\cdots&\pi_n \end{pmatrix} \begin{pmatrix} P_{11}&P_{12}&\cdots&P_{1n}\\ P_{21}&P_{22}&\cdots&P_{2n}\\ \vdots&\vdots&\ddots&\vdots\\ P_{n1}&P_{n2}&\cdots&P_{nn} \end{pmatrix} \end{equation}\]注意我们要在不可约和非周期的条件下求解上面的矩阵方程。
下面，我们对这个方程进行一些说明：
第一，这是一个左手方程。我们常见的线性方程的形式是 列向量 = 矩阵 * 列向量，但这个方程的形式是 行向量 = 行向量 * 矩阵。
第二，即使没有不可约和非周期的条件，只要 $P(1)$ 是一个转移概率矩阵，那么这个方程总有非零解（证明见附录6）。
第三，这个矩阵方程的解是一个平稳分布 (stationary distribution)。
如果一个分布 $\pi$ 是一个平稳分布，那么有：
\[\begin{equation} P(X_0=i)=\pi_i\implies \forall n,\ P(X_n=i)=\pi_i \end{equation}\]可以证明，分布 $\pi$ 是一个平稳分布当且仅当 $\pi$ 是矩阵方程 $\pi=\pi P$ 的解（见附录7）。
第四，Cesaro 平均的极限也满足矩阵方程，这也是一个平稳分布。
第五，细致平衡关系。若 $\pi$ 满足
\[\begin{equation} \pi_i P_{ij}=\pi_j P_{ji} \end{equation}\]那么一定有
\[\begin{equation} \pi_i=\sum_k \pi_i P_{ik}=\sum_k \pi_k P_{ki} \end{equation}\]即一定有 $\pi=\pi P$。
3.5. 一些实际应用例子
Case 1.
考虑 3 个状态的马尔可夫链：$S=\lbrace1,2,3\rbrace$。两两状态之间都存在转移概率：$P_{ij}=1/2$。
这是一个有限状态、不可约、全都是常返态、非周期的马尔可夫链。因此，$\pi=\pi P$ 的解同时是转移概率和 Cesaro 平均的极限。
在我们这个例子中，矩阵方程为：
\[\begin{equation} \begin{pmatrix} \pi_1&\pi_2&\pi_3 \end{pmatrix} = \begin{pmatrix} \pi_1&\pi_2&\pi_3 \end{pmatrix} \begin{pmatrix} 0&1/2&1/2\\ 1/2&0&1/2\\ 1/2&1/2&0 \end{pmatrix} \end{equation}\]解得
\[\begin{equation} \pi_1=\pi_2=\pi_3=\frac{1}{3} \end{equation}\]Case 2 (Ehrenfest Model).
考虑一个密闭容器，中间有一个挡板。在起始状态时，挡板的一侧充满了气体分子，另一侧真空。
在某个起始时刻，我们把中间的挡板抽掉，让容器中的气体分子自由扩散，直至达到平衡状态（即每个地方的气体分子密度相同）。
我们希望对这个过程进行建模。
首先，我们确定这个过程的状态空间。我们考察右侧容器中的分子数量 $S=\lbrace 0,\dots,N\rbrace$，其中 $N$ 为起始状态左侧的分子数量。
然后，我们增加两点假设：
- 时间离散化：我们仅在离散时间点 $n\Delta t$ 处考虑状态的转移。
- 在每一个单位时间 $\Delta t$ 内，有且仅有一个分子在左右半边容器之间运动，且所有分子运动的概率都相同。
不难发现，这是一个不可约、有限状态、常返、周期为 2 的马尔可夫链。
Note：由于周期为 2，我们只能断言 Cesaro 平均存在极限，但不能断言转移概率不收敛。因为非周期是转移概率收敛的充分条件而非必要条件。
现在，我们就可以写出这个马尔可夫链的一步转移概率。
根据上面的建模，$P_{ij}$ 表示右侧的分子数量从 $i$ 变为 $j$ 的概率。由于单位时间内有且仅有一个分子在运动，因此：
- 当 $\vert i-j \vert\neq 1$ 时，$P_{ij}=0$。
- 当 $i-j=1$ 时，表示右侧的 $i$ 个分子有一个去到左侧，因此 $P_{ij}=\frac{i}{N}$。
- 当 $i-j=-1$ 时，表示左侧的 $N-i$ 个分子有一个去到右侧，因此 $P_{ij}=\frac{N-i}{N}$。
综上所述，一步转移概率为：
\[\begin{equation} P_{ij}= \begin{cases} \frac{i}{N},&i-j=1\\ \frac{N-i}{N},&i-j=-1\\ 0,&\text{otherwise}\\ \end{cases} \end{equation}\]下面，我们就可以求解矩阵方程 $\pi=\pi P$。
\[\begin{equation} \begin{pmatrix} \pi_0&\pi_1&\cdots&\pi_N \end{pmatrix} = \begin{pmatrix} \pi_0&\pi_1&\cdots&\pi_N \end{pmatrix} \begin{pmatrix} 0 & 1 & 0 & \cdots & 0 & 0 \\ \frac{1}{N} & 0 & \frac{N-1}{N} & 0 & \cdots & 0 \\ 0 & \frac{2}{N} & 0 & \frac{N-2}{N} & \cdots & 0 \\ \vdots & \ddots & \ddots & \ddots & \ddots & \vdots \\ 0 & \cdots & 0 & \frac{N-1}{N} & 0 & \frac{1}{N} \\ 0 & \cdots & 0 & 0 & 1 & 0 \end{pmatrix} \end{equation}\]对应的线性方程组为：
\[\begin{equation} \begin{cases} \pi_0=\frac{1}{N}\pi_1\\ \pi_1=\pi_0+\frac{2}{N}\pi_2\\ \pi_2=\frac{N-1}{N}\pi_1+\frac{3}{N}\pi_3\\ \cdots\\ \pi_k=\frac{N-k+1}{N}\pi_{k-1}+\frac{k+1}{N}\pi_{k+1}\\ \cdots\\ \pi_N=\frac{1}{N}\pi_{N-1}\\ \end{cases} \end{equation}\]代入可以发现：
\[\begin{equation} \pi_k=\binom{N}{k}\pi_0 \end{equation}\]因此：
\[\begin{equation} \sum_{k=0}^{N}\pi_k = \sum_{k=0}^{N}\binom{N}{k}\pi_0\\ = 2^N \pi_0=1 \end{equation}\]解得
\[\begin{equation} \pi_k=\frac{1}{2^N}\binom{N}{k} \end{equation}\]因此，这个马尔可夫链是正常返的。
Case 3 (PageRank).
考虑任意一个无向图，其中包括 $N$ 个结点。某个粒子在图的结点之间随机游走。在某个结点 $i$ 处，以等概率转移到相邻的结点：
\[\begin{equation} P_{ij}= \begin{cases} \frac{1}{d_i},&i:i \to j\\ 0,&\text{otherwise}\\ \end{cases} \end{equation}\]其中 $d_i$ 为结点 $i$ 的度。
我们希望求解这个马尔可夫链的平稳分布。
这个问题甚至比上面的问题还要困难，我们甚至没法写出这个马尔可夫链的一步转移概率，因为我们的图是任意的，没法确定结点之间的可达性。
一个较为合理的猜测是平稳分布的概率正比于结点的度：
\[\begin{equation} \pi_i= \frac{d_i}{\sum_k d_k} \end{equation}\]我们来验证这个猜测的正确性，也就是代入矩阵方程中看看是否成立。
\[\begin{equation} \begin{aligned} \sum_i \pi_i P_{ij} &= \sum_{i:i\to j} \frac{1}{\sum_k d_k}\\ &= \frac{d_j}{\sum_k d_k}\\ &=\pi_j \end{aligned} \end{equation}\]说明这个解是正确的，符合矩阵方程。
四、连续时间马尔可夫链
考虑一个离散状态、连续时间的随机过程 $X(t)$：
\[\begin{equation} \forall n,\forall t_1,\cdots,t_n,\ X(t_1),\cdots,X(t_n)\in\lbrace 1,2,\cdots,N,\cdots\rbrace \end{equation}\]我们称这个随机过程具有马尔可夫性，当且仅当
\[\begin{equation} P(X(t_{n+1})\mid X(t_{n}),X(t_{\lt n})) = P(X(t_{n+1})\mid X(t_{n})) \end{equation}\]对于连续时间马尔可夫链，我们同样可以定义转移概率：
\[\begin{equation} P_{ij}(s,t)= P(X(t)=j\mid X(s)=i) \end{equation}\]同样的，我们也引入平稳性假设，即转移概率只与时间间隔 $t-s$ 有关，而与具体时间点 $t,s$ 无关。
4.1. Kolmogorov Forward-Backward Equation
在连续时间马尔可夫链中，转移概率同样满足 C-K 方程：
\[\begin{equation} P_{ij}(s+t) = \sum_k P_{ik}(s) P_{kj}(t) \end{equation}\]写为矩阵形式，我们有
\[\begin{equation} P(s+t) = P(s)P(t) \end{equation}\]在离散时间的情况下，由于存在最小时间单元，因此我们可以通过递推求出 $n$ 步转移矩阵的具体形式（公式 \eqref{eq:c-k-matrix}）。
然而在连续时间中，我们不能这么做。为此，我们需要引入 Kolmogorov 前进-后退方程。
考虑转移概率矩阵的差分。根据 C-K 方程，我们有两种表达形式：
\[\begin{equation} \begin{aligned} \frac{P(t+\Delta t)-P(t)}{\Delta t} &= \frac{P(t)P(\Delta t)-P(t)}{\Delta t} = P(t)\frac{P(\Delta t)-I}{\Delta t}\\ &= \frac{P(\Delta t)P(t)-P(t)}{\Delta t} = \frac{P(\Delta t)-I}{\Delta t}P(t)\\ \end{aligned} \end{equation}\]上面的式子称为前进 (forward) 方程，下面的式子称为后退 (backward) 方程。
我们令 $\Delta t\to 0$，并定义：
\[\begin{equation} Q= \lim_{\Delta t\to 0} \frac{P(\Delta t)-I}{\Delta t} \end{equation}\]我们得到两个微分方程：
\[\begin{equation} \begin{aligned} \frac{\mathrm{d}}{\mathrm{d}t} P(t)&=P(t)\cdot Q\\ \frac{\mathrm{d}}{\mathrm{d}t} P(t)&=Q\cdot P(t) \end{aligned} \end{equation}\]Kolmogorov 证明了，上面两个微分方程的解是一样的：
\[\begin{equation} P(t)=\exp(Qt) \end{equation}\]因此，在连续时间马尔可夫链中，$Q$ 矩阵的作用就相当于离散时间中的一步转移概率矩阵。
$Q$ 矩阵具有如下的性质。
- 对角线元素非正：$Q_{ii}\leq 0$。
- 非对角线元素非负：$Q_{ij}\geq 0$。
- 行和为 0。
Case（泊松过程的转移概率）
下面我们从马尔可夫链的角度来理解泊松过程。
转移概率 $P_{ij}(t)$ 表示在时间 $t$ 内共发生了 $j-i$ 次事件的概率。因此：
\[\begin{equation} P_{ij}(t) = \begin{cases} \frac{(\lambda t)^{j-i}}{(j-i)!}\exp(-\lambda t),&j\geq i\\ 0,&j<i \end{cases} \end{equation}\]下面我们计算泊松过程对应的 $Q$ 矩阵。对角线元素为
\[\begin{equation} \begin{aligned} Q_{ii} &= \lim_{\Delta t\to 0} \frac{P_{ii}(\Delta t)-1}{\Delta t}\\ &= \lim_{\Delta t\to 0} \frac{\exp(-\lambda \Delta t)-1}{\Delta t}\\ &= -\lambda \end{aligned} \end{equation}\]上次对角线元素为：
\[\begin{equation} \begin{aligned} Q_{i,i+1} &= \lim_{\Delta t\to 0} \frac{P_{i,i+1}(\Delta t)}{\Delta t}\\ &= \lim_{\Delta t\to 0} \frac{\lambda \Delta t\exp(-\lambda \Delta t)}{\Delta t}\\ &= \lambda \end{aligned} \end{equation}\]上三角的其余元素 ($j-i\geq 2$) 为：
\[\begin{equation} \begin{aligned} Q_{ij} &= \lim_{\Delta t\to 0} \frac{P_{ij}(\Delta t)}{\Delta t}\\ &= \lim_{\Delta t\to 0} \frac{\frac{(\lambda \Delta t)^{j-i}}{(j-i)!}\exp(-\lambda \Delta t)}{\Delta t}\\ &= \lim_{\Delta t\to 0} \frac{(\lambda)^{j-i}}{(j-i)!}(\Delta t)^{j-i-1}\exp(-\lambda \Delta t)\\ &= 0 \end{aligned} \end{equation}\]下三角元素显然为 0。
因此，泊松过程对应的 $Q$ 矩阵为：
\[\begin{equation} Q= \begin{pmatrix} -\lambda & \lambda & 0 & \cdots & 0 \\ 0 & -\lambda & \lambda & \cdots & 0 \\ 0 & 0 & -\lambda & \ddots & \vdots \\ \vdots & \vdots & \ddots & \ddots & \lambda \\ 0 & 0 & \cdots & 0 & -\lambda \end{pmatrix} \end{equation}\]4.2. 连续时间马尔可夫链的渐近行为
连续时间马尔可夫链有下面的重要性质：
\[\begin{equation} \exists t_0,P_{ij}(t_0)\gt 0 \implies \forall t,P_{ij}(t)\gt 0 \end{equation}\]也就是说，只要能过去，那么任何时间长度都能过去。
因此，连续时间的马尔可夫链可以理解成是”非周期“的。也就是说当 $t\to \infty$ 时，转移概率矩阵 $P(t)$ 一定存在极限。
在前向方程中令 $t\to \infty$，我们有：
\[\begin{equation} \pi Q=0 \end{equation}\]下面的定理可以将连续时间和离散时间马尔可夫链的极限概率联系起来。
Theorem (Poisson Arrivals See Time Averages, PASTA).
- 考虑连续时间马尔可夫链 $X(t)$。
- $N(t)$ 是一个参数为 $\lambda$ 的泊松过程，且独立于 $X(t)$。设其事件发生时刻为 $T_n$。
- 定义随机过程 $Y_n=X(T_n)$，显然 $Y_n$ 是一个离散时间马尔可夫链，设其一步转移矩阵为 $P^Y$。
我们有
\[\begin{equation} \pi=\pi P^Y\iff\pi Q^X = 0 \end{equation}\]也就是说，我们以泊松过程事件发生时刻观察连续时间马尔可夫链 $X(t)$，得到的离散时间马尔可夫链 $Y_n$ 的极限概率与 $X(t)$ 的极限概率相同。
下面我们来证明这个定理。
根据定义：
\[\begin{equation} \begin{aligned} P^Y &= P^X(T_n-T_{n-1}) \end{aligned} \end{equation}\]由于泊松过程的事件发生间隔 $T_n-T_{n-1}$ 服从参数为 $\lambda$ 的指数分布。因此
\[\begin{equation} \begin{aligned} P^Y &= P^X(T_n-T_{n-1})\\ &= \int_{0}^{\infty} P^X(t) \lambda \exp(-\lambda t) \mathrm{d}t\\ &= -\int_{0}^{\infty} P^X(t) \mathrm{d}\exp(-\lambda t)\\ &= I+ \int_{0}^{\infty} \exp(-\lambda t) \mathrm{d}P^X(t)\\ &= I+ Q \int_{0}^{\infty} \exp(-\lambda t) P^X(t) \mathrm{d}t\\ &= I+ \frac{1}{\lambda} Q P^Y \end{aligned} \end{equation}\]左右同乘向量 $\pi$ 得
\[\begin{equation} \pi P^Y=\pi+\frac{1}{\lambda}\pi QP^Y \end{equation}\]因此，问题得证：
\[\begin{equation} \pi=\pi P^Y \iff \pi Q = 0 \end{equation}\]4.3. M/M/k 排队问题
在前面的内容中，我们用过滤泊松过程解决了 $M/G/\infty$ 的排队问题。其关键原因在于服务体系中的资源是无限的，所以在这类排队问题中不存在等待时间，只有服务时间。
当服务资源有限时，过滤泊松过程就无法解决了。此时，我们需要用到连续时间的马尔可夫链。
具体来说，我们使用下面的生灭过程 (Birth-Death Process) 来建模 M/M/k 排队问题。这个过程包括两个独立的动作：
- 生动作：在 $\Delta t$ 时间内，
- 产生一个后代的概率是时间差的线性函数 $\lambda_i \Delta t + o(\Delta t)$。
- 产生多个后代的概率都是 $o(\Delta t)$。
- 因此，不产生后代的概率是 $1-\lambda_i \Delta t+o(\Delta t)$。
- 灭动作：在 $\Delta t$ 时间内，
- 死亡一个后代的概率是 $\mu_i \Delta t + o(\Delta t)$。
- 死亡多个后代的概率都是 $o(\Delta t)$。
- 因此，不死亡后代的概率是 $1-\mu_i \Delta t+o(\Delta t)$。
对应排队问题中，生动作代表客户到达，灭动作代表客户离开。
4.3.1. 生灭过程的 Q 矩阵
首先，我们来计算生灭过程的概率转移矩阵。
考虑在 $\Delta t$ 时间内，系统的状态不发生变化的概率为
\[\begin{equation} \begin{aligned} P_{ii}(\Delta t) &= (1-\lambda_i \Delta t+o(\Delta t))(1-\mu_i \Delta t+o(\Delta t))\\ &\quad + (\lambda_i \Delta t + o(\Delta t))(\mu_i \Delta t + o(\Delta t))\\ &\quad + (o(\Delta t))^2 \end{aligned} \end{equation}\]系统新增一个后代的概率为
\[\begin{equation} \begin{aligned} P_{i,i+1}(\Delta t) &= (\lambda_i \Delta t + o(\Delta t))(1-\mu_i \Delta t+o(\Delta t))\\ &\quad + (o(\Delta t))(\mu_i \Delta t + o(\Delta t))\\ &\quad + (o(\Delta t))^2 \end{aligned} \end{equation}\]系统减少一个后代的概率为
\[\begin{equation} \begin{aligned} P_{i,i-1}(\Delta t) &= (1-\lambda_i \Delta t + o(\Delta t))(\mu_i \Delta t+o(\Delta t))\\ &\quad + (o(\Delta t))(1-\mu_i \Delta t + o(\Delta t))\\ &\quad + (o(\Delta t))^2 \end{aligned} \end{equation}\]系统状态变化大于等于 2 个的概率为
\[\begin{equation} P_{i,j}(\Delta t)=o(\Delta t),\vert i-j \vert\geq 2 \end{equation}\]因此，Q 矩阵的对角线元素为
\[\begin{equation} \begin{aligned} Q_{ii} &= \lim_{\Delta t\to 0} \frac{P_{ii}(\Delta t)-1}{\Delta t}\\ &=-(\lambda_i+\mu_i) \end{aligned} \end{equation}\]上次对角线元素为
\[\begin{equation} \begin{aligned} Q_{i,i+1} &= \lim_{\Delta t\to 0} \frac{P_{i,i+1}(\Delta t)}{\Delta t}\\ &=\lambda_i \end{aligned} \end{equation}\]下次对角线元素为
\[\begin{equation} \begin{aligned} Q_{i,i-1} &= \lim_{\Delta t\to 0} \frac{P_{i,i-1}(\Delta t)}{\Delta t}\\ &=\mu_i \end{aligned} \end{equation}\]其余元素都是 0。
综上所述，生灭过程的 Q 矩阵为：
\[\begin{equation} Q= \begin{pmatrix} -\lambda_0 & \lambda_0 & & & \\ \mu_1 & -(\lambda_1+\mu_1) & \lambda_1 & & \\ & \mu_2 & -(\lambda_2+\mu_2) & \lambda_2 & \\ & \ddots & \ddots & \ddots & \end{pmatrix} \end{equation}\]4.3.2. M/M/1 问题
M/M/1 排队问题针对客户按照泊松分布的间隔来到和离开的场景。我们希望研究在稳态条件 ($t\to\infty$) 下，系统中的队长（客户数量）的分布。
由上面的内容我们可以知道，这个稳态分布满足下面的矩阵方程：
\[\begin{equation} \pi Q=0 \end{equation}\]其中 $\pi=(\pi_0,\pi_1,\cdots,\pi_n,\cdots)$。
将矩阵方程转为线性方程得：
\[\begin{equation} \begin{cases} \pi_0\lambda_0&=\pi_1\mu_1\\ \pi_0\lambda_0-\pi_1(\lambda_1+\mu_1)+\pi_2\mu_2&=0\\ \pi_1\lambda_1-\pi_2(\lambda_2+\mu_2)+\pi_3\mu_3&=0\\ \cdots \end{cases} \end{equation}\]解得：
\[\begin{equation} \pi_n=\left(\prod_{k=0}^{n-1}\frac{\lambda_{k}}{\mu_{k+1}}\right)\pi_0 \end{equation}\]由于
\[\begin{equation} \sum_{n=0}^{\infty}\pi_n = \pi_0 \left(\sum_{n=1}^{\infty} \prod_{k=0}^{n-1}\frac{\lambda_{k}}{\mu_{k+1}}+1\right) =1 \end{equation}\]上述方程要有解，级数
\[\begin{equation} \sum_{n=1}^{\infty} \prod_{k=0}^{n-1} \frac{\lambda_{k}}{\mu_{k+1}} \end{equation}\]必须收敛，排队系统才能进入稳态。
在 M/M/1 问题中，$\lambda_i=\lambda, \mu_i=\mu$。上面的级数就变成
\[\begin{equation} \sum_{n=1}^{\infty} \left(\frac{\lambda}{\mu}\right)^n \end{equation}\]这个级数是收敛的，当且仅当 $\mu\gt\lambda$。也就是说，当且仅当死亡率大于出生率，M/M/1 系统才能达到稳态。
在 $\mu\gt\lambda$ 的条件下，稳态分布为：
\[\begin{equation} \begin{aligned} \pi_0 &= \frac{1}{\sum_{n=0}^{\infty}\left(\frac{\lambda}{\mu}\right)^n} = 1-\frac{\lambda}{\mu}\\ \pi_n &= \left(1-\frac{\lambda}{\mu}\right) \left(\frac{\lambda}{\mu}\right)^n \end{aligned} \end{equation}\]4.3.3. M/M/k 问题
将 M/M/1 推广到 M/M/k 的关键是研究 $\lambda_i$ 和 $\mu_i$ 在 M/M/k 中是什么情况。
- 到达率仍然与当前系统中的人数无关，因此有 $\lambda_i=\lambda$。
- 离开率 $\mu_i$ 与当前系统中的人数是有关的：
- 当系统中人数 $i$ 不超过系统容量 $k$ 时，离开率是线性的：$\mu_i=i\mu$。
- 当人数超过系统容量时，离开率就变成常数：$\mu_i=k\mu$。
综上所述，在 M/M/k 中有：
\[\begin{equation} \begin{aligned} \lambda_i&=\lambda\\ \mu_i&=\min(i,k)\mu \end{aligned} \end{equation}\]因此，M/M/k 系统能达到稳态的条件是级数
\[\begin{equation} \sum_{n=1}^{\infty} \prod_{l=0}^{n-1} \frac{\lambda_{l}}{\mu_{l+1}}+1 = \sum_{n=1}^{k} \frac{\lambda^n}{n!\mu^n} + \sum_{n=k+1}^{\infty} \left(\frac{\lambda}{k\mu}\right)^n +1 \end{equation}\]收敛。这意味着当且仅当 $\lambda\lt k\mu$ 时，系统才可能达到稳态。
因此，系统中刚好有 $k$ 个人的概率为：
\[\begin{equation} \pi_k= \frac{\frac{1}{k!}\left(\frac{\lambda}{\mu}\right)^k} { \sum_{n=0}^{k}\frac{1}{n!}\left(\frac{\lambda}{\mu}\right)^n + \left(\frac{\lambda}{k\mu}\right)^{k+1} \left(1-\frac{\lambda}{k\mu}\right) } \end{equation}\]这个概率称为呼损率，这是系统刚好满载的概率。
Appendix
Apd.1. 马尔可夫性两种表述的等价性证明
下面我们证明马尔可夫性两种表述 \eqref{eq:markov-1} 和 \eqref{eq:markov-2} 是等价的。
\eqref{eq:markov-1} $\implies$ \eqref{eq:markov-2}
考虑公式 \eqref{eq:markov-2} 的等式左侧：
\[\begin{equation} \begin{aligned} \text{LHS} &= P(X_{n+1},X_{\lt n}\mid X_n)\\ &= P(X_{n+1}\mid X_n,X_{\lt n}) P(X_{\lt n}\mid X_n)\\ &= P(X_{n+1}\mid X_n) P(X_{\lt n}\mid X_n)\\ &=\text{RHS} \end{aligned} \end{equation}\]\eqref{eq:markov-2} $\implies$ \eqref{eq:markov-1}
\[\begin{equation} \begin{aligned} \text{LHS} &= P(X_{n+1}\mid X_{n},X_{\lt n})\\ &= \frac{P(X_{n+1},X_{\lt n}\mid X_{n})}{P(X_{\lt n}\mid X_n)}\\ &= P(X_{n+1}\mid X_{n})\\ &=\text{RHS} \end{aligned} \end{equation}\]Apd.2. C-K 方程的证明
下面我们证明 Chapman-Kolmogorov 方程：
\[\begin{equation} P_{ij}(m+n) = \sum_{k\in S} P_{ik}(m) P_{kj}(n) \end{equation}\]根据马尔可夫性和平稳性假设，我们有：
\[\begin{equation} \begin{aligned} P_{ij}(m+n) &= P(X_{m+n}=j\mid X_0=i)\\ &= \sum_{k\in S} P(X_{m+n}=j,X_{m}=k\mid X_0=i)\\ &= \sum_{k\in S} P(X_{m+n}=j\mid X_{m}=k, X_0=i) P(X_{m}=k\mid X_0=i)\\ &= \sum_{k\in S} P(X_{m+n}=j\mid X_{m}=k) P(X_{m}=k\mid X_0=i)\\ &= \sum_{k\in S} P_{ik}(m) P_{kj}(n) \end{aligned} \end{equation}\]Apd.3. 不可约的等价性证明
下面我们证明不可约的两种定义的等价性，即：
- 状态集 $S$ 没有闭的真子集。
- 状态集 $S$ 中的任意两个状态都是相通的。
是等价的。
2 $\implies$ 1
这个证明比较简单。如果存在某个闭的真子集 $C\subseteq S$，那么 $\forall i\in C,j\notin C$，状态 $i$ 都不可达状态 $j$。这与相通性矛盾。
1 $\implies$ 2
任取 $i\in S$，定义 $A_i$ 为从 $i$ 出发的所有可达状态的集合集。只要证明 $A_i$ 是闭集，由于 $S$ 没有闭的真子集，所以 $A_i=S$ 也是闭集。由 $i$ 的任意性，就能证明 $S$ 中的任意两个状态都是相通的。
也就是说，任取 $j\in A_i,k\notin A_i$，我们希望证明 $j$ 不可达 $k$。
用反证法。如果 $j$ 可达 $k$，而 $i$ 可达 $j$，根据可达关系的传递性，$i$ 也可达 $k$。也就是说 $k\in A_i$，矛盾。
Apd.4. 首达概率和转移概率的关系
下面我们证明两个状态之间的首达概率和转移概率存在如下关系：
\[\begin{equation} P_{ij}(n)= \sum_{k=1}^n f_{ij}(k)P_{jj}(n-k) \end{equation}\]定义首达时间 $T_{ij}$ 为状态 $i$ 首次到达状态 $j$ 的时间：
\[\begin{equation} T_{ij}=k \iff X_k=j,j\notin X_{[1:k-1]}\mid X_0=i \end{equation}\]则转移概率为：
\[\begin{equation} \begin{aligned} P_{ij}(n) &= P(X_n=j\mid X_0=i)\\ &= \sum_{k=1}^{n} P(X_n=j,T_{ij}=k\mid X_0=i)\\ &= \sum_{k=1}^{n} P(X_n=j\mid T_{ij}=k, X_0=i) P(T_{ij}=k\mid X_0=i)\\ &= \sum_{k=1}^{n} P(X_n=j\mid X_k=j, j\notin X_{[1:k-1]}, X_0=i) P(X_k=j, j\notin X_{[1:k-1]}\mid X_0=i)\\ &= \sum_{k=1}^{n} P(X_n=j\mid X_k=j) P(X_k=j, j\notin X_{[1:k-1]}\mid X_0=i)\\ &= \sum_{k=1}^{n} P_{kj}(n-k) f_{ij}(k) \end{aligned} \end{equation}\]得证。
Apd.5. 相通状态有同样的周期
下面我们证明如果两个状态 $i$ 和 $j$ 是相通的，那么 $d_i=d_j$。
由于 $i$ 和 $j$ 是相通的，因此存在 $m,n\in\mathbb{N}$，使得 $P_{ij}(m)\gt 0$ 且 $P_{ji}(n)\gt 0$。
定义 $A_i=\lbrace k\geq 1\mid P_{ii}(k)\gt 0 \rbrace$，则：
\[\begin{equation} P_{ii}(m+n)\geq P_{ij}(m)P_{ji}(n)\gt 0 \end{equation}\]因此有 $m+n\in A_i$，即 $d_i\mid m+n$。
任取 $k\in A_j$，这说明 $P_{jj}(k)\gt 0$。因此：
\[\begin{equation} P_{ii}(m+n+k)\geq P_{ij}(m)P_{jj}(k)P_{ji}(n)\gt 0 \end{equation}\]因此有 $m+n+k\in A_i$，即 $d_i\mid m+n+k$。
由上面两个结论，我们有 $d_i\mid (m+n+k)-(m+n)$，即 $d_i\mid k$。
由 $k$ 的任意性，说明 $d_i$ 是 $A_j$ 的公因子。由于公因子一定整除最大公因子，因此 $d_i\mid d_j$。
同理，重复上面的过程，我们也有 $d_j\mid d_i$。
因此，$d_i=d_j$ 得证。
Apd.6. 矩阵方程非零解的存在性
下面我们证明，只要 $P$ 是一个转移概率矩阵，那么矩阵方程
\[\begin{equation} \pi=\pi P \end{equation}\]一定有非零解。
为了逻辑通顺，我们将逻辑链条倒过来：
\[\begin{equation} \begin{aligned} &\pi=\pi P \iff \pi^T=P^T\pi^T \iff (P^T-I)\pi^T=0\\ &\iff \det(P^T-I)=0 \iff \det(P-I)=0 \impliedby (P-I)\cdot\bm{1}=0 \end{aligned} \end{equation}\]即只需要 $P$ 行和为1，则矩阵方程一定有非零解。
Apd.7. 矩阵方程的解与平稳分布
下面我们来证明，分布 $\pi$ 是一个平稳分布当且仅当 $\pi$ 是矩阵方程 $\pi=\pi P$ 的解。
充分性（平稳分布一定满足矩阵方程）
根据平稳分布的定义，
\[\begin{equation} \begin{aligned} \pi_i &=P(X_1=i)\\ &=\sum_{k}P(X_1=i\mid X_0=k)P(X_0=k)\\ &= \sum_{k}\pi_k\cdot P_{ki} \end{aligned} \end{equation}\]因此，$\pi$ 是矩阵方程 $\pi=\pi P$ 的解。
必要性（矩阵方程的解一定是一个平稳分布）
由于 $\pi=\pi P$，我们有
\[\begin{equation} \begin{aligned} \pi_i &=P(X_2=i)\\ &= \sum_{k}\pi_k\cdot P_{ki}\\ &=\sum_{k}P(X_2=i\mid X_1=k)P(X_1=k) \end{aligned} \end{equation}\]因此，$\pi$ 是一个平稳分布。
