文章/答案/技术大牛

发布

社区首页 >专栏 >随机过程（9）——连续时间马尔科夫链的泊松过程描述，爆炸现象，离散马尔科夫链对比

随机过程（9）——连续时间马尔科夫链的泊松过程描述，爆炸现象，离散马尔科夫链对比

学弱猹

发布于 2021-08-10 03:33:01

2.3K0

文章被收录于专栏：学弱猹的精品小屋学弱猹的精品小屋

上一节笔记：随机过程（8）——更新过程在排队论的两个应用，PASTA，连续时间马尔科夫链引入

————————————————————————————————————

大家好！告别2020年之后，希望2021年大家能够顺心顺意，似乎暴露了文章写作的时间哦……

这一节我们会继续介绍连续时间马尔科夫链，包括它的一些比较形象化的描述，它的极限性质等，就和我们之前讨论离散状态马尔科夫链一样。事实上到后面我们也会继续接触各式各样的排队论模型，连续时间马尔科夫链在排队论中的应用同样十分广泛。

那么我们开始吧。

连续时间马尔科夫链的转移速率应用

首先声明一下，这里的转移速率（transition rate）的概念，其实就是上一节所提到的跳跃速率（jump rate），很多时候两个概念会混着用。

在上一节的最后我们给大家展示了转移速率和C-K方程的联系，合理利用它们俩可以帮助我们求解连续时间马尔科夫链的转移概率矩阵。考虑到马尔科夫链中，转移概率矩阵是一个核心工具，因此在连续时间马尔科夫链中，刻画出转移速率矩阵就成为了一个很重要的任务。这一部分我们就简单的举两个例子，给大家加深一些印象。

Problem 1: 考虑一个速率为

λ

$\lambda$

的泊松过程，证明

q (n, n + 1) = λ, \forall n \geq 0

$q(n, n + 1) = \lambda, \forall n \ge 0$

。

这个其实就是上一节的例子（Problem 3）。这里就不多费笔墨去说这一件事了。

Problem 2: 考虑排队论中的

M / M / s

$M/M/s$

模型，也即顾客到达服从一个速率为

λ

$\lambda$

的泊松过程，而服务时间服从一个速率为

μ

$\mu$

的泊松过程，二者相互独立。一共有

s

$s$

个服务器，那么在这个场景下，刻画整个系统中的人数，其对应的转移速率为

q (n, n + 1) = λ

$q(n, n + 1) = \lambda$

，

$q(n, n - 1) = \begin{cases} n\mu & 0 < n \le s \\ s \mu & n \ge s\end{cases}$

。

如果到达的速率服从泊松过程的话，

$q(n, n+ 1) = \lambda$

其实就是Problem 1的复用，没有太多需要强调的地方。但是

$q(n, n -1)$

对应的是什么情况呢？自然就是系统中有人离开的情况了。在这个时候，我们将系统中的人数分情况做讨论，就可以看出一些端倪。

首先如果

$0 < n \le s$

，事实上对应的是服务器未满载的情况。那么这个时候，可以想像

$s$

个服务器中，只有

$n$

个在服务，那么“离开”这一件事情要等待的时间，其实就是所有的正在服务的人，要等待的最小值。如果说每一个的时间是

$t_i$

的话，那么这个“离开”发生所需要的等待时间就是

$\min(t_1, \ldots, t_n)$

，自然也是服从一个指数分布（这个是一个概率论的结论，后面单独说）。而这个指数分布的参数对应的就是

$n \mu$

。那么既然等待时间是指数分布，整个过程就是一个泊松过程，所以复用一下Problem 1的结论就可以了。

同样的思路，如果

$n \ge s$

，那么服务器满载，所以

$s$

个都会服务，那么对应的参数就是

$s \mu$

。

最后我们来说一下这个指数分布的概率论中的结论。

Lemma 1: 若

$X_1, \ldots, X_n \sim \exp(\lambda)$

，那么

$\min(X_1, \ldots, X_n) \sim exp(n \lambda)$

。

这可以直接利用分布函数来推得，是概率论的内容。如果这个不会的话，可能就需要回去复习一下概率论中的最小值分布了。

转移速率的形象化描述

因为脱去了“步数”这么一个具体的概念，所以很多时候会导致连续时间马尔科夫链不是特别好想。这里我们提供了三个常见的对于转移速率的形象化描述。

