05 连续时间 Markov 链：等多久，往哪里跳

医院急诊室的状态不是每隔一小时才更新一次：病人可能在上午 10:03 到达，10:17 离开，10:26 又有人进入。若把时间硬切成很细的小格，就会遇到一个麻烦：格子取得多细才算合适？更自然的模型是直接描述“此刻处于哪个状态”“下一次变化还要等多久”，并让等待时间由状态决定。

如果只记病人数量变化的先后顺序，等了半分钟和等了半小时就看不出区别。连续时间 Markov 链（continuous-time Markov chain，CTMC）把跳向哪里与等待多久放在同一个模型中。我们会从一台设备的故障与修复算起，再看一个小停车场：车越多，总离开速率究竟会不会变？这句话若没读准，后面的平稳分布也会跟着算错。

从“下一步”改成“下一次跳变”

设 $X(t)$ 在 $t\ge0$ 时取值于有限或可数状态空间 $S$。它满足 Markov 性，是指给定当前状态后，未来与过去无关：

若转移规律只依赖时间间隔 $s$，而不依赖日历时刻 $t$，称为时间齐次。记

则 $P(t)=(p_{ij}(t))$ 是时间 $t$ 的转移矩阵，并且满足半群关系

这个乘法表达的是：从现在走 $s+t$ 时间，可以分成“先走 $s$，再走 $t$”；中间状态求和，正是普通的全概率分解。

本章研究时间齐次、右连续、分段常值的跳过程，每个状态的总离开速率有限，并要求有限时间内几乎必然只发生有限次跳变，这称为非爆炸。右连续约定说的是：发生跳变的那个时刻，记录已经到达的新状态。有限状态模型满足这些条件最方便；可数无穷状态时，逐个速率有限还不够，稍后会看到跳得越来越快的反例。

生成矩阵：把极短时间内的变化率写下来

对 $i\ne j$，定义跳转率

如果该极限存在且有限。令

表示从状态 $i$ 离开的总速率。生成矩阵 $Q=(q_{ij})$ 的对角线定义为

因此每一行的和为零，非对角元非负。短时间 $h$ 内的近似是

“$o(h)$”表示误差除以 $h$ 后趋于 $0$。固定有限状态模型中，总速率有共同上界，两次或更多跳变的概率为 $O(h^2)$；本章后面的统一时钟表示会给出这个界。因此，指定一次跳转贡献了短时间端点概率的一阶项。这里的 $p_{ij}(h)$ 仍然是“时刻 在 ”的概率，它包含所有可能路径，并不要求中途恰好只跳一次。

例题：把设备故障率翻译成 $Q$

设备有三个状态：$0$ 表示正常，$1$ 表示降级运行，$2$ 表示停机。正常到降级的速率为 $0.4$（每小时），正常到停机的速率为 $0.1$；降级到正常的速率为 $0.8$，降级到停机的速率为 $0.2$，停机到降级的速率为 $1.5$，停机不能直接回到正常。写出生成矩阵，并近似计算从状态 出发， 小时后处于状态 的概率。

选择生成矩阵是因为题目给的是“每小时速率”，而不是固定时间间隔的转移概率。对角线不能凭感觉填写，要用离开该状态的所有速率之和取负。

等待时间与下一跳各自记录什么

刚进入状态 $i$ 时，把离开它的等待时间记为 $T_i$。在本章的时间齐次跳过程条件下，只要还没离开，未来的等待规律就和刚进入时相同：当前状态相同，时间齐次性又排除了日历时刻的影响。于是生存函数满足 $S_i(t+s)=S_i(t)S_i(s)$。这用到了时间齐次性，不能只凭“有 Markov 性”就对任意模型断言等待一定服从固定参数的指数分布。

具体写 $S_i(t)=\mathbb P_i(T_i>t)$。在当前跳过程模型下，小时间内尚未离开的概率为 。留在 的端点概率还允许“出去再回来”，但这不影响这一阶项。因此

移项、除以 $h$，再令 $h\downarrow0$，得到微分方程

解为

因此

