第8章马尔可夫链：离散时间与连续时间

系统分析：线性规划、非线性规划与排队模型 · 第 8 / 11 篇（展开目录）

从线性规划建模、单纯形法、对偶与灵敏度、运输与指派，到非线性规划、随机过程、马尔可夫链、排队模型和决策分析，每章都配手算例题和自测，最后一章用综合例题把方法串起来。

约 40 分钟 · 需要第7章的几何、指数和泊松分布

读完你能： 判断一个系统能否建成马尔可夫链并选取状态；写出转移概率矩阵（含泊松需求的库存模型）；画状态转移图；求平均逗留时间、 $n$ 步转移概率和稳态概率；对连续时间链写出转移速率矩阵 $Q$ 和速率平衡方程，求稳态概率、生产率；处理生灭过程。

1. 马尔可夫性质

离散时间随机过程 $\{X_n\}$ ，状态空间可数。若

P(X_n=j\mid X_{n-1}=i,\ X_{n-2}=i_2,\ \dots,\ X_0=i_n)=P(X_n=j\mid X_{n-1}=i),

就是离散时间马尔可夫链（DTMC）：已知现在，将来与过去无关。若转移概率不随 $n$ 变化，称为齐次链，本章只讨论齐次链。

建模时最重要的一步是选状态：状态必须包含预测下一步所需的全部信息。如果“下一步怎样”还取决于“之前发生过什么”，就要把那部分信息也放进状态里。

2. 转移概率矩阵与状态转移图

一步转移概率 $p_{ij}=P(X_n=j\mid X_{n-1}=i)$ 组成转移概率矩阵（TPM） $P=[p_{ij}]$ ：

0\le p_{ij}\le1,\qquad \sum_j p_{ij}=1\quad(\text{每一行加起来等于 1}).

状态转移图：每个状态画一个节点， $p_{ij}>0$ 时画一条从 $i$ 到 $j$ 的有向边并标上 $p_{ij}$ 。

例1：两状态机器。 每小时检查一次：状态 0 = 正常，状态 1 = 维修中。正常的机器一小时内坏掉的概率 $a=0.1$ ，维修中的机器一小时内修好的概率 $b=0.6$ ：

P=\begin{pmatrix}1-a&a\\b&1-b\end{pmatrix}=\begin{pmatrix}0.9&0.1\\0.6&0.4\end{pmatrix}.

例2：两台独立机器，坏了不修。 每台每小时坏的概率 $a$ 。状态 = 坏了几台：

P=\begin{pmatrix}(1-a)^2&2a(1-a)&a^2\\0&1-a&a\\0&0&1\end{pmatrix}.

$p_{01}=2a(1-a)$ 是因为“第一台坏第二台好”和“第一台好第二台坏”两种情况。状态 2 一旦进入就不再离开（ $p_{22}=1$ ），叫吸收态。

3. 逗留时间

链进入状态 $i$ 后，连续停留的步数 $T_i$ 满足 $P(T_i>n)=p_{ii}^n$ ，所以 $T_i$ 是成功概率为 $1-p_{ii}$ 的几何随机变量：

E(T_i)=\frac{1}{1-p_{ii}} .

例1中：正常状态平均持续 $1/0.1=10$ 小时，维修状态平均持续 $1/0.6\approx1.67$ 小时。 $p_{ii}=0$ 时每次只停 1 步； $p_{ii}=1$ 时永远不离开。

4. n 步转移：Chapman–Kolmogorov 方程

从 $i$ 出发 $m+n$ 步后到 $j$ ，必须在第 $m$ 步时处于某个中间状态 $k$ ：

p_{ij}(m+n)=\sum_k p_{ik}(m)\,p_{kj}(n)\qquad\Longleftrightarrow\qquad P(m+n)=P(m)P(n).

由此 $P(n)=P^n$ ：** $n$ 步转移矩阵就是一步矩阵的 $n$ 次方。**

若初始分布为行向量 $\pi(0)$ ，则 $n$ 步后的分布

\pi(n)=\pi(0)P^n .

例1 续： 现在机器正常，两小时后它在维修中的概率？

P^2=\begin{pmatrix}0.9&0.1\\0.6&0.4\end{pmatrix}^2=\begin{pmatrix}0.87&0.13\\0.78&0.22\end{pmatrix},

$\pi(2)=(1,0)P^2=(0.87,\ 0.13)$ ，所求概率 0.13。

5. 稳态概率

很多链运行足够长时间后，处于各状态的概率趋于固定值，并且与初始状态无关。设 $Y=\lim_{n\to\infty}\pi(n)$ ，在 $\pi(n)=\pi(n-1)P$ 两边取极限：