首先来看第一种描述。

Description 1: 考虑平面上的点，那么假如说一开始，一个跳蚤在点

$i$

，对每一个

$j \ne i$

，假设经过

$\exp(q(i, j))$

的时间，跳蚤就会跳到点

$j$

。但跳蚤最终跳到哪里，取决于到哪儿所需要的时间最短，那么可以说明的是，跳蚤所在的点对应的转移概率

$p_h(i, j)$

满足

$q(i,j) = \lim_{h \to 0} \frac{p_h(i, j)}h$

。

画一张图来表示一下这个过程。

第一次，因为跳到

$j$

要等的时间更短，所以就先跳到了

$j$

。

对这个问题如何建模呢？其实我们只需要关心怎么求

$p_h(i, j)$

。这里就涉及到跳跃的统计问题。诚然，从

$i$

到

$j$

的跳跃会有很多种可能，因此我们先考虑一步到

$j$

的可能性。那么这样的话，实质上可以建模为

$P(t_j < h, t_k > h, k \ne j)$

这表示在

$(0, h)$

的时间内，到达

$j$

所需要等待的时间最短，其它的等待时间都不在

$h$

以内。

那么自然的，对它求极限和除法，就会有

$\lim_{h \to 0}\frac{P(t_j < h, t_k >h, k \ne j)}{h} = \lim_{h \to 0} \frac{1 - e^{-q(i, j)h}}{h}\prod_{k \ne j}e^{-q(i, k)h} \to q(i, j)$

那么两步及以上的情况呢？这里要说明的是它本身是一个

$h$

的高阶小量，细节上不太好说，这里提供一个思考视角。注意到两步其实就是“一步又一步”的含义。前后的独立性带来的概率的乘积，会将两个

$h$

的线性项乘起来，这就变成二阶，也就是高阶无穷小了。

因此我们可以看出，这个描述的其实就是一个转移速率矩阵为

$Q$

的连续时间马尔科夫链。

Description 2: 考虑一个跳蚤一开始在点

$i$

，那么从其离开

$i$

需要等待

$\exp(\lambda_i)$

的时间，其中

$\lambda_i = \sum_{j \ne i}q(i, j) \in (0 , \infty)$

。其跳到

$j$

的概率为

$r(i,j) = \frac{q(i, j)}{\lambda_i}$

。此描述对应的随机过程与Description 1相同。

如果说它和Description 1相同，其实一开始不容易让人信服，毕竟，第一个可以看出，跳跃到具体哪一个点是受所有的点制约的。但是这一个似乎就把这个”相互关系“给剥离掉了。这是什么情况呢？事实上这也是一个概率论的性质，这个性质要说明起来还是有点难度，我们仔细看一下。

Lemma 2: Exponential Race 设

$T_i \sim \exp(\lambda_i)$

，相互独立。

$V = \min\{T_1, \ldots, T_n\}, I = \{i: T_i = V\}$

，那么有

$V \sim \exp(\sum_{k = 1}^n \lambda_k), P(I=i) = \frac{\lambda_i}{\sum_{k = 1}^n \lambda_k}$

，并且

$I, V$

相互独立。

这里相对有些反人类的地方就是

$I, V$

相互独立，简单来说，“第一个到达的点的时间”和“第一个到达的点是谁”没有联系。这在这两个随机变量都和

$\lambda_i$

有关的情况下就显得更加的反直觉了。

要说明这一点，其实也就是概率论的定义。注意到

$f_{I, V}(i, t) = P(I = i, V = t) = P(T_i = t, T_k >t, k \ne i)$

$=P(T_i = t)\prod_{k\ne i} P(T_k >t) = \lambda_i e^{-\lambda_i t}\prod_{k \ne i}e^{-\lambda_k t} = (\frac{\lambda_i}{\sum_{k = 1}^n \lambda_k})(\sum_{k = 1}^n \lambda_k)e^{-(\sum \lambda_k)t}$

$= P(I=i) P(V = t)$

注意到分离变量，这就完成了证明。

这个命题可以说明的一点是，用Description 2来描述这个过程，和用Description 1来描述是一模一样的。这只是同一个结论用了两段不同的话语去说而已。

