张叶安的小站

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

===== 6.1 引言 =====

连续时间马尔可夫链（Continuous-Time Markov Chain, CTMC）是离散时间马尔可夫链向连续时间的推广。与离散情形不同，状态转移可以在任意时刻发生，系统的演化由**停留时间**（Holding Time）和**转移概率**共同描述。

**典型应用**：
  * 排队系统（M/M/1, M/M/c等）
  * 可靠性分析
  * 生物种群动态
  * 化学反应网络
  * 计算机网络性能分析

===== 6.2 连续时间马尔可夫链的定义 =====

**定义6.1（连续时间马尔可夫链）** 随机过程 $\{X(t), t \geq 0\}$ 称为**连续时间马尔可夫链**，如果：

  * 状态空间 $S$ 是有限或可列集
  * **Markov性**：对任意 $t, s \geq 0$ 和任意状态 $i, j$：
$$P(X(t+s) = j | X(u), 0 \leq u \leq t) = P(X(t+s) = j | X(t) = i)$$

  * **时齐性**：转移概率 $p_{ij}(t) = P(X(t+s) = j | X(s) = i)$ 不依赖于 $s$

===== 6.3 转移速率与生成元 =====

==== 6.3.1 转移概率函数 ====

**定义6.2（转移概率函数）**
$$p_{ij}(t) = P(X(t) = j | X(0) = i), \quad i, j \in S, t \geq 0$$

转移概率矩阵 $\mathbf{P}(t) = (p_{ij}(t))$ 满足：
  * $p_{ij}(t) \geq 0$，$\sum_j p_{ij}(t) = 1$
  * $\mathbf{P}(0) = \mathbf{I}$
  * Chapman-Kolmogorov方程：$\mathbf{P}(s+t) = \mathbf{P}(s)\mathbf{P}(t)$

==== 6.3.2 转移速率 ====

**定义6.3（转移速率）**
$$q_{ij} = \lim_{h \to 0^+} \frac{p_{ij}(h) - \delta_{ij}}{h}, \quad i \neq j$$

$q_{ij}$ 表示从状态 $i$ 向状态 $j$ 转移的速率（$i \neq j$）。

**定理6.1** 若极限存在，则：
$$q_{ii} = \lim_{h \to 0^+} \frac{p_{ii}(h) - 1}{h} = -\sum_{j \neq i} q_{ij} = -q_i$$

其中 $q_i = -q_{ii} \geq 0$ 称为状态 $i$ 的**转出速率**。

==== 6.3.3 生成元（无穷小生成元）====

**定义6.4（生成元）** 矩阵 $\mathbf{Q} = (q_{ij})$ 称为连续时间马尔可夫链的**生成元**或**无穷小生成元**（Infinitesimal Generator），满足：
  * $q_{ij} \geq 0$ 对 $i \neq j$
  * $q_{ii} = -\sum_{j \neq i} q_{ij} \leq 0$
  * 每行和为0

===== 6.4 Kolmogorov方程 =====

==== 6.4.1 Kolmogorov向前方程 ====

**定理6.2（Kolmogorov向前方程）**
$$\frac{d}{dt}p_{ij}(t) = \sum_{k \neq j} p_{ik}(t)q_{kj} + p_{ij}(t)q_{jj} = \sum_k p_{ik}(t)q_{kj}$$

**矩阵形式**：
$$\mathbf{P}'(t) = \mathbf{P}(t)\mathbf{Q}$$

==== 6.4.2 Kolmogorov向后方程 ====

**定理6.3（Kolmogorov向后方程）**
$$\frac{d}{dt}p_{ij}(t) = \sum_{k \neq i} q_{ik}p_{kj}(t) + q_{ii}p_{ij}(t) = \sum_k q_{ik}p_{kj}(t)$$

**矩阵形式**：
$$\mathbf{P}'(t) = \mathbf{Q}\mathbf{P}(t)$$

==== 6.4.3 解的形式 ====

**定理6.4** Kolmogorov方程的解为：
$$\mathbf{P}(t) = e^{\mathbf{Q}t} = \sum_{n=0}^{\infty} \frac{(\mathbf{Q}t)^n}{n!}$$

对于有限状态空间，此级数收敛。

===== 6.5 停留时间与嵌入链 =====

==== 6.5.1 停留时间分布 ====

**定理6.5** 设链在时刻 $t$ 处于状态 $i$，则在该状态的**停留时间**（Holding Time）$H_i$ 服从参数为 $q_i = -q_{ii}$ 的指数分布：
$$P(H_i > s) = e^{-q_i s}, \quad s \geq 0$$

**证明思路**：由Markov性和时齐性，
$$P(H_i > s+t | H_i > s) = P(H_i > t)$$
即具有无记忆性，必为指数分布。

