马尔可夫链是最重要的一类随机过程，具有“无后效性”（Markov性）：给定现在，未来与过去独立。这一性质大大简化了分析，使马尔可夫链成为随机建模的核心工具。
典型应用：
定义4.1（马尔可夫链） 随机序列 $\{X_n, n = 0, 1, 2, \ldots\}$ 称为离散时间马尔可夫链（Discrete-Time Markov Chain, DTMC），如果满足：
$$P(X_{n+1} = j | X_0 = i_0, X_1 = i_1, \ldots, X_n = i) = P(X_{n+1} = j | X_n = i)$$
Markov性表明：在给定当前状态的条件下，未来状态的条件分布只依赖于当前状态，而与过去的历史无关。
定义4.2（一步转移概率） 称 $$p_{ij} = P(X_{n+1} = j | X_n = i), \quad i, j \in S$$ 为从状态 $i$ 到状态 $j$ 的一步转移概率。
如果 $p_{ij}$ 不依赖于 $n$，则称马尔可夫链是时齐的（Homogeneous）。我们主要研究时齐马尔可夫链。
定义4.3（转移概率矩阵） 矩阵 $\mathbf{P} = (p_{ij})$ 称为转移概率矩阵或随机矩阵，满足：
例4.1（随机游动） 考虑整数上的简单随机游动： $$p_{i,i+1} = p, \quad p_{i,i-1} = q = 1-p, \quad i \in \mathbb{Z}$$
转移概率矩阵是无限维的，主对角线上下元素分别为 $q$ 和 $p$。
例4.2（Ehrenfest模型） 两个容器共有 $N$ 个分子，每次随机选取一个分子移动到另一个容器。设 $X_n$ 为时刻 $n$ 容器A中的分子数，则： $$p_{i,i+1} = \frac{N-i}{N}, \quad p_{i,i-1} = \frac{i}{N}, \quad i = 0, 1, \ldots, N$$
定义4.4（$n$步转移概率） $$p_{ij}^{(n)} = P(X_n = j | X_0 = i)$$ 特别地，$p_{ij}^{(0)} = \delta_{ij}$（Kronecker delta），$p_{ij}^{(1)} = p_{ij}$。
定理4.1（Chapman-Kolmogorov方程） 对任意 $m, n \geq 0$ 和任意 $i, j \in S$： $$p_{ij}^{(m+n)} = \sum_{k \in S} p_{ik}^{(m)} p_{kj}^{(n)}$$
矩阵形式：$\mathbf{P}^{(m+n)} = \mathbf{P}^{(m)} \mathbf{P}^{(n)}$，特别地，$\mathbf{P}^{(n)} = \mathbf{P}^n$。
证明：
$$\begin{aligned}
p_{ij}^{(m+n)} &= P(X_{m+n} = j | X_0 = i)
&= \sum_{k \in S} P(X_{m+n} = j, X_m = k | X_0 = i)
&= \sum_{k \in S} P(X_m = k | X_0 = i) P(X_{m+n} = j | X_m = k, X_0 = i)
&= \sum_{k \in S} p_{ik}^{(m)} p_{kj}^{(n)}
\end{aligned}$$
定义4.5（初始分布） 设 $\pi_i^{(0)} = P(X_0 = i)$，则向量 $\boldsymbol{\pi}^{(0)} = (\pi_i^{(0)})$ 称为初始分布。
定理4.2 $n$ 时刻的绝对分布为： $$\pi_j^{(n)} = P(X_n = j) = \sum_{i \in S} \pi_i^{(0)} p_{ij}^{(n)}$$
向量形式：$\boldsymbol{\pi}^{(n)} = \boldsymbol{\pi}^{(0)} \mathbf{P}^n$。
例4.3 设转移矩阵 $\mathbf{P} = \begin{pmatrix} 0.7 & 0.3
0.4 & 0.6 \end{pmatrix}$，初始分布 $\boldsymbol{\pi}^{(0)} = (0.5, 0.5)$。
计算：
$$\mathbf{P}^2 = \begin{pmatrix} 0.61 & 0.39
0.52 & 0.48 \end{pmatrix}$$
$$\boldsymbol{\pi}^{(2)} = (0.5, 0.5) \mathbf{P}^2 = (0.565, 0.435)$$
定义4.6（可达） 若存在 $n \geq 0$ 使得 $p_{ij}^{(n)} > 0$，则称状态 $j$ 可达（Accessible）于状态 $i$，记为 $i \to j$。
定义4.7（互通） 若 $i \to j$ 且 $j \to i$，则称状态 $i$ 和 $j$ 互通（Communicate），记为 $i \leftrightarrow j$。
定理4.3 互通关系是等价关系：
互通关系将状态空间划分为等价类。
定义4.8（不可约） 若马尔可夫链只有一个等价类（即所有状态互通），则称其为不可约（Irreducible）的。
定义4.9（周期） 状态 $i$ 的周期定义为： $$d(i) = \gcd\{n \geq 1: p_{ii}^{(n)} > 0\}$$ 若 $d(i) = 1$，称状态 $i$ 是非周期（Aperiodic）的。
定理4.4 若 $i \leftrightarrow j$，则 $d(i) = d(j)$。即周期是类性质。
例4.4 简单随机游动：从任意状态出发，奇数步不能回到自身，故 $d(i) = 2$（周期性）。
定义4.10（首达时） 从状态 $i$ 出发首次到达状态 $j$ 的时间： $$T_j = \inf\{n \geq 1: X_n = j\}$$ （若集合为空，定义 $T_j = \infty$）
定义4.11（首达概率） $$f_{ij}^{(n)} = P(T_j = n | X_0 = i) = P(X_n = j, X_k \neq j, 1 \leq k < n | X_0 = i)$$ $$f_{ij} = \sum_{n=1}^{\infty} f_{ij}^{(n)} = P(T_j < \infty | X_0 = i)$$
定义4.12（常返/非常返） 状态 $i$ 称为：
定理4.5 状态 $i$ 常返当且仅当 $\sum_{n=1}^{\infty} p_{ii}^{(n)} = \infty$。
状态 $i$ 非常返当且仅当 $\sum_{n=1}^{\infty} p_{ii}^{(n)} < \infty$。
定理4.6 常返性是类性质。
证明：设 $i \leftrightarrow j$，则存在 $m, n$ 使得 $p_{ij}^{(m)} > 0$，$p_{ji}^{(n)} > 0$。于是： $$p_{jj}^{(m+k+n)} \geq p_{ji}^{(n)} p_{ii}^{(k)} p_{ij}^{(m)}$$ 若 $i$ 常返，$\sum_k p_{ii}^{(k)} = \infty$，则 $\sum_k p_{jj}^{(k)} = \infty$，故 $j$ 常返。
定义4.13（遍历状态） 状态 $i$ 称为遍历（Ergodic）的，如果它是：
定理4.7（极限定理） 设状态 $j$ 是遍历的，则： $$\lim_{n \to \infty} p_{ij}^{(n)} = \frac{1}{\mu_j} > 0$$ 其中 $\mu_j$ 是从 $j$ 出发返回 $j$ 的期望时间。
若状态 $j$ 是非常返的或零常返的，则 $\lim_{n \to \infty} p_{ij}^{(n)} = 0$。
定理4.8 对于有限状态的不可约遍历马尔可夫链，极限 $\lim_{n \to \infty} p_{ij}^{(n)} = \pi_j$ 存在且与初始状态 $i$ 无关。
定义4.14（平稳分布） 概率分布 $\boldsymbol{\pi} = (\pi_j)$ 称为平稳分布（Stationary Distribution），如果满足： $$\boldsymbol{\pi} = \boldsymbol{\pi} \mathbf{P}$$ 即 $\pi_j = \sum_{i \in S} \pi_i p_{ij}$ 对所有 $j \in S$。
定理4.9 若初始分布是平稳分布，则过程是严平稳的。
定理4.10 对于不可约遍历马尔可夫链，平稳分布存在、唯一，且： $$\pi_j = \frac{1}{\mu_j} = \lim_{n \to \infty} p_{ij}^{(n)}$$
例4.5（两状态链） $\mathbf{P} = \begin{pmatrix} 1-p & p
q & 1-q \end{pmatrix}$
求解 $\boldsymbol{\pi} = \boldsymbol{\pi}\mathbf{P}$： $$\pi_0 = (1-p)\pi_0 + q\pi_1$$ $$\pi_1 = p\pi_0 + (1-q)\pi_1$$ $$\pi_0 + \pi_1 = 1$$
解得：$\pi_0 = \frac{q}{p+q}$，$\pi_1 = \frac{p}{p+q}$。
设状态 $a$ 是吸收态（$p_{aa} = 1$），定义从状态 $i$ 出发最终被 $a$ 吸收的概率为 $u_i$。
定理4.11 $\{u_i\}$ 满足方程组： $$u_a = 1, \quad u_i = \sum_{j} p_{ij} u_j \text{（对非吸收态 } i\text{）}$$
例4.6（赌徒输光问题） 赌徒初始有 $i$ 元，每次以概率 $p$ 赢1元，以概率 $q = 1-p$ 输1元，直到输光或达到 $N$ 元。求输光概率。
设 $u_i$ 为从 $i$ 元出发输光的概率，则： $$u_0 = 1, \quad u_N = 0$$ $$u_i = p u_{i+1} + q u_{i-1}, \quad i = 1, \ldots, N-1$$
解：特征方程 $r = pr^2 + q$，即 $pr^2 - r + q = 0$，根为 $r = 1$ 和 $r = q/p$。
若 $p \neq q$：$u_i = A + B(q/p)^i$
利用边界条件：$u_i = \frac{(q/p)^i - (q/p)^N}{1 - (q/p)^N}$
若 $p = q = 1/2$：$u_i = 1 - i/N$
设 $v_i$ 为从状态 $i$ 出发被吸收前的期望时间。
定理4.12 $$v_a = 0, \quad v_i = 1 + \sum_{j} p_{ij} v_j \text{（对非吸收态 } i\text{）}$$
例题1 证明：若状态 $i$ 常返且 $i \to j$，则 $j \to i$ 且 $j$ 常返。
证明：设 $i \to j$，则存在 $n$ 使得 $p_{ij}^{(n)} > 0$。由于 $i$ 常返，必以概率1返回 $i$ 无穷多次。每次返回 $i$ 后，都有正概率 $p_{ij}^{(n)}$ 在 $n$ 步内到达 $j$。由Borel-Cantelli引理，几乎必然某次成功，故 $j$ 可达。互通性保证 $j$ 常返。
例题2 设转移矩阵：
$$\mathbf{P} = \begin{pmatrix} 0 & 1/2 & 1/2
1/2 & 0 & 1/2
1/2 & 1/2 & 0 \end{pmatrix}$$
(1) 判断不可约性和周期性 (2) 求平稳分布 (3) 求 $\lim_{n \to \infty} \mathbf{P}^n$
解：
(1) 所有状态互通，不可约。$p_{ii}^{(2)} = 1/2 > 0$，$p_{ii}^{(3)} > 0$，故 $d(i) = 1$，非周期。
(2) 由对称性，$\pi = (1/3, 1/3, 1/3)$。
(3) 遍历链，$\lim_{n \to \infty} \mathbf{P}^n = \begin{pmatrix} 1/3 & 1/3 & 1/3
1/3 & 1/3 & 1/3
1/3 & 1/3 & 1/3 \end{pmatrix}$。
习题4.1 设 $\mathbf{P} = \begin{pmatrix} 0.5 & 0.5
0.3 & 0.7 \end{pmatrix}$，$\boldsymbol{\pi}^{(0)} = (0.6, 0.4)$。
(1) 求 $\boldsymbol{\pi}^{(1)}$，$\boldsymbol{\pi}^{(2)}$ (2) 求平稳分布 (3) 求 $\lim_{n \to \infty} \boldsymbol{\pi}^{(n)}$
习题4.2 证明：若状态 $i$ 的周期为 $d$，则存在 $N$ 使得对所有 $n \geq N$，$p_{ii}^{(nd)} > 0$。
习题4.3 设状态空间 $S = \{0, 1, 2, 3\}$，转移矩阵：
$$\mathbf{P} = \begin{pmatrix} 1 & 0 & 0 & 0
0 & 1 & 0 & 0
0.2 & 0 & 0.5 & 0.3
0 & 0.4 & 0.2 & 0.4 \end{pmatrix}$$
(1) 识别常返类和非常返类 (2) 求从状态2出发最终被状态0吸收的概率 (3) 求从状态3出发的期望吸收时间
习题4.4 设 $\{X_n\}$ 是简单随机游动，$p$ 为右移概率。证明：
(1) 当 $p \neq 1/2$ 时，所有状态非常返 (2) 当 $p = 1/2$ 时，所有状态零常返
习题4.5 设 $\mathbf{P}$ 是双随机矩阵（每行每列和都为1），状态空间有限。证明均匀分布是平稳分布。
习题4.6 设天气模型：若今天晴，则明天晴的概率为0.7；若今天雨，则明天晴的概率为0.4。
(1) 写出转移矩阵 (2) 求长期晴天比例 (3) 若今天晴，求三天后晴的概率
习题4.7 证明：有限状态的马尔可夫链至少有一个常返态。
习题4.8 设 $\mathbf{P}$ 是不可约马尔可夫链的转移矩阵，证明：对所有 $i, j$，$\sum_{n=0}^{\infty} p_{ij}^{(n)} = \infty$ 当且仅当链是常返的。
上一章：第三章_更新过程 | 下一章：第五章_状态的分类与极限分布