事实上，还有一个Description 3，可以理解为它是Description 2的一个标准化。

Description 3: 考虑一个跳蚤一开始在点

$i$

，那么从其离开

$i$

需要等待

$\exp(\Lambda)$

的时间，其中

$\Lambda = \sup_i \lambda_i$

，并且

$\lambda_i = \sum_{j \ne i}q(i, j) \in (0 , \infty)$

与之前的定义一样。其跳到

$j$

的概率为

$u(i,j) = \frac{q(i, j)}{\Lambda}, i \ne j$

。并且

$u(i, i) = 1 - \frac{\lambda_i}{\Lambda}$

。此描述对应的随机过程与Description 1相同。

一般来说，我们会把它称为是Description 2的一个“归一化”。直观来看，相当于我们把所有的

$\lambda_i$

都统一了起来，统一为一个“离开时间”（但是注意，这个时候是有可能这个点不会离开的，因此叫离开时间可能并不准确）。

至于为什么说这个描述也是正确的，就需要参考上一节的Problem 2。在Problem 2我们描述了一个随机过程

$Y_{N(t)}$

。其中

$N(t)$

就是一个泊松过程，而

$Y_n$

是一个离散马尔科夫链，转移概率为

$u(i, j)$

。

在上一节的Problem 2-2，我们也给出了这个随机过程的转移概率

$p_t(i, j)$

。事实上，如果我们把这些数据代入公式计算，会发现转移速率矩阵和Description 1是相同的，因此它确实是一个合理的描述连续时间马尔科夫链的方案。至于这个验证过程，我们就交给读者了。

Description 3还有一个优势在随机模拟上。在计算统计中经常会出现需要模拟一条随机过程的情况（比方说MCMC），而这个方案相对来说是最好实现的。

最后总结一下，因为我们相当于把一条连续时间马尔科夫链给建模成了一条泊松过程，所以一切之前与泊松过程有关的性质，结论，都可以应用到这里的连续时间马尔科夫链上。这也是为什么之后介绍它与离散马尔科夫链的联系的时候，我们很多时候可能只会寥寥几笔带过，因为所需要的工具，之前都铺垫的差不多了。

爆炸现象

这里的爆炸（explosion）现象自然不可能是物理中的原子弹爆炸，也不可能是化学中的活泼金属遇水爆炸，而是一种特殊的状态转移现象。即

有限时间内，状态转移发生了无限次。

如果这种现象发生，就说明所有的状态转移，都发生在有限的一段时间内。这在随机模拟中自然是一个不可接受的现象，同样这也不会在离散马尔科夫链中发生，因为在离散情况下根本没有时间的概念。

我们来看一个具有爆炸现象的例子。

Problem 3: Pure Birth 考虑一个生命链，也即

$q(i, i+1) = \lambda i^p$

，其余均为0。并假设从

$1$

开始。那么考虑

$T_n = \sum_{k = 1}^n t_k$

为跳转

$n$

次状态经过的时间，说明如果

$p > 1$

，那么会发生爆炸现象。

直观来看，容易猜出

$p > 1$

应该是一个合理的答案，因为这个时候，可以看出转移速率呈现指数上升的趋势。因此可以想像，到最后，跳转的速度就越来越快，一直到最后可能就会一发不可收拾。

首先是

$p > 1$

的情况，这个时候，我们来考察

$E(T_n)$

，注意到

$E(T_n) = \sum_{k = 1}^n E(t_k) = \sum_{k = 1}^n \frac1{\lambda i^p}$

数分中我们学过，这是一个p-级数。简单来说，

$p > 1$

的时候，这个级数是收敛的。那么高等概率论中有说过

$\lim_{n \to \infty} E(T_n) < \infty \to \lim_{n \to \infty} T_n < \infty \quad a.s.$

简单来说，这个时候就出现了这种“几乎处处”极限时间为有限的情况，这也就是所谓的爆炸现象。

多说几句，如果

$p = 1$

，其实也有一个有意思的事情，就是

$E(T_n) \to \infty$

。但是要注意，这个时候并没有

$T_n \to \infty$

相关的结论。那么这里如果要看

$T_n$

的情况，一个粗略的办法是看它的波动，也就是方差。容易发现

$Var(T_n) \to C < \infty$