==== 6.5.2 嵌入马尔可夫链 ====

**定义6.5（嵌入链）** 设 $T_0 = 0 < T_1 < T_2 < \cdots$ 是转移时刻，定义 $Y_n = X(T_n)$ 为第 $n$ 次转移后的状态。则 $\{Y_n\}$ 是离散时间马尔可夫链，称为**嵌入链**（Embedded Chain）。

**定理6.6** 嵌入链的转移概率为：
$$r_{ij} = \frac{q_{ij}}{q_i}, \quad i \neq j, \quad q_i > 0$$
若 $q_i = 0$，则 $i$ 是吸收态（$r_{ii} = 1$）。

===== 6.6 生灭过程 =====

==== 6.6.1 定义 ====

**定义6.6（生灭过程）** 状态空间 $S = \{0, 1, 2, \ldots\}$ 的连续时间马尔可夫链称为**生灭过程**，如果转移只发生在相邻状态：
$$q_{i,i+1} = \lambda_i \text{（出生率）}, \quad q_{i,i-1} = \mu_i \text{（死亡率）} \text{（}i \geq 1\text{）}$$
$$q_{ii} = -(\lambda_i + \mu_i), \quad q_{01} = \lambda_0, \quad q_{00} = -\lambda_0$$

==== 6.6.2 数字特征 ====

**定理6.7** 生灭过程的转移概率满足：
$$p_{ij}'(t) = \lambda_{j-1}p_{i,j-1}(t) - (\lambda_j + \mu_j)p_{ij}(t) + \mu_{j+1}p_{i,j+1}(t)$$

==== 6.6.3 平稳分布 ====

**定理6.8** 生灭过程存在平稳分布 $\boldsymbol{\pi}$ 当且仅当：
$$\sum_{n=0}^{\infty} \frac{\lambda_0 \lambda_1 \cdots \lambda_{n-1}}{\mu_1 \mu_2 \cdots \mu_n} < \infty$$

此时：
$$\pi_0 = \left(1 + \sum_{n=1}^{\infty} \frac{\lambda_0 \cdots \lambda_{n-1}}{\mu_1 \cdots \mu_n}\right)^{-1}$$
$$\pi_n = \frac{\lambda_0 \cdots \lambda_{n-1}}{\mu_1 \cdots \mu_n} \pi_0, \quad n \geq 1$$

==== 6.6.4 M/M/1排队系统 ====

**例6.1（M/M/1队列）** 顾客按速率为 $\lambda$ 的泊松过程到达，服务时间服从 $Exp(\mu)$，单服务台。

这是生灭过程，$\lambda_n = \lambda$（$n \geq 0$），$\mu_n = \mu$（$n \geq 1$）。

**稳定性条件**：$\rho = \lambda/\mu < 1$（交通强度）

**平稳分布**：
$$\pi_n = (1-\rho)\rho^n, \quad n = 0, 1, 2, \ldots$$
几何分布！

**性能指标**：
  * 系统中平均顾客数：$L = \frac{\rho}{1-\rho}$
  * 队列中平均等待顾客数：$L_q = \frac{\rho^2}{1-\rho}$
  * 平均逗留时间：$W = \frac{1}{\mu - \lambda}$
  * 平均等待时间：$W_q = \frac{\lambda}{\mu(\mu-\lambda)}$

===== 6.7 纯生过程与泊松过程 =====

==== 6.7.1 纯生过程 ====

**定义6.7（纯生过程）** 生灭过程中 $\mu_i = 0$ 对所有 $i$，称为**纯生过程**。

**Yule过程**：$\lambda_i = i\lambda$（线性出生率），描述种群分裂模型。

**定理6.9（Yule过程）** Yule过程中，若 $X(0) = 1$，则：
$$P(X(t) = n) = e^{-\lambda t}(1 - e^{-\lambda t})^{n-1}, \quad n = 1, 2, \ldots$$
服从几何分布！

==== 6.7.2 泊松过程作为纯生过程 ====

泊松过程是纯生过程的特例：$\lambda_i = \lambda$（常数）。

===== 6.8 状态分类 =====

==== 6.8.1 互通性 ====

连续时间马尔可夫链的状态互通性与嵌入链相同。

**定理6.10** 状态 $i$ 和 $j$ 在CTMC中互通当且仅当在嵌入链中互通。

==== 6.8.2 常返与非常返 ====

**定理6.11** 状态 $i$ 在CTMC中是常返的当且仅当在嵌入链中是常返的。

==== 6.8.3 正常返与平稳分布 ====

**定理6.12** 不可约连续时间马尔可夫链存在平稳分布当且仅当它是正常返的。

**定理6.13** 平稳分布 $\boldsymbol{\pi}$ 满足全局平衡方程：
$$\sum_i \pi_i q_{ij} = 0, \quad \forall j \in S$$
或等价地：
$$\pi_j q_j = \sum_{i \neq j} \pi_i q_{ij}$$