Y=YP,\qquad \sum_j y_j=1,\qquad y_j\ge0 .

$y_j$ 是长期来看链处于状态 $j$ 的时间比例。此时 $P^n$ 的每一行都趋于 $Y$ 。

例1 续： $Y=YP$ 的第一个分量给出 $y_0=0.9y_0+0.6y_1$ ，即 $0.1y_0=0.6y_1$ ——流出状态 0 的概率流等于流入的。加上 $y_0+y_1=1$ ：

y_0=\frac{b}{a+b}=\frac{0.6}{0.7}=\frac67,\qquad y_1=\frac{a}{a+b}=\frac17 .

机器长期有 $6/7\approx85.7\%$ 的时间可用。

稳态不一定存在或唯一

若 $a=b=0$ ， $P=I$ ，链永远停在初始状态，任何分布都满足 $Y=YP$ ，稳态不唯一。若 $a=b=1$ ，链在 0、1 之间来回跳， $P^n$ 不收敛（偶数步回到原状态），但 $Y=(0.5,0.5)$ 仍表示长期时间比例。应区分两件事：平稳分布满足 $Y=YP$ ；从任意初始状态收敛到该分布则还需要条件，例如有限状态链不可约且非周期。不能把平稳分布一律定义成必然存在的极限。

$Y=YP$ 中有一个方程是多余的（因为每行和为 1），求解时用 $\sum y_j=1$ 替换掉其中一个。

6. 泊松需求的库存模型

这是一类典型的建模题：每期需求是独立的泊松随机变量，期末按某个规则补货，“期末剩余量”构成马尔可夫链。

例3： 一家店某种限量商品最多放 3 件。每天的需求 $D_k$ 独立，服从 $\lambda=1$ 的泊松分布。补货规则：当天结束时剩余不超过 1 件，就在夜里补到 3 件；剩 2 件或 3 件就不补。 设 $L_k$ 为第 $k$ 天结束时的剩余件数， $L_0=3$ 。

第一步，状态空间。 剩余件数只能是 $\{0,1,2,3\}$ 。

第二步，每个状态第二天以多少件开始。

今天结束时 $L_{k-1}$	0	1	2	3
明天开始时的库存	3	3	2	3

第三步，从“开始库存 $s$ ”算到“结束剩余 $j$ ”。 剩 $j>0$ 件要求需求恰好为 $s-j$ ；剩 0 件要求需求 $\ge s$ （多出的需求丢失）：

P(\text{剩 }j)=P(D=s-j)\ (1\le j\le s),\qquad P(\text{剩 }0)=P(D\ge s)=1-\sum_{d=0}^{s-1}P(D=d).

泊松 $\lambda=1$ ： $P(D=0)=e^{-1}$ ， $P(D=1)=e^{-1}$ ， $P(D=2)=\tfrac12e^{-1}$ ， $P(D=3)=\tfrac16e^{-1}$ 。

开始 3 件：剩 3 件 $e^{-1}$ ，剩 2 件 $e^{-1}$ ，剩 1 件 $\tfrac12e^{-1}$ ，剩 0 件 $1-\tfrac52e^{-1}$ 。开始 2 件：剩 2 件 $e^{-1}$ ，剩 1 件 $e^{-1}$ ，剩 0 件 $1-2e^{-1}$ 。

第四步，组装 TPM（行：今天结束时，列：明天结束时，顺序 0,1,2,3）：

P=\begin{pmatrix} 1-\frac52e^{-1}&\frac12e^{-1}&e^{-1}&e^{-1}\\[2pt] 1-\frac52e^{-1}&\frac12e^{-1}&e^{-1}&e^{-1}\\[2pt] 1-2e^{-1}&e^{-1}&e^{-1}&0\\[2pt] 1-\frac52e^{-1}&\frac12e^{-1}&e^{-1}&e^{-1} \end{pmatrix} \approx\begin{pmatrix} 0.0803&0.1839&0.3679&0.3679\\ 0.0803&0.1839&0.3679&0.3679\\ 0.2642&0.3679&0.3679&0\\ 0.0803&0.1839&0.3679&0.3679 \end{pmatrix}.

第 0、1、3 行相同——因为这三种情况第二天都从 3 件开始。检查：每行之和为 1。

平均逗留时间 $1/(1-p_{ii})$ ：状态 0 为 1.087 天，状态 1 为 1.225 天，状态 2、3 各为 1.582 天。状态 0（售罄）停留最短。

稳态概率：解 $Y=YP$ 、 $\sum y_j=1$ ，得

y_0\approx0.148,\quad y_1\approx0.252,\quad y_2=e^{-1}\approx0.368,\quad y_3\approx0.233 .