是一个有限的数，所以利用切比雪夫（Chebyshev）不等式，我们有

$P(T_n \le \frac {E(T_n)}2) \le \frac {4C}{(E(T_n))^2} \to 0$

那么再根据

$E(T_n) \to \infty$

，说明

$T_n$

比一个无穷要小的概率趋于0，那自然就说明了

$T_n \to \infty \quad a.s.$

。这也说明了，

$p = 1$

的情况下，尽管移动的速率仍然会越来越快，但是因为不会有指数上升的趋势，所以依然可以使用随机模拟来模拟这个过程，不会有爆炸现象的发生。

好的，到此为止，我们就说完了对于连续时间马尔科夫链的基本刻画。在这之后，我们会利用这些性质，来推广一些离散马尔科夫链中已经涉及到的定理等内容。

连续时间马尔科夫链的平稳分布

很自然，这一节对标的就是离散马尔科夫链的对应内容。强调一遍，我们需要多次的与之前的离散马尔科夫链模型进行对比，所以如果对相关术语感到陌生，建议对之前的内容再多阅读阅读

随机过程（1）——引入，有限状态马尔科夫链，状态转移，常返与瞬时状态

随机过程（2）——极限状态的平稳分布与周期（上），一些特殊的马尔科夫链

随机过程（3）——无限状态的平稳测度，返回时间，访问频率：几个定理的证明

随机过程（4）——返回时间，访问频率定理应用，离出分布，离出时间

回顾一下离散马尔科夫链的平稳分布定义，我们要求马尔科夫链是不可约的，非周期的，常返的。在连续时间马尔科夫链中，首先不再有周期的概念，其次其余的概念肯定也不能直接套用。所以这里需要对他们做一个重新的刻画。

Definition 1: Irreducible 对于连续时间马尔科夫链

$\{X_t\}$

而言，如果对任意的

$i, j$

，

$i$

到

$j$

都能在有限步内完成，也即

$\exists i = k_0 < k_1 < \ldots < k_n = j$

，使得

$q(k_{m - 1}, k_m) > 0, 1 \le m \le n$

，那么称其不可约。

如果要说明为什么这个不可约的定义是合理的，只需要说明

$p_t(i, j) > 0, \forall i, j ,t$

即可。这个其实也不是特别困难，和离散马尔科夫链的思考过程类似，考虑一种状态转移的情况，首先将

$q(k_{m-1},k_m) > 0$

转换为

$p_h(k_{m - 1}, k_m) > 0, h \to 0$

，所以我们取一个很小的

$h$

，对区间分拆，就有

$p_t(i, j) = P(X_t = j|X_0 = i) \ge P(X_t = j, X_{mh} = k_m , m = 0, 1, \ldots, n |X_0 = i)$

$=P(X_t = j|X_0 = i, \ldots, X_{mh} = j)P(X_{mh} = j|X_0 = i ,\ldots, X_{(n-1)h} =k_{n - 1}) \cdots P(X_h = k_1 | X_0=i)$

$= p_{t - nh}(j, j)p_h(k_{n - 1}, k_n)\cdots p_n(k_0, k_1) >0$

这个转移的过程相当于说，一开始从

$i$

到

$j$

的这中间经过的各个步骤，每一步都经过了时间

$h$

，然后到了最后的

$j$

的时候停留了一段时间（时间

$> t- nh$

）。那么注意到

$p_{t-nh}(j, j) > 0$

（这是因为等待这个过程本身是一个泊松过程，所以这个概率就是一个指数分布的概率），所以自然的根据条件就可以得到这个结论。

这个区间分拆大概可以用图表示为这么一个意思。

下面我们来给定平稳分布的定义。

Definition 2: Stationary Distribution 如果满足

$\pi Q = 0$

，那么称

$\pi$

是一个平稳分布。

自然地，我们也希望了解为什么

$\pi Q = 0$

可以对应上离散马尔科夫链的平稳分布的定义。回顾一下，之前我们说过

$\pi P = \pi$

是一个条件，那么两边求导就会有

$\pi P' = 0$

。这是一个思路，总结一下就是

$\pi Q p_t = \frac {\mathrm d} {\mathrm dt}(\pi p_t) = 0$

因为我们之前有提过

$Qp_t = \frac {\mathrm d}{\mathrm d t}p_t$

