张叶安的小站

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。
====== 第四章 离散时间马尔可夫链 ======

===== 4.1 引言 =====

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

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

===== 4.2 马尔可夫链的定义 =====

**定义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.3 转移概率 =====

==== 4.3.1 一步转移概率 ====

**定义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.2 转移概率矩阵 ====

**定义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.3.3 $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.4 Chapman-Kolmogorov方程 =====

**定理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 状态的分布与演化 =====

==== 4.5.1 初始分布 ====

**定义4.5（初始分布）** 设 $\pi_i^{(0)} = P(X_0 = i)$，则向量 $\boldsymbol{\pi}^{(0)} = (\pi_i^{(0)})$ 称为**初始分布**。

==== 4.5.2 绝对分布 ====

**定理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 状态的分类 =====

==== 4.6.1 可达与互通 ====

**定义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.6.2 等价类与不可约性 ====

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

**定义4.8（不可约）** 若马尔可夫链只有一个等价类（即所有状态互通），则称其为**不可约**（Irreducible）的。

==== 4.6.3 周期性 ====

**定义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.6.4 常返与非常返 ====

**定义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.7 遍历性与极限分布 =====

==== 4.7.1 遍历性定义 ====

**定义4.13（遍历状态）** 状态 $i$ 称为**遍历**（Ergodic）的，如果它是：
  * 非周期的（$d(i) = 1$）
  * 正常返的（$\mu_i = E[T_i | X_0 = i] < \infty$）

==== 4.7.2 极限分布 ====

**定理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.8 平稳分布 =====

**定义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}$。

===== 4.9 吸收概率与期望时间 =====

==== 4.9.1 吸收概率 ====

设状态 $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$

==== 4.9.2 期望吸收时间 ====

设 $v_i$ 为从状态 $i$ 出发被吸收前的期望时间。

**定理4.12** 
$$v_a = 0, \quad v_i = 1 + \sum_{j} p_{ij} v_j \text{（对非吸收态 } i\text{）}$$

===== 4.10 本章例题详解 =====

**例题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.11 本章习题 =====

**习题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$ 当且仅当链是常返的。

----

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