（ $y_2$ 恰好等于 $e^{-1}$ ：从任何状态到状态 2 的概率都是 $e^{-1}$ ，所以列 2 的加权和就是 $e^{-1}$ 。）长期来看约 14.8% 的日子以售罄收尾。

多步问题： 周一结束时售罄，周三结束时剩 1 件的概率？这是从状态 0 出发两步到状态 1： $p_{01}(2)=[P^2]_{01}$ 。由于第 0、1、3 行相同， $P^2$ 的每一行都已经等于稳态分布，所以答案约为 0.252。一般情况下就老老实实算矩阵乘法： $[P^2]_{01}=\sum_k p_{0k}p_{k1}$ 。

写 TPM 的检查清单

状态空间是否包含所有可能的取值？2. 每个状态“下一期从哪里开始”有没有按规则处理？3. “剩 0”是否用了 $P(D\ge s)$ 而不是 $P(D=s)$ ？4. 每行之和是否为 1？

7. 连续时间马尔可夫链

若时间连续、状态离散，并满足马尔可夫性质，就是连续时间马尔可夫链（CTMC）。由无记忆性可以推出：链在状态 $i$ 的逗留时间服从指数分布，速率记为 $\nu_i$ 。 $\nu_i=0$ 时 $i$ 是吸收态。

CTMC 用转移速率矩阵（生成矩阵） $Q=[q_{ij}]$ 描述：

$q_{ij}$ （ $i\ne j$ ）：从 $i$ 直接转到 $j$ 的速率；
$q_{ii}=-\sum_{j\ne i}q_{ij}=-\nu_i$ ：每行之和为 0。

转移概率矩阵 $H(t)=[p_{ij}(t)]$ 满足 Chapman–Kolmogorov 方程 $H(s+t)=H(s)H(t)$ 和前向 Kolmogorov 方程 $\dfrac{dH(t)}{dt}=H(t)Q$ ，解为 $H(t)=e^{Qt}$ ；状态分布 $\pi(t)=\pi(0)e^{Qt}$ ，满足 $\dfrac{d\pi(t)}{dt}=\pi(t)Q$ 。

稳态： 令 $d\pi/dt=0$ ：

\pi Q=0,\qquad \sum_j\pi_j=1,\qquad \pi_j\ge0 .

逐项展开就是速率平衡方程：

\pi_j\sum_{k\ne j}q_{jk}=\sum_{k\ne j}\pi_kq_{kj}\qquad(\text{流出 } j \text{ 的速率} = \text{流入 } j \text{ 的速率}).

画好状态转移图（边上标速率）后，对每个状态写“出 = 入”，比做矩阵乘法快得多。

8. 例：加工—故障—维修

一台机器循环工作：先准备（速率 $s=4$ /小时），然后加工一个零件（速率 $p=2$ /小时）；加工中可能故障（速率 $f=0.5$ /小时），修理速率 $r=1$ /小时。所有时间相互独立且服从指数分布。

状态：0 = 准备，1 = 加工，2 = 维修。

续做策略：修好后继续加工原来那个零件（回到状态 1）。

在状态 1 有两个出口：加工完成（去 0，速率 2）、故障（去 2，速率 0.5），逗留时间 $\mathrm{EXP}(2.5)$ 。

Q=\begin{pmatrix}-4&4&0\\2&-2.5&0.5\\0&1&-1\end{pmatrix}.

速率平衡：

\text{状态 0：}\ 4\pi_0=2\pi_1,\qquad \text{状态 2：}\ 1\cdot\pi_2=0.5\pi_1,\qquad \pi_0+\pi_1+\pi_2=1 .

由前两式 $\pi_0=\pi_1/2$ ， $\pi_2=\pi_1/2$ ，于是 $\pi_1=1/2$ ，** $\pi=(1/4,\ 1/2,\ 1/4)$ **。

解读：机器 25% 的时间在准备，50% 在加工，25% 在维修。生产率 = 处于加工状态的概率 × 加工完成速率 $=\pi_1p=0.5\times2=1$ 个/小时。

一般公式： $\pi_0=\dfrac{pr}{pr+rs+fs}$ ， $\pi_1=\dfrac{rs}{pr+rs+fs}$ ， $\pi_2=\dfrac{fs}{pr+rs+fs}$ 。

丢弃策略：故障后正在加工的零件作废，修好后重新准备（从状态 2 回到状态 0）。 $Q$ 的第三行变为 $(1,0,-1)$ 。速率平衡：

\text{状态 1：}\ 2.5\pi_1=4\pi_0,\qquad \text{状态 2：}\ \pi_2=0.5\pi_1,\qquad \sum\pi=1 .