，当然这是需要假设

$p_0 = I$

的情况下。

这是一个引发我们思考的思路，但很显然不是证明，因为还差另外一个方向。如果

$\pi Q = 0$

，那么能不能推导出

$\pi p_t = \pi$

这样的结论呢？其实也是可以的，因为我们有

$\frac {\mathrm d}{\mathrm d t}(\pi p_t) = \pi \frac{\mathrm d}{\mathrm d t}p_t = \pi Q p_t = 0$

那么这就说明了

$\pi p_t = \pi p_0 = \pi$

，因为

$p_0 = I$

。所以可以看出，两个方向的证明其实都利用了上一节提到的Kolmogorov方程。

现在我们再回头看一下

$\pi Q = 0$

所想表达的意思。其实利用矩阵乘法，也不难发现它就是这么一个意思

$\sum_{k \ne j}\pi_k q(k, j) = \lambda_j \pi_j = \sum_{k \ne j}\pi_j q(j ,k)$

当然第二个等号是因为我们之前有定义

$\lambda_j = \sum_{k \ne j} q(j, k)$

，同样是在上一节我们定义跳跃速率的时候做的人工补充。

抽象一下，

$\sum_{k \ne j}\pi_k q(k, j)$

就是从

$k$

出发，到其它各点的“加权速率和”，而

$\sum_{k \ne j}\pi_j q(j ,k)$

就是除

$k$

以外的点到达

$k$

的“加权速率和”。因此这里的“平稳”，就是“到达的速率”和“出去的速率”相同的意思。当然这个话术其实我们在离散马尔科夫链中就已经用过了，当时是使用转移概率矩阵来描述的。

一个比较好的对比技巧是，将这里的

$Q$

和之前的

$P - I$

联系起来，比方说离散情况，其实平稳分布的定义就是

$\pi (P - I) = 0$

，这就可以和这里的公式对应上。

有了平稳分布之后，自然也可以很好的定义细致平衡条件（detailed balanced condition）和逆马尔科夫链（reversed Markov chain）。

Definition 3: Detailed Balanced Condition 如果

$\pi(k) q(k ,j) = \pi(j) q(j, k)$

，那么称分布满足细致平衡条件。

类似的，满足细致平衡条件的分布肯定也是平稳分布，但是反过来不一定。这也是从离散马尔科夫链直接推导过来的结论。

Definition 4: Reversed Chain 定义

$Y_t = X_{T - t}, 0 \le t \le T$

是原连续时间马尔科夫链的逆马尔科夫链。其中

$X_t$

从平稳分布出发。

这里的

$T$

其实是可以趋于无穷大的，因此这个定义并不代表这个随机变量只定义在区间

$[0, T]$

上。

对于它的转移速率相关的性质，也是和离散情况非常类似的。

Proposition 1 逆马尔科夫链的转移速率满足

$\hat q (i, j) = \frac{\pi(j) q(j, i)}{\pi(i)}$

。

可以看出，与离散的情况基本上相同。

要说明

$\hat q (i, j)$

是合理的，其实只需要说明

$\hat p_t (i, j) = \frac{\pi(j) p_t(j, i)}{\pi(i)}$

和离散情况一模一样的推导方式，我们直接可以得到

$\hat p_t (i, j) = P(Y_t = j| Y_0 = i) = P(X_{T - t} = j |X_T = i)$

$= \frac{P(X_T = i|X_{T - t} = j) P(X_{T - t} = j)}{P(X_T = i)} = \frac{p_t(i, j) \pi(j)}{\pi(i)}$

这里就不多解释了。

同样的，如果

$\pi$

服从细致平衡条件，那么会有

$\hat q(i,j ) = q(i, j)$

。

最后也是类比于离散情况，我们可以得到下面这样的结论。

Theorem 1: 设

$X_t$

是一条连续时间马尔科夫链，不可约，且存在平稳分布

$\pi$

，那么有

$\lim_{t \to \infty} p_t(i, j) = \pi(j)$

。

我们就不证明这个结论了。

Theorem 2: 在连续时间马尔科夫链中，有

$\lim_{t \to \infty} \frac 1t \int_0^t I(X_s= j) ds = \frac 1 {\lambda_j E_j T_j}$

