连续时间马尔可夫链（Continuous-Time Markov Chain, CTMC）是离散时间马尔可夫链向连续时间的推广。与离散情形不同，状态转移可以在任意时刻发生，系统的演化由停留时间（Holding Time）和转移概率共同描述。
典型应用：
定义6.1（连续时间马尔可夫链） 随机过程 $\{X(t), t \geq 0\}$ 称为连续时间马尔可夫链，如果：
$$P(X(t+s) = j | X(u), 0 \leq u \leq t) = P(X(t+s) = j | X(t) = i)$$
定义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))$ 满足：
定义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.4（生成元） 矩阵 $\mathbf{Q} = (q_{ij})$ 称为连续时间马尔可夫链的生成元或无穷小生成元（Infinitesimal Generator），满足：
定理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.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 Kolmogorov方程的解为： $$\mathbf{P}(t) = e^{\mathbf{Q}t} = \sum_{n=0}^{\infty} \frac{(\mathbf{Q}t)^n}{n!}$$
对于有限状态空间，此级数收敛。
定理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（嵌入链） 设 $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（生灭过程） 状态空间 $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.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.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.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$$ 几何分布！
性能指标：
定义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$$ 服从几何分布！
泊松过程是纯生过程的特例：$\lambda_i = \lambda$（常数）。
连续时间马尔可夫链的状态互通性与嵌入链相同。
定理6.10 状态 $i$ 和 $j$ 在CTMC中互通当且仅当在嵌入链中互通。
定理6.11 状态 $i$ 在CTMC中是常返的当且仅当在嵌入链中是常返的。
定理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.8（细致平衡） 分布 $\boldsymbol{\pi}$ 满足细致平衡，如果对任意 $i, j$： $$\pi_i q_{ij} = \pi_j q_{ji}$$
定理6.14 若细致平衡成立，则 $\boldsymbol{\pi}$ 是平稳分布。
定理6.15 生灭过程满足细致平衡，因此是可逆的。
例题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.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公式）
上一章：第五章_状态的分类与极限分布 | 下一章：第七章_条件期望与鞅