如果 $q_i=0$，则 $T_i=\infty$，状态 $i$ 是吸收态；不要把它写成均值有限的指数变量。若 $q_i>$，离开后跳向 的条件概率是

这个比值还能从联合分布看得更清楚。令 $J$ 为下一状态，要使 $T_i$ 落在 $[t,t+dt)$ 且 $J=j$，必须先保持在 到 ，再以速率 跳向 。所以联合密度为

右边分成指数等待的密度和目标状态的概率，因此给定当前状态后，$T_i$ 与 $J$ 独立。这才允许我们用两次独立抽样模拟一次跳变：抽等待时间，再按 $q_{ij}/q_i$ 抽去向。

若几种可能事件各有独立指数时钟，速率为 $a_1,\ldots,a_k$，则第一个时钟响起的等待时间满足

第 $r$ 类先发生的联合密度为 $a_re^{-(\sum a_\ell)t}$，同样得到胜出概率 $a_r\mathrm{/}\sum$。独立性在这里很关键；不能把任意相关等待的速率直接相加。

回到设备例，从降级状态 1 出发，总率为 1，下一跳到 0 的概率为 0.8。因此

取 $h=0.05$，这个首跳事件的概率约为 $0.039016$。如果还要求跳到 0 后直到 $h$ 都不再跳，概率则为

它又是一个不同事件。三个问题的一阶近似都是 $0.8h$，精确概率却不能互换。

有限时间内跳变次数的边界

有限状态时令 $M=\max_iq_i$。若 $M=0$，所有状态都吸收，不会跳变；若 $M>0$，每次等待可以写成 ，其中 是独立的参数 1 指数变量。非吸收状态上 ，后者累加后由大数律发散。因此不可能在有限时间内完成无穷次跳变；若遇到吸收态，跳变直接停止。

可数状态时可能没有共同的 $M$。例如从 $n$ 只能跳到 $n+1$，速率为 $2^n$，从 0 开始。完成无穷次跳变所需时间为 $\sum_{n\ge0}T_n$，其期望为 。非负随机变量的期望有限，意味着它几乎必然有限，所以这个过程会爆炸。若要继续描述爆炸后的行为，还需要另作规定；它不属于本章采用的非爆炸模型。

例题：等待时间与下一状态的联合判断

某服务系统当前有任务正在处理，记为状态 $i$。接下来改变任务数量的事件有“新任务到达”和“一个任务完成”，在这个状态下两类独立指数时钟的速率分别为 $2$ 与 $3$（每小时）。求下一次状态变化的平均等待时间，以及下一次变化是新任务到达的概率。

题目只问当前状态离开的第一跳，因此不需要先求 $P(t)$。先把所有离开速率相加得到总速率，再利用“各跳转率除以总速率”的竞争风险解释。

练习 1（等待机制的巩固）

当前状态 $i$ 有三条可能跳转，速率分别为 $1.2,0.8,2.0$（每分钟）。求总等待时间的分布、平均等待时间，以及下一次跳向第一条目标状态的概率。

从生成矩阵得到前向与后向方程

有了短时间近似，可以把半群关系和一个小时间片结合起来。对于行向量约定，Chapman–Kolmogorov 关系给出

因为 $P(h)=I+hQ+o(h)$，所以

这得到前向方程

也可以把小时间片放在前面：

从而得到后向方程

这里的差商、矩阵乘法和极限交换都在有限维中进行，所以下面的推导先限定为有限状态。两式都成立，解为

这里的矩阵指数定义为 $e^{tQ}=\sum_{n\ge0}t^nQ^n/n!$。有限矩阵的幂级数在有界时间区间一致收敛，可以逐项求导，得到 ，且初值为 ；有限维线性常微分方程的唯一性确定了它就是 。

前向方程看末尾的小时间片：此刻各状态有多少概率质量，各以什么速率流入或流出目标状态。后向方程把小时间片放在开头：从起点可能先保持不动，也可能先去另一个状态，之后再运行 $t$。它们并不是在逐条定位完整路径的“最后一次实际跳变”。只问某个边际概率时，选未知量更少的写法常会省去大量矩阵计算。

