4. 离散时间马尔可夫过程

# 马尔可夫链的定义

# 基本概念

• 马尔可夫过程（马尔可夫链）：一个随机过程 $\{X(t), t \in T\}$，若其未来的状态只依赖于当前状态，而与过去的状态无关，则称其为马尔可夫过程。数学上，对于任意 $t_1 < t_2 < \cdots < t_n \in T$，该过程满足：

  $$\left( X(t_1), X(t_2), \cdots, X(t_n) \right) \perp X(t_{n+1}) \mid X(t_n)$$

  对于离散时间过程 $\{X_n, n \in \mathbb{N}\}$，该性质等价于：

  $$P\{X_{n+1} = x_{n+1} \mid X_n = x_n, \cdots, X_0 = x_0\} = P\{X_{n+1} = x_{n+1} \mid X_n = x_n\}$$

• 状态：马尔可夫链在某个时刻所处的值，记为 $j \in S$，其中 $S$ 为状态空间。

• 状态驻留概率：马尔可夫链 $\{X_n\}$ 在时刻 $n$ 处于状态 $j \in S$ 的概率。

  $$\pi_j^{(n)} = P\{X_n = j\}$$

  向量 $\mathbf{\pi}^{(n)} = \{ \pi_j^{(n)} \}_{j \in S}$ 称为状态分布，其中 $\mathbf{\pi}^{(0)}$ 是初始状态分布。

• 状态转移概率：马尔可夫链从状态 $i \in S$ 转移到状态 $j \in S$ 的概率。

  • 一步转移概率：从时刻 $k$ 转移到时刻 $k+1$ 的概率，记为 $P(X_{k+1} = j \mid X_k = i) = p_{ij}(k, k+1)$。
  • $n$ 步转移概率：从时刻 $k$ 转移到时刻 $k+n$ 的概率，记为 $P(X_{k+n} = j \mid X_k = i) = p_{ij}(k, k+n)$。

# 齐次马尔可夫链

• 齐次马尔可夫链：如果一步转移概率 $p_{ij}(k, k+1)$ 与时刻 $k$ 无关，即 $p_{ij}(k, k+1) = p_{ij}$，则称该马尔可夫链是齐次的。此时，$n$ 步转移概率也与 $k$ 无关，记为 $p_{ij}^{(n)}$。

• 转移概率矩阵：对于齐次马尔可夫链，一步转移概率矩阵 $\mathbf{P} = \{ p_{ij} \}_{i, j \in S}$ 是一个以 $i$ 为行、以 $j$ 为列的矩阵，其每一行元素之和为 1。$n$ 步转移概率矩阵为 $\mathbf{P}^{(n)} = \{ p_{ij}^{(n)} \}_{i, j \in S}$，每一行元素之和也为 1，且 $\mathbf{P}^{(1)} = \mathbf{P}$。

• 状态分布与转移矩阵的关系：状态分布 $\mathbf{\pi}^{(n)}$ 可由初始分布 $\mathbf{\pi}^{(0)}$ 和 $n$ 步转移概率矩阵 $\mathbf{P}^{(n)}$ 得到：

  $$\mathbf{\pi}^{(n)} = \mathbf{\pi}^{(0)} \mathbf{P}^{(n)}$$

• 查普曼-科尔莫戈洛夫（C-K）方程：该方程描述了多步转移概率之间的关系，其数学形式为：

  $$p_{ij}^{(n)} = \sum_{k \in S} p_{ik}^{(m)} p_{kj}^{(n-m)}, \quad \forall n \ge m \ge 1$$

  该方程的矩阵形式为 $\mathbf{P}^{(n)} = \mathbf{P}^{(m)} \mathbf{P}^{(n-m)}$，由此可得 $\mathbf{P}^{(n)} = \mathbf{P}^n$。其中规定 $p_{ij}^{(0)} = \delta_{ij}$，即 $\mathbf{P}^{(0)} = \mathbf{I}$。

  • C-K 不等式：$p_{ij}^{(n)} \ge P_{ik}^{(m)} p_{kj}^{(n-m)}, \forall k \in S$。

• 状态转移图：一种直观表示马尔可夫链状态转移的图。

# 马尔可夫链状态的分类