$\pi(j) = \lim_{t \to \infty} \frac 1t E(\int_0^t I(X_s = j) ds) = \frac 1 {\lambda_j E_j T_j}$

同样，它们也是和离散时间马尔科夫链相对应的结论。细微的差别便在

$\lambda_j$

这个系数上。

要说明这个结论，我们可以使用更新过程的方法，这是因为我们之前说过，

$X_t$

可以理解为是一个泊松过程，我们画一张图解释一下。

这里两个

$j$

之间的内容都是其他状态。简单来说，定义这里的奖赏

$r_1$

为“等待离开

$j$

的时间”。

因为连续时间马尔科夫链可以用泊松过程描述（Description 2），所以这里我们使用更新奖赏过程来进行证明，也就是说定义

$r_i$

为停留在状态

$j$

的时间，定义

$t_i$

为从一个

$j$

到下一个

$j$

所需要的时间，这样的话直接就会有

$\lim_{t \to \infty} \frac 1t \int_0^t I(X_s= j) ds = \frac{E(r_i)}{E(t_i)} = \frac{\frac 1 \lambda }{E_j T_j }$

这就完成了证明。

对于第二个式子，可能情况稍微复杂一些。注意到

$\lim_{t \to \infty} \frac 1t E(\int_0^t I(X_s = j) ds) = \lim_{t \to \infty} \frac 1t \int_0^t P(X_s = j) ds$

这其实就是一个期望和积分的交换顺序。有了这个之后，其实只需要注意到，因为我们的

$t \to \infty$

，所以极限状态下，会有

$P(X_s = j) \to \pi(j)$

。比较类似数分里，有限的部分带来的影响可以忽略不计一样。这里也是因为这个可以得到这个极限为

$\pi(j)$

。当然了至于为什么同样可以得到

$\frac 1 {\lambda_j E_j T_j}$

，其实还是更新奖赏过程的理论，可以参考第7节

随机过程（7）——更新奖赏过程：交替更新过程，生存与濒死时间，观察悖论

好的，我们来看几个例子吧。

Problem 4:

$M/M/s$

Queue with Balking 考虑一个排队论模型，理发店有

$s$

个理发师，顾客到来时间服从一个速率为

$\lambda$

的泊松分布，而对于每一个顾客而言，有

$a_n$

的概率加入这个队伍，这里的

$n$

是在系统中的人数，不包括他自己。服务时间服从一个速率为

$\mu$

的泊松分布。刻画这个系统的平稳分布。

事实上有了连续时间马尔科夫链的工具，我们可以用它来解决一些排队论的问题，因为它也可以被理解为是一种泊松过程。

不难得到我们可以刻画出这样的转移速率矩阵。

$q(n, n + 1) = \lambda a_n$

$q(n, n - 1) = \begin{cases}n \mu & 0 < n \le s \\ s \mu & n > s\end{cases}$

这里要注意

$q(n ,n + 1) = \lambda a_n$

是怎么来的，速率为

$\lambda$

加上“加入概率为

$a_n$

"，所以对应了一条速率为

$\lambda a_n$

的泊松过程。这一个对应泊松过程的稀疏变换，可以参考这一节

随机过程（6）——泊松过程三大变换，更新过程引入

这个转移速率其实可以利用细致平衡条件来求解，不难得到

$\pi(n + 1) = \begin{cases} \frac{a_n \lambda}{s \mu} \pi(n) & n \ge s \\ \frac{a_n \lambda}{(n + 1) \mu} & n < s \end{cases}$

当然要刻画它的平稳分布，在这个无限状态的情况下，我们就自然希望知道

$\sum_n \pi(n)$

是否是一个有限数，因为这决定了平稳分布的存在性和值。

虽然没办法再给出更细节的刻画，但有一个比较好分析的case就是

$a_n \to 0$

。这个情况下根据级数的比值判别法，可以看出和是收敛的，也就是平稳分布存在的意思。

Problem 5: 考虑一个天气转移的过程。天气从晴天转为多云的时间服从

$\exp(\frac 13)$

，从多云转为雨天的时间服从

$\exp(\frac 14)$

，从雨天转为晴天服从

$\exp(1)$

。刻画这个连续时间马尔科夫链的转移速率矩阵

$Q$

，并得出长期来看，各个天气占据时间的比例。

这个