坐标形式分别为

和

由于 $Q$ 的行和为 $0$，前向方程右侧每行求和为 $0$，因此概率总和随时间保持不变；这说明生成矩阵的行和条件不是记号习惯，而是概率守恒的微分表达。

一个保证概率非负的表示

矩阵指数里有负的对角元，直接看幂级数不容易知道结果为何非负。选 $r\ge\max_iq_i$ 且 $r>0$，定义

$R$ 非负、每行和为 1，是离散时间转移矩阵。由于 $Q=r(R-I)$，而 $I$ 与 $R$ 可交换，

系数非负且总和为 $e^{-rt}e^{rt}=1$，所以它是转移矩阵 $R^k$ 的加权平均。这个公式叫统一化表示：让一个速率为 $r$ 的公共时钟响起，每次按 选下一状态；选中自己时状态不变。这类时钟响动只是为了统一计算，不能算作真实跳变。下一章会把“时段 内响了 次”的权重正式认作 Poisson 分布。

每次在 $i$，时钟以概率 $q_i/r$ 造成真实离开，其余时候仍在 $i$。真实跳变数不超过时钟响动数，因此小时间 $h$ 内至少两次真实跳变的概率不超过

补上了前面短时近似的依据。若用有限项求和近似 $P(t)$，遗漏的系数和也给出每个坐标误差的上界。直接用 $I+tQ$ 则没有这个保证：例如离开速率为 3，取 $t=1$，对角近似会成为 $-2$。近似的时间间隔必须足够短。

例题：两状态 CTMC 的完整转移概率

状态 $0$ 以速率 $\alpha$ 跳到状态 $1$，状态 $1$ 以速率 $\beta$ 跳到状态 $0$，其中 $\alpha,\beta>0$。求从状态 出发时 ，并找出平稳分布。

令

只追踪“此刻在状态 $1$”这一件事最省力：从 $0$ 流入 $1$ 的速率是 $\alpha(1-u)$，从 $1$ 流出到 $0$ 的速率是 $\beta u$。因此用前向流量平衡建立标量方程。

完整转移矩阵为

时间占比和平稳方程

有限状态时，平稳分布的定义仍是“从它出发后分布不变”，即对全部 $t\ge0$ 都有 $\pi P(t)=\pi$。在 $t=0$ 求导得到必要条件 $\pi Q=0$；反过来， 使幂级数中所有正次项消失，确有 。因而

是有限状态 CTMC 的平稳方程。

若有限链不可约，选严格大于全部 $q_i$ 的 $r$，则 $R=I+Q/r$ 既不可约又有自环。上一章证明 $R^k$ 从任意起点收敛到唯一平稳分布 。在统一化表示中， 增大时，固定前面有限个 的总权重趋于零；余下足够大的 对应的 已接近 ，于是 也收敛到 。所以这里无需再排除离散跳链的周期：随机等待已经打破固定时刻的相位锁定。

但是，如果你只在每次真实跳变后记一次状态，得到的是另一条离散链，称为嵌入跳链，其转移矩阵为

这个公式要求 $q_i>0$；吸收态没有下一次真实跳变，不能除以零。对于至少两个状态的有限不可约 CTMC，所有 $q_i>0$。记跳链的平稳分布为 $\eta$，则

第一式可以直接核验：$\sum_{i\ne j}\pi_iq_iK_{ij}=\sum_{i\ne j}\pi_iq_{ij}=\pi_jq_j$，最后一步就是 的第 个坐标。

第二式解释时间占比。按跳变计数，访问 $i$ 的比例趋于 $\eta_i$，不需要跳链非周期；每次来到 $i$，独立的指数停留平均长 $1/q_i$。分别对这些等待时间用大数律，在很多个完整停留段中，状态 $i$ 累计用时占比就趋于上式的 。观察终点切在半段也不改变极限：有限多个状态的各次等待都有有限均值，一次等待除以已完成段数趋于零，而总用时除以段数趋于正的有限常数。于是