# 可达性与互通性

• 可达性：对于状态 $i, j \in S$，若存在 $n \ge 1$ 使得 $p_{ij}^{(n)} > 0$，则称状态 $i$ 可达于状态 $j$，记为 $i \rightarrow j$。

  • 性质：可达性具有传递性。若 $i \nrightarrow j$，则对于任意 $n \ge 1$，有 $p_{ij}^{(n)} = 0$。

• 互通性：若 $i \rightarrow j$ 且 $j \rightarrow i$，则称状态 $i$ 与状态 $j$ 互通，记为 $i \leftrightarrow j$。

  • 性质：互通性是一种等价关系，具有自反性、对称性和传递性。
  • 等价类：互通关系将状态空间 $S$ 划分为若干个互不相交的等价类。包含状态 $i$ 的等价类记为 $C(i) = \{ j \in S \mid i \leftrightarrow j \}$。

# 闭集与不可约集

• 闭集：若状态空间的子集 $B \subseteq S$ 满足马尔可夫链不能从 $B$ 中的任何状态转移到 $S \setminus B$ 中的任何状态，则称 $B$ 为闭集。

  • 性质：
    • 闭集可以单独构成一个马尔可夫链的状态空间。
    • 吸收态是只有一个状态的闭集，满足 $P_{ii} = 1$，是最小的闭集。
    • 整个状态空间 $S$ 是最大的闭集。
    • 闭集与等价类之间没有互相蕴含的关系。

• 不可约集：一个闭的等价类。如果马尔可夫链的状态空间 $S$ 本身是一个不可约集，则称该链为不可约链。

# 马尔可夫链状态的常返性

# 常返与非常返

• 首达概率：从状态 $i$ 出发，经过 $n$ 步首次到达状态 $j$ 的概率记为 $f_{ij}^{(n)}$。

  • 从状态 $i$ 出发，至少一次到达状态 $j$ 的概率为可达概率 $f_{ij} = \sum_{n=1}^{+\infty} f_{ij}^{(n)}$。
  • 当 $i=j$ 时，$f_{ii}$ 称为返回概率。

• 常返与非常返：

  • 常返态：若状态 $i$ 的返回概率 $f_{ii} = 1$，则称状态 $i$ 为常返态。
  • 非常返态（暂态）：若状态 $i$ 的返回概率 $f_{ii} < 1$，则称状态 $i$ 为非常返态。

• 常返性判别：

  • 状态 $i$ 是常返的，当且仅当 $\sum_{n=0}^{+\infty} P_{ii}^{(n)} = +\infty$。
  • 状态 $i$ 是非常返的，当且仅当 $\sum_{n=0}^{+\infty} P_{ii}^{(n)} = 1/(1 - f_{ii}) < +\infty$。

• 常返性性质：

  • 有限状态空间的马尔可夫链至少有一个常返态。
  • 常返性是类性质，即若 $i \leftrightarrow j$，则 $i$ 与 $j$ 具有相同的常返性。
  • 若 $i$ 为常返态且 $i \rightarrow j$，则必有 $j \rightarrow i$，且 $f_{ij} = 1$。
  • 吸收态是常返态。
  • 若 $j$ 是非常返态，则对于任意 $i \in S$，有 $\lim_{n \to +\infty} P_{ij}^{(n)} = 0$。

---

# 正常返与零常返

• 首达时间：对于状态 $j \in S$，从 $j$ 出发，首次返回到 $j$ 的时间 $\tau_j = \min\{ n \mid X_n = j, n \ge 1 \}$。若 $j$ 是常返态，则 $\{ f_{jj}^{(n)} \}$ 是 $\tau_j$ 的分布列。

• 平均返回时间：常返态 $j$ 的平均返回时间为 $\mu_j = E\left\{ \tau_j \mid X_0 = j \right\} = \sum_{n=1}^{+\infty} n f_{jj}^{(n)}$。

• 正常返与零常返：

  • 正常返态：若常返态 $j$ 的平均返回时间 $\mu_j < +\infty$。
  • 零常返态：若常返态 $j$ 的平均返回时间 $\mu_j = +\infty$。