$\pi_0=\frac58\pi_1$ ， $\pi_2=\frac12\pi_1$ ， $\pi_1(1+\frac58+\frac12)=1$ ， $\pi_1=8/17$ 。** $\pi=(5/17,\ 8/17,\ 4/17)$ **，生产率 $\frac{8}{17}\times2=\frac{16}{17}\approx0.94$ 个/小时，比续做策略低 6%。

生产率的另一种算法

也可以用“流出加工状态并且是完成”的速率：在续做策略下，状态 1 → 0 的流量 $\pi_1\cdot p=1$ 。总是用“处于该状态的概率 × 对应事件的速率”。

9. 生灭过程

状态 $0,1,2,\dots$ ，只能跳到相邻状态： $k\to k+1$ 速率 $\lambda_k$ （出生）， $k\to k-1$ 速率 $\mu_k$ （死亡）。在 $k-1$ 与 $k$ 之间“切一刀”，上行流量等于下行流量：

\lambda_{k-1}\pi_{k-1}=\mu_k\pi_k\quad\Rightarrow\quad \pi_k=\pi_0\prod_{i=1}^{k}\frac{\lambda_{i-1}}{\mu_i},\qquad \pi_0=\Big(1+\sum_{k\ge1}\prod_{i=1}^{k}\frac{\lambda_{i-1}}{\mu_i}\Big)^{-1}.

例4： 一个窗口，加上排队最多容纳 2 人（满了的人直接离开）。到达速率 2/小时，服务速率 3/小时。状态 = 系统内人数 $\{0,1,2\}$ ：

\pi_1=\tfrac23\pi_0,\qquad \pi_2=\big(\tfrac23\big)^2\pi_0,\qquad \pi_0\big(1+\tfrac23+\tfrac49\big)=1\ \Rightarrow\ \pi=\big(\tfrac{9}{19},\ \tfrac{6}{19},\ \tfrac{4}{19}\big).

有 $4/19\approx21\%$ 的时间系统是满的，此时到达的人会流失。这就是第9章 M/M/1/N 排队的特例。

10. 小结

	DTMC	CTMC
描述	转移概率矩阵 $P$ ，行和 = 1	转移速率矩阵 $Q$ ，行和 = 0
逗留时间	几何，均值 $1/(1-p_{ii})$	指数，均值 $1/\nu_i=-1/q_{ii}$
多步/有限时间	$P(n)=P^n$ ， $\pi(n)=\pi(0)P^n$	$H(t)=e^{Qt}$ ， $\pi(t)=\pi(0)e^{Qt}$
稳态	$Y=YP$ ， $\sum y_j=1$	$\pi Q=0$ ， $\sum\pi_j=1$ （速率平衡）

自测

1. 求 $P=\begin{pmatrix}0.6&0.2&0.2\\0.1&0.8&0.1\\0.6&0&0.4\end{pmatrix}$ 的稳态概率。

$Y=YP$ ： $y_0=0.6y_0+0.1y_1+0.6y_2$ ， $y_1=0.2y_0+0.8y_1$ ， $y_2=0.2y_0+0.1y_1+0.4y_2$ 。第二式给 $y_1=y_0$ 。第三式： $0.6y_2=0.2y_0+0.1y_0=0.3y_0$ ， $y_2=0.5y_0$ 。归一化 $y_0(1+1+0.5)=1$ ， $Y=(0.4,\ 0.4,\ 0.2)$ 。

2. 化妆师的工作：出发去客户家（速率 2）→ 化妆（速率 3）；化妆中眼线可能花掉（速率 0.5），需要重画（速率 1），重画后继续化妆。求稳态概率和平均每小时完成的单数。

状态 0 路上、1 化妆、2 重画。 $Q=\begin{pmatrix}-2&2&0\\3&-3.5&0.5\\0&1&-1\end{pmatrix}$ 。速率平衡： $2\pi_0=3\pi_1$ ， $\pi_2=0.5\pi_1$ 。 $\pi_1(\frac32+1+\frac12)=1$ ， $\pi_1=\frac13$ ， $\pi=(\frac12,\ \frac13,\ \frac16)$ 。完成速率 $\pi_1\times3=1$ 单/小时。

3. 例3中，如果补货规则改为“剩余为 0 才补到 3 件”，状态空间和 TPM 的哪些行会变？

状态空间仍是 $\{0,1,2,3\}$ 。状态 1 的下一天不再补货而是从 1 件开始：剩 1 件 $e^{-1}$ ，剩 0 件 $1-e^{-1}$ ，其余为 0。所以只有第 1 行变成 $(1-e^{-1},\ e^{-1},\ 0,\ 0)$ ；第 0、3 行（从 3 件开始）和第 2 行（从 2 件开始）不变。