比如 $\alpha=2,\beta=1$，真实跳链总在 0、1 之间交替，按跳变数看两边各占约一半。但每次在 0 平均停 $1/2$，在 1 平均停 $1$，所以按钟表计时的长期比例是 $(1/3,2/3)$。若把两条速率同时乘 5，状态序列的规则没变，全部等待缩短为原来的 $1/5$，平稳占比也没变；变化的是走到那个长期结构需要的时间尺度。

先设 $\alpha=2,\beta=1$，从 0 出发。你会看到按跳变计数的比例很快接近各半，但按停留时长算出的比例朝 $1/3,2/3$ 波动。把观察终点拖到一个停留段中间，检查最后一段只累计已经观察到的时间；它还没有结束，不能把截下来的长度当成一次完整指数等待。保持种子再延长观察时间，路径前缀应保持相同。旁边的 $p_{01}(t)$ 是多次重复实验在固定时刻的概率，并不等于这一条路径的状态值。

Birth–death 链：只在相邻状态间变化

许多计数系统的状态是当前对象数 $n=0,1,2,\ldots$。一次事件只能让数量增加一个或减少一个，于是得到 birth–death 链：

边界要单独处理：在 $0$ 处没有 $n=-1$，所以 $\mu_0=0$；若容量上限为 $M$，则 $\lambda_M=0$。状态 的等待时间是速率 的指数分布，下一次向上跳的概率是

向下跳的概率是

若存在平稳分布 $\pi$，平稳方程 $\pi Q=0$ 在 birth–death 结构下可化成局部关系

为什么能这样化？令 $J_n=\pi_n\lambda_n-\pi_{n+1}\mu_{n+1}$ 表示跨过边 的净流量。状态 的平衡方程给出 ；状态 的方程再给出 ，递推下去所有 。因此在线性状态空间和自然边界下，整体平衡会逼出逐边详细平衡。

递推公式为

最后必须检查归一化常数

是否有限。容量为 $M$ 时，求和只到 $M$，$Z$ 自动有限；无限容量时，除了归一化，还须确认采用的是非爆炸过程。这里讨论相邻边的出生、死亡速率均为正的不可约情形；在这个范围内，有限的 $Z$ 才给出平稳概率分布。若某条边速率为零，要按闭类和可达关系另作分析，不能继续在递推式里除以零。

例题：有限容量的 birth–death 系统

一个小型停车场最多停 $3$ 辆车。车辆以每小时 $2$ 辆的速率进入，只要还没满；每辆车独立地以每小时 $1$ 的速率离开。因此状态 $n\in\{0,1,2,3\}$，求平稳分布，并计算长期平均车辆数。

读到“每辆车独立地离开”，要把当前所有车的离开机会相加。有 $n$ 辆车时，最早离开的等待时间是 $n$ 个独立参数 1 指数变量的最小值，因此总离开速率是 $\mu_n=n$，而非固定的 1。进入速率为 $\lambda_0=\lambda_1=\lambda_2=2$，满场时 。

还可以检查单位时间的总流量。平稳时被接纳的到达率为 $2(1-\pi_3)=30/19$，总离开率为 $\sum_n n\pi_n=30/19$，两者吻合。若算出长期进入比离开更多，概率质量就不可能保持平衡。

去掉容量上限之前，要保留离开机制

有两种不同模型，值得放在一起比较。

若只有一个服务台，每次只处理一个任务，忙碌时总完成速率恒为 $\mu$，则 $\lambda_n=\lambda$，$\mu_n=\mu$（$n\ge1$）。写 ，递推权重为 。总速率有界，过程非爆炸；权重仅在 时可归一化，得到

$\rho=1$ 时每个权重都为 1，$\rho>1$ 时权重还在增长，都没有平稳概率分布。有限容量的柱形图始终能归一化，不能据此认定无限容量系统也能稳定。

若保留停车场的独立离开机制，并让容量无限，则 $\mu_n=n\mu$。同样写 $\rho=\lambda/\mu$，权重却变成

它们对任何有限 $\rho$ 的总和都是 $e^\rho$，所以