• 性质：

  • 若 $j$ 是常返态，则 $j$ 为零常返当且仅当 $\lim_{n \to +\infty} P_{jj}^{(n)} = 0$。
  • 正常返和零常返也是类性质。

• 弱遍历性定理：对于齐次马尔可夫链，从状态 $i$ 出发，长期来看访问状态 $j$ 的平均频率的极限为：

  $$\lim_{n \to +\infty} \frac{1}{n} \sum_{k=0}^{n-1} P_{ij}^{(k)} = \frac{f_{ij}}{\mu_j} = \begin{cases} 0 & \text{若 $j$ 为零常返态或非常返态} \\ \frac{f_{ij}}{\mu_j} & \text{若 $j$ 为正常返态} \end{cases}$$

  特别是当 $i=j$ 时，该极限为 $1/\mu_j$，表示从 $i$ 出发，链访问状态 $i$ 的频率的期望的极限，等于首次返回状态 $i$ 的平均时间的倒数。

• 有限状态的马尔可夫链：至少有一个正常返态。

---

# 马尔可夫链的极限行为

# 周期性

• 状态的周期：对于状态 $i \in S$，其周期 $d_i$ 定义为集合 $\{ n \mid P_{ii}^{(n)} > 0 \}$ 的最大公约数，$d_i = \gcd\{ n \mid P_{ii}^{(n)} > 0 \}$。若状态 $i$ 永远无法返回自身，则定义 $d_i = +\infty$。
  • 非周期态：若 $d_i = 1$，则称状态 $i$ 为非周期态。
  • 性质：周期性也是类性质，即若 $i \leftrightarrow j$，则 $d_i = d_j$。

# 转移概率的极限

• 非常返态：对非常返态 $j$，对于任意 $i \in S$，都有 $\lim_{n \to +\infty} P_{ij}^{(n)} = 0$。

• 常返、非周期态：对常返、非周期态 $j$，对于任意 $i \in S$，有：

  $$\lim_{n \to +\infty} P_{ij}^{(n)} = \frac{f_{ij}}{\mu_j} = \begin{cases} 0 & \text{若 $j$ 为零常返} \\ \frac{f_{ij}}{\mu_j} & \text{若 $j$ 为正常返} \end{cases}$$

• 常返、周期态：对周期为 $d$ 的常返态 $j$，对于任意 $i \in S$，转移概率的极限在周期子序列上存在。设 $r_{ij} = \min\{ n \mid P_{ij}^{(n)} > 0 \}$，则：

  $$\lim_{n \to +\infty} P_{ij}^{(nd + r_{ij})} = \frac{d f_{ij}}{\mu_j} = \begin{cases} 0 & \text{若 $j$ 为零常返} \\ \frac{d f_{ij}}{\mu_j} & \text{若 $j$ 为正常返} \end{cases}$$

# 状态空间的分解

• 状态空间的分解：任何马尔可夫链的状态空间 $S$ 都可以分解为若干常返等价类（闭集）和一个非常返状态集合 $F$ 的并集：

  $$S = (\cup_{i=1}^{m} C_i) \cup F, \quad m \le +\infty$$

  其中 $C_i$ 为常返等价类，$F$ 为非常返状态集合。

• 转移矩阵的块矩阵形式：根据状态空间的分解，转移矩阵 $\mathbf{P}$ 可以写成块矩阵形式：

  $$\mathbf{P} = \begin{bmatrix} \mathbf{P}_1 & \mathbf{O} & \cdots & \mathbf{O} & \mathbf{O} \\ \mathbf{O} & \mathbf{P}_2 & \cdots & \mathbf{O} & \mathbf{O} \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ \mathbf{O} & \mathbf{O} & \cdots & \mathbf{P}_m & \mathbf{O} \\ \mathbf{R}_1 & \mathbf{R}_2 & \cdots & \mathbf{R}_m & \mathbf{Q} \end{bmatrix}$$

  当 $n \to +\infty$ 时，非常返状态的转移概率极限为零，因此转移矩阵的极限为：

  $$\mathbf{P}^{(n)} \to \begin{bmatrix} \mathbf{P}_1^{(\infty)} & \cdots & \mathbf{O} & \cdots & \mathbf{O} \\ \vdots & \ddots & \vdots & \ddots & \vdots \\ \mathbf{O} & \cdots & \mathbf{P}_k^{(\infty)} & \cdots & \mathbf{O} \\ \vdots & \ddots & \vdots & \ddots & \vdots \\ \mathbf{R}_1^{(\infty)} & \cdots & \mathbf{R}_k^{(\infty)} & \cdots & \mathbf{0} \end{bmatrix}$$

  其中 $\mathbf{P}_i^{(\infty)}$ 是对应正常返等价类的极限，$\mathbf{0}$ 是零矩阵。

---

# 平稳分布

# 定义与性质

• 平稳分布：对于齐次马尔可夫链，若存在一个概率分布 $\mathbf{\pi}$ 满足 $\mathbf{\pi} = \mathbf{\pi} \mathbf{P}$，则称 $\mathbf{\pi}$ 为该链的平稳分布。

  • 性质：
    • 若 $\mathbf{\pi}$ 是平稳分布，则 $\mathbf{\pi} = \mathbf{\pi} \mathbf{P}^n, \quad \forall n \ge 1$。
    • 如果马尔可夫链的初始分布就是平稳分布，则该链是严平稳的。
    • 平稳分布的存在性与极限分布的存在性是两个不同的概念。

• 遍历态：一个正常返且非周期的状态。若一个等价类中有一个遍历态，则所有状态都是遍历态，该等价类称为遍历等价类。

• 不可约遍历链的平稳分布：对于不可约的遍历链，其转移概率的极限与出发状态无关，即 $\lim_{n \to +\infty} P_{ij}^{(n)} = 1/\mu_j$。这个极限分布 $\mathbf{\pi} = \{ \pi_j = 1/\mu_j; j \in S \}$ 构成了该链唯一的平稳分布。

• 平稳分布的存在性：

  • 一个马尔可夫链存在且唯一的平稳分布，当且仅当它只包含一个正常返等价类。
  • 一个不可约马尔可夫链是正常返的充要条件是存在平稳分布。

# 细致平衡方程与可逆链

• 反向马尔可夫链：若齐次马尔可夫链 $\{X_n; n \ge 0\}$ 存在平稳分布 $\mathbf{\pi} > 0$，且初始分布为 $\mathbf{\pi}$，则其反向马尔可夫链也是齐次的，其一步转移概率为 $P(X_{n-1}=j \mid X_n=i) = (\pi_j / \pi_i) P_{ji}$。

• 细致平衡方程（细致平稳方程）：若定义在马尔可夫状态空间 $S$ 上的分布 $\mathbf{\pi}$ 满足：

  $$\pi_i P_{ij} = \pi_j P_{ji}, \quad \forall i,j \in S$$

  则称 $\mathbf{\pi}$ 满足细致平衡方程，该马尔可夫链称为可逆马尔可夫链。

  • 细致平衡方程是平稳分布的一个充分条件。

# 应用：马尔可夫链蒙特卡洛（MCMC）

• MCMC：通过构造一个具有目标平稳分布的马尔可夫链，来生成服从该分布的随机样本的方法。
• MH 算法：一种构造马尔可夫链以达到指定平稳分布的常用 MCMC 算法。

---

# 辅助定理

• 哈代-利特尔伍德定理：用于分析幂级数的极限性质。
  • 对于幂级数 $A(z) = \sum_{n=0}^{+\infty} a_n z^n$（在 $0 \le z < 1$ 收敛），有：

    $$\lim_{n \to +\infty} \frac{1}{n} \sum_{k=0}^{n-1} a_k = \lim_{z \to 1^-} (1 - z) A(z)$$

• 控制收敛定理：用于判断函数项级数的一致收敛性。
  • 若存在收敛的数项级数 $\sum_{k=1}^{+\infty} c_k$ 满足 $|f_k(x)| \le c_k$，则函数项级数 $\sum_{k=1}^{+\infty} f_k(x)$ 在指定区间上一致收敛。
• 非常返判据：对于一个不可约的齐次马尔可夫链，它非常返的充要条件是方程 $\mathbf{y} = \mathbf{P}_0 \mathbf{y}$ 具有非零的有界解，其中 $\mathbf{P}_0$ 是去掉某个状态（如0状态）对应行和列的转移矩阵。