$Q$

不难得到，假如说晴天状态是1，多云状态是2，雨天状态是3，那么有

$Q = \begin{bmatrix}-\frac 13 & \frac 13 & 0 \\ 0 & -\frac 14 & \frac 14 \\ 1 & 0 & -1\end{bmatrix}$

状态则是按照

$[1, 2, 3]$

的顺序从左到右，从上到下排序的。比方说

$q(1, 2) = \frac 13$

表示从状态1到状态2，转移速率为

$\frac 13$

，这对应一个

$\exp(\frac 13)$

的指数分布。

那么这样的话，求解

$\pi Q = 0$

，可以得到

$\pi = (\frac 38, \frac 48, \frac 1 8)$

注意这里不能使用细致平衡条件。

因此可以得到，晴天，多云和雨天的时间占比为

$3: 4: 1$

。感兴趣的读者可以使用更新奖赏过程中，交替更新过程的方法进行建模，利用指数分布的无记忆性，可以发现这个时候，结果是一致的。

Problem 6: 考虑一个理发店排队论模型

$M/ M / 1$

，理发店理发服从一个速率为

$3$

的泊松过程（平均每一个小时完成3个人），顾客到达服从一个速率为

$2$

的泊松过程。但如果顾客前面已经有2个人排队，则顾客会离开。刻画这个模型，并求解出进入系统的人中，长期来看平均在系统停留的时间。

那么我们可以看出这个时候，定义状态

$n$

表示系统里有

$n$

个人的话，就不难得到

$q(i, i - 1) = 3, i = 1, 2, 3$

$q(i, i + 1) = 2, i = 0 , 1 ,2$

当然这个没有考虑人离开的情况，具体怎么加上这个条件会在后面说。当然因为这个我们可以知道，队伍里最多只会有3个人。

这个转移速率知道之后，再补上对角线上的

$-\lambda_i$

，我们就可以求解

$\pi Q = 0$

，得到

$\pi = (\frac{27}{65}, \frac {18}{65}, \frac{12}{65}, \frac{8}{65})$

注意在这里可以使用细致平衡条件。具体什么时候可以使用什么时候不可以使用，在之前的离散马尔科夫链的部分我们提过一个小的方法，不熟悉的读者可以回去翻一下。

https://zhuanlan.zhihu.com/p/335796325

而这个就对应“系统里有

$n$

个人“占据的时间比。比方说从这个结论中，我们可以看出“系统里有3个人”占据的时间比为

$\frac 8 {65}$

。

前方一个小高能。注意到上一节的PASTA性质，系统里有3个人所占据的时间和“某个人到达之后系统里有3个人所占据的比例”是相同的。因此相当于说，这里有

$\frac 8 {65}$

的人会离开系统，不接受服务（加入他们的时候系统里有3个人，相当于没到的时候系统有2个人，符合离开的条件）。也就是说，这里的排队论模型是有阻拦的（balking），对应的是

$\lambda_a = \frac {57}{65} \lambda < \lambda$

。

去掉这一部分人之后，剩下的人都接受了服务，那么直接求期望可以得到

$t = 20 \times \frac {27}{57} + 40 \times \frac {18}{57} + 60 \times \frac {12}{57} = \frac{660}{19} = 34.74$

这里的单位是min。

这里

$\frac {27} { 57}$

对应的是“看到系统里没有人”的情况，所以相当于这一段时间，有一个人接受服务，那么因为平均一个小时服务3人，所以这一段时间，这一部分人在系统停留的平均时间就是20min。

好的，关于连续时间马尔科夫链的例子，我们就说到这里。这一节我们提了很多例子，也是希望可以通过例子，将连续时间马尔科夫链的理论，性质，与其对应的实际的应用可以相关联起来。

小结

本节主要介绍了连续时间马尔科夫链的转移速率的描述和对应的泊松过程的形象化描述。虽然说是“形象化描述”，但却是我们最为常用的理解和分析连续时间马尔科夫链问题的工具。同时这一节我们也介绍了大量与离散马尔科夫链的对比性质，因此如果对离散马尔科夫链的结论感到陌生，这一节的阅读就会产生较大的困难。不过这也是这一部分内容的常态了。

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2021-01-12，如有侵权请联系 cloudcommunity@tencent.com 删除

definition