这个过程也非爆炸：有限时间内，恒定速率的出生只有有限次，而死亡次数不超过初始数量加上出生次数。这里的出生等待为独立参数 $\lambda$ 的指数变量，累加发散即可证明前一句，无需预先使用下一章的计数分布。一个是总离开能力固定，一个是对象越多、总离开能力越大；同一个 $\lambda/\mu$ 可以给出完全不同的长期结果。

练习 2（birth–death 的变式）

无限状态 birth–death 链的出生速率恒为 $\lambda=3$，在非零状态的总死亡速率恒为 $\mu=4$。判断它是否有平稳分布，并求 $\pi_0,\pi_1,\pi_2$。

设容量为 3、到达率为 2、每辆车离开率为 1，核对图上从状态 2 向下的速率确实是 2，向下箭头对应的平稳流量是 $12/19$。切换为“总离开速率恒定”，观察 $Q$、停留时间和平稳柱形图一起怎样变化。两种模型中都把容量逐渐增大：固定总离开机制在 $\rho\ge1$ 时没有无限容量平稳分布，而独立离开机制仍有可归一化的权重。实验中有限容量的结果和无限容量的结论会分别列出，读图时也请保留这个区别。

用方程选择合适的计算路线

遇到 CTMC 问题时，可以先辨认题目要的是哪一层信息。若只问下一次跳变，求总速率和竞争概率即可；若问固定时间 $t$ 的分布，需要前向／后向方程或矩阵指数；若图是相邻状态的 birth–death 结构，平稳问题优先检查局部流量；若存在吸收状态，则要区分“最终吸收”与“有限时刻已经吸收”的概率。

练习 3（迁移：前向方程的状态流量）

某 CTMC 有三个状态，生成矩阵为

令 $r_j(t)=\mathbb P(X(t)=j)$，当前分布为 $r(0)=(0.5,0.5,0)$。求 ，并解释它是哪些流量的差。

练习 4（巩固：生成矩阵与短时概率）

对两状态 CTMC，

从状态 $0$ 出发，求 $h$ 很小时在时间 $h$ 处于状态 $1$ 的概率的一阶近似，并求状态 $0$ 的平均停留时间。

练习 5（变式：平稳方程与动态方程对照）

对两状态 CTMC，状态 $0\to1$ 的速率为 $2$，状态 $1\to0$ 的速率为 $1$。求平稳分布，并写出从 $0$ 出发时 $u(t)=p_{01}(t)$ 满足的微分方程和初值。

练习 6（迁移：容量边界的作用）

一个容量为 $2$ 的单服务台系统有出生速率 $\lambda$，在非空状态的总完成速率恒为 $\mu$，其中 $\lambda,\mu>0$。写出生成矩阵，并说明为什么第三个状态的出生率必须是 $0$。再用 $\rho=\lambda/\mu$ 表示平稳分布。

用不同问题核对同一个模型

11. 容量为 2 的系统，到达率为 3，每个对象独立以速率 2 离开。写出 $Q$ 和平稳分布。若把“每个对象”误读为“整个系统”，哪些行和结果会改变？

12. 从状态 $i$ 有两条独立竞争时钟，速率分别为 2 和 3。求下一次变化在 $0.1$ 小时内且属于第一类的概率。只给这两个速率，能否求 $0.1$ 小时后处于第一类目标状态的精确概率？

13. 两状态链速率为 $0\to1:3$、$1\to0:1$。取统一时钟速率 $r=4$，写出 $R$；求从 0 出发时 $p_{01}$、时间占比和嵌入跳链的长期访问比例。如果两条真实速率都乘 2，分别如何变化？

14. 从 $n$ 只向 $n+1$ 跳，速率为 $3^{n+1}$。每个状态的速率都有限，能否据此断言非爆炸？从 0 完成无穷次跳变的总等待时间，其期望是多少？

15. 无容量上限，到达率为 6。模型 A 在非零状态总离开率为 4；模型 B 每个对象独立以速率 4 离开。判断两者是否有平稳概率分布，并解释结论为何不同。