马尔可夫链是最重要的一类随机过程，具有“无后效性”（Markov性）：给定现在，未来与过去独立。这一性质大大简化了分析，使马尔可夫链成为随机建模的核心工具。

典型应用：

• 随机游动与赌博问题
• 排队系统建模
• 生物群体遗传
• 网页排序算法（PageRank）
• 语音识别与自然语言处理
• 金融衍生品定价

定义4.1（马尔可夫链） 随机序列 $\{X_n, n = 0, 1, 2, \ldots\}$ 称为离散时间马尔可夫链（Discrete-Time Markov Chain, DTMC），如果满足：

• 状态空间 $S$ 是有限或可列集
• Markov性：对任意 $n \geq 0$ 和任意状态 $i_0, i_1, \ldots, i_n, j \in S$，有：

$$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})$ 称为转移概率矩阵或随机矩阵，满足：

• $p_{ij} \geq 0$ 对所有 $i, j \in S$
• $\sum_{j \in S} p_{ij} = 1$ 对所有 $i \in S$

例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 互通关系是等价关系：

• 自反性：$i \leftrightarrow i$
• 对称性：若 $i \leftrightarrow j$，则 $j \leftrightarrow i$
• 传递性：若 $i \leftrightarrow j$ 且 $j \leftrightarrow k$，则 $i \leftrightarrow k$

互通关系将状态空间划分为等价类。

定义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$ 称为：

• 常返（Recurrent）：若 $f_{ii} = 1$（最终必定返回）
• 非常返（Transient）：若 $f_{ii} < 1$（以正概率永不返回）

定理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）的，如果它是：

• 非周期的（$d(i) = 1$）
• 正常返的（$\mu_i = E[T_i | X_0 = i] < \infty$）

定理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$ 当且仅当链是常返的。

上一章：第三章_更新过程 | 下一章：第五章_状态的分类与极限分布