这表示进入状态 $j$ 的速率等于离开状态 $j$ 的速率。

===== 6.9 细致平衡与可逆性 =====

**定义6.8（细致平衡）** 分布 $\boldsymbol{\pi}$ 满足**细致平衡**，如果对任意 $i, j$：
$$\pi_i q_{ij} = \pi_j q_{ji}$$

**定理6.14** 若细致平衡成立，则 $\boldsymbol{\pi}$ 是平稳分布。

**定理6.15** 生灭过程满足细致平衡，因此是可逆的。

===== 6.10 本章例题详解 =====

**例题1** 设两状态CTMC，生成元 $\mathbf{Q} = \begin{pmatrix} -\alpha & \alpha \\ \beta & -\beta \end{pmatrix}$。

(1) 求 $\mathbf{P}(t)$
(2) 求平稳分布

**解**：

(1) 特征值：$\det(\mathbf{Q} - \lambda\mathbf{I}) = (\alpha + \lambda)(\beta + \lambda) - \alpha\beta = \lambda(\lambda + \alpha + \beta) = 0$

$\lambda_1 = 0$，$\lambda_2 = -(\alpha + \beta)$

通过矩阵指数或求解微分方程得：
$$\mathbf{P}(t) = \frac{1}{\alpha + \beta}\begin{pmatrix} \beta + \alpha e^{-(\alpha+\beta)t} & \alpha - \alpha e^{-(\alpha+\beta)t} \\ \beta - \beta e^{-(\alpha+\beta)t} & \alpha + \beta e^{-(\alpha+\beta)t} \end{pmatrix}$$

(2) 令 $\mathbf{P}'(t) = 0$ 或解 $\boldsymbol{\pi}\mathbf{Q} = 0$：
$$\pi_0 = \frac{\beta}{\alpha + \beta}, \quad \pi_1 = \frac{\alpha}{\alpha + \beta}$$

**例题2** M/M/c队列：$c$ 个服务台，到达率 $\lambda$，服务率 $\mu$。

求平稳分布存在的条件和具体形式。

**解**：生灭过程，参数：
$$\lambda_n = \lambda \text{（所有 } n\text{）}$$
$$\mu_n = \begin{cases} n\mu & 0 \leq n \leq c \\ c\mu & n \geq c \end{cases}$$

稳定性条件：$\lambda < c\mu$。

平稳分布：
$$\pi_n = \begin{cases} \pi_0 \frac{(\lambda/\mu)^n}{n!} & n \leq c \\ \pi_0 \frac{(\lambda/\mu)^n}{c! c^{n-c}} & n \geq c \end{cases}$$

其中 $\pi_0$ 由归一化确定。

===== 6.11 本章习题 =====

**习题6.1** 设 $\mathbf{Q} = \begin{pmatrix} -2 & 1 & 1 \\ 2 & -4 & 2 \\ 1 & 2 & -3 \end{pmatrix}$。

(1) 验证 $\mathbf{Q}$ 是有效生成元
(2) 求嵌入链转移矩阵
(3) 求平稳分布

**习题6.2** 纯生过程，$\lambda_i = i\lambda$（Yule过程），$X(0) = n_0$。

(1) 求 $E[X(t)]$
(2) 求 $Var(X(t))$

**习题6.3** M/M/1队列，$\lambda = 3$，$\mu = 4$。

(1) 求平稳分布
(2) 求系统中平均顾客数
(3) 求顾客等待时间超过2分钟的概率

**习题6.4** 生灭过程，$\lambda_i = \lambda$（$i \geq 0$），$\mu_i = i\mu$（$i \geq 1$）（移民-死亡过程）。

(1) 求平稳分布存在的条件
(2) 求平稳分布

**习题6.5** 证明：连续时间马尔可夫链的嵌入链常返，则原链常返。反之是否成立？

**习题6.6** 机器维修问题：两台机器，一台工作一台备用。工作时间 $\sim Exp(\lambda)$，修理时间 $\sim Exp(\mu)$。

(1) 建立CTMC模型
(2) 求平稳分布
(3) 求两台机器都故障的稳态概率

**习题6.7** 设CTMC的生成元 $\mathbf{Q}$ 对称（$q_{ij} = q_{ji}$），证明均匀分布是平稳分布。

**习题6.8** 电话交换台有 $n$ 条线路，呼叫按泊松过程到达（速率 $\lambda$），通话时间 $\sim Exp(\mu)$。若线路占满，呼叫丢失。

(1) 建立模型
(2) 求呼叫丢失概率（Erlang B公式）

----

**上一章**：[[第五章_状态的分类与极限分布]] | **下一章**：[[第七章_条件期望与鞅]]