随机过程（A）——连续时间马尔科夫链的离出分布，到达时间。排队论模型与排队网络举例

学弱猹

发布于 2021-08-10 11:33:16

1.3K0

发布于 2021-08-10 11:33:16

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

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

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

大家好！相信大家都习惯了，A就是10的意思。

上一节我们介绍了连续时间马尔科夫链的一些极限性质，包括它的描述，平稳分布等。在连续时间马尔科夫链中，这些概念都与离散马尔科夫链有些许不同。这一节我们会介绍连续时间马尔科夫链的离出分布和到达时间，对应的是离散马尔科夫链的相关内容。如果有空的话，还会介绍更多的排队论的例子，这些例子的建模都会严重依赖连续时间马尔科夫链的内容。

那么我们开始吧。

离出分布和到达时间

离出分布（Exit Distribution）和到达时间（Hitting Time）就对应离散马尔科夫链的离出分布和离出时间，在名词上稍微有些差别。离散马尔科夫链的部分可以看下面这一篇来找到，我们在这里会频繁的与离散的情况进行对比。

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

在方法论上，其实核心还是之前提到的“一步转移”。而在连续时间马尔科夫链中，这个“一步”其实就是“这个状态跳到下一个状态所需要的时间“。

还是一样，我们看一个例子。通过例子来说明具体的求解方法。

Problem 1: 考虑一个

M/M/1

模型，其满足

q(i, i+ 1) = \lambda, i \ge 0

，

q(i, i - 1) = \mu, i \ge 1

，求解

P_i(V_N < V_0)

这里的

V_i

表示第一次到达

的时间，

P_i

就表示从

出发。当然这个第一次到达，以及第一次返回的定义，其实和离散情况不太一样。我们把它们的定义补充在下面。

Definition 1: First Visit, First Return Time 定义

V_k = \inf \{t \ge 0: X_t = k\}

是第一次到达状态

的时间。定义

T_k = \inf \{t \ge 0: X_t = k, X_s \ne k, \exists s < t\}

为第一次返回

的时间。

T_k

和

V_k

的区别就在于，如果我们是从

出发的，那么

T_k

就是真正的“下一次返回

的时间“，而

V_k = 0

。

好的，回到这个题目，看看怎么利用一步转移。理解一步转移，其实就是要理解

P_i(V_N < V_0)

到底是什么含义。注意到

P_i(V_N < V_0 )= \sum_k P_i(V_N < V_0 | X_T = k)P_i(X_T = k)

= \sum_k P_k(V_N < V_0) \frac{q(i, k)}{\lambda_i}

这里

T = \inf \{t \ge 0, X_t \ne i\}

，也即第一次跳出

的时间，

\lambda_i

就是一行的转移速率矩阵的总和，也是上一节提到的概念。

P_k(V_N < V_0)

就是一样的式子，不必多说。但是另外一个呢？注意看含义，

P_i(X_T = k)

就是从

出发，第一次离开到达

的概率。根据上一节提到的Description 2，我们自然有

P_i(X_T = k) = \frac{q(i, k)}{\lambda_i}

。

有了这个之后，我们再看这个题应该怎么理解。事实上，根据一步转移，我们可以得到

h(i) = \frac{ \mu}{\mu + \lambda} h(i - 1) + \frac \lambda {\lambda + \mu}h(i + 1), 0 < i <N

同时根据定义其实可以得到

h(0) = 0, h(N) = 1

，所以求解起来也不困难，求解的过程就交给读者了。

所以其实可以看出，对离出分布相关的问题，连续和离散情况是没有区别的。

说完离出分布，我们来看看到达时间相关的问题。这同样可以通过排队论模型来展开。

Problem 2: 考虑一个

M/M/1

模型，转移速率为

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

，

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

。求解

E_1(T_0)

。

回顾一下，

E_1(T_0)

就是从状态

出发，回到

所需要的平均时间。

和离散马尔科夫链的离出时间类似，我们也可以先看看怎么推导在这里的情况。注意到

E_i (V_0) = \sum_k E_i(V_0 | X_T = k) P_i(X_T = k)

这里

T = \inf\{t: X_t \ne i\}

表示第一次离开状态

的时间。剩下的过程其实和上面很像，但是对于

E_i(V_0|X_T = k)

的处理和离出分布略有区别。比方说在这里，我们实质上有

E_1(V_0) = \frac 35 (E_0(V_0) + E(T)) + \frac 25 (E_2(V_0) +E(T))

= E(T) + \frac 35 E_0(V_0) + \frac 2 5 E_2(V_0)

再强调一遍注意

V_i

和

T_i

的区别，虽然在这里，

E_1(T_0) = E_1(V_0)

。

因此在这里，如果我们设

g(i) = E_i(V_0)

，那么很明显

g(0) = 0

，并且我们很自然的可以得到下面的这一组方程。

\begin{cases} g(1) = \frac 15 + \frac 2 5 g(2) \\ g(2) = \frac 15 + \frac 2 5 g(3) + \frac 3 5 g(1) \\g(3) = \frac 13 + g(2)\end{cases}

看到这儿肯定会有人懵逼了，首先一开头的数是怎么得到的？其次为什么每一个项对应的数还不一样？首先很明显，一开始的常数肯定对应的是

E(T)

这个数。那么注意

E(T)

的含义，表示第一次离开某个状态的时间。那么注意，在不同的状态下，离开对应的速率是不同的。在状态

1, 2

下，可以减少1，也可以增加1，一边的速率是3，一边的速率是2，加在一起就是5，对应的均值就是

\frac 15

。

难以理解？画一张图看一看就明白了，本质上就是一个最小值分布的问题。

那么这就可以理解为什么状态

那个均值为

\frac 13

了，因为它只能前往一个方向（状态变成2）。

理解这个之后，直接求解就可以了，这里可以算出

g(1) = E_1(V_0) = \frac {19}{27}

。

虽然这个地方的计算的数和离散情况不太一样，但是本质上都是一样的，在离散情况下我们没有时间的概念，所以每一次移动都认为是“移动一步”。但这里因为有了时间的概念，所以**”移动一步“就变成了”移动所需要等待时间的期望“**。

再来看一个题吧，这个题的做法又和上一个有所不同。

Problem 3: 考虑一个

M/ M/ 1

模型，其中

q(i, i + 1) = \lambda, i \ge 0

，

q(i, i - 1) = \mu, i \ge 1

，求解

E_1 (T_0)

，其中

\lambda < \mu

。

这个题和Problem 2的细微差别就在于，这个题对应的模型状态是可数无限的。所以实质上对应的是无限状态的离散马尔科夫链，这个的相关内容可以参考这一节笔记。

随机过程（5）——无限状态马尔科夫链的进一步探讨，泊松分布引入，复合泊松分布

对于这个题，为什么说做法略有不同呢？不妨先列出公式看看，设

g(i) = E_i(V_0)

，那么

g(0) = 0

，并且我们有

g(i) = \frac 1 {\lambda + \mu} + \frac \mu{\lambda + \mu} g(i - 1) + \frac \lambda { \lambda + \mu}g(i + 1), i \ne 0

有没有发现什么问题？这里要注意，每多写一个方程，就会多一个未知数，因此如果只有这一系列的方程，是无法求解的。因此必须要通过肉眼来观察出其他的结论。

肉眼观察？开什么玩笑？事实上也没有太复杂，我们只需要观察一些简单的情况。这里我们希望求解

E_1(T_0)

，那么不妨看一下

E_1(T_0)

会依赖于什么？注意到

E_1(T_0) = E_1(V_0) = \frac 1 {\lambda + \mu} + \frac \lambda {\lambda + \mu} E_2(V_0)

但是要注意

E_2(V_0)

在这里只有可能走

2 \to 1 \to 0

这一条路，而

2 \to 1

和

1 \to 0

实质上对应同样的转移速率，所以我们有

E_2(V_0) = 2E_1 (V_0)

。这样的话代回，就能得到

E_1(T_0) = \frac {\lambda + \mu}{\mu - \lambda}

。也就是说这个题其实没有必要真正的去求解一系列方程或者做递推。

但事实上一定会有读者感到疑惑，这也是这个题一个非常难理解的地方，为什么一定是

2 \to 1 \to 0

？我不能先走到

，再走到

，再回来？不能反复横跳一会儿？当然可以，但是我们这里的说法并不是一定要从

，下一次跳到

，再下一次跳到

。而是关注，从

到

，必经哪里？所以这一段想表达的意思是，从

一定要经过

再到

，所以可以把

2 \to 0

拆解为两个部分：

2 \to 1

，

1 \to 0

，最终的期望时间就是这两段时间的和。但是

2 \to 1

在本质上和

1 \to 0

是没有区别的，都是“往后退了一步”，有马尔科夫性的保证。因此两段所需要消耗的期望时间是相同的。这一个过程也可以用图来表示如下。

更加复杂的例子：马尔科夫队列举例

马尔科夫队列（Markovian Queue）并不是一个新概念，它对应的就是之前我们讨论的

M/M/s

排队论模型。要单独拉出来说，是因为一方面，它是连续时间马尔科夫链最适合的应用场地。另一方面，其实它还有一些其他的变种，研究起来其实还颇有难度。这一部分我们慢慢来看。

M/M/1

模型的更多性质

之前已经多次提到过这个模型，所以这里我们更多是做一些补充，它对应的就是顾客加入队列的

\lambda

（

\sim \exp(\lambda)

）和服务的速率

\mu

（

\exp(\mu)

），这两个服从指数分布，对应两条独立的泊松过程。通过连续时间马尔科夫链的方法论，看看我们能不能得到更多的信息。

我们在第8节（随机过程（8）——更新过程在排队论的两个应用，PASTA，连续时间马尔科夫链引入）有提到过

M/G/1

模型。因为

M/M/1

模型相当于是

M/G/1

模型的一个子集（记得

是general的意思），所以所有

M/G/1

模型中介绍的性质，在

M/M/1

模型中都是有的。

在之前我们提到过了，一个无其他条件的

M/M/1

模型，如果用连续时间马尔科夫链来刻画，就会对应下面这个转移速率。

\begin{cases}q(n, n + 1) = \lambda & n \ge 0 \\ q(n, n - 1) = \mu & n \ge 1\end{cases}

这里

就是队列里有

个人的意思。

那么根据细致平衡条件，我们有

\pi(n) = (1 - \frac{\lambda}\mu)(\frac \lambda \mu)^n

。这只需要根据

\pi(n) q(n, n + 1) = \pi(n + 1)q(n + 1, n)

来递推得到。在这个无限状态的情况下，也不难得到

\lambda < \mu

才对应平稳分布的存在性。因为在这个时候，服务的速率

\mu

大于队列加入的速率

\lambda

，所以排队不会拥挤，最终队列有几个人是存在一个稳态的。但是可以设想

\lambda > \mu

，对应的就是队列会不断变长的情况，这个时候自然不可能有稳态，因为稳态就是队列不断的有人来，不断变长，最终趋于无限长的情况。

注意到我们在上一节提到过，极限状态下，

\pi(n)

就是队列里有

个人的时间占比。也可以理解为队列里有

个人的概率（对应上一节的Theorem 2）。所以我们在这里可以得到

\pi(0) = 1 - \frac \lambda \mu

，对应的就是“队列空闲的时间占比”。这个和第8节对应的结论一致。

同样的，我们可以利用这个结论，计算队列的平均长度，因为讲白了就是对

这个随机变量求一个期望。注意到

L = \sum_n n \pi(n) = (1 - \frac \lambda \mu ) \sum_n n (\frac \lambda \mu)^{n}

这里有一个trick就是怎么求解

\sum_n n (\frac \lambda \mu)^{n}

。我们设

\frac \lambda \mu = p

，那么有

\sum_n n p^{n} = \frac {\mathrm d \sum_np^{n + 1}}{\mathrm d p} -\sum_n p^n=( \frac p {1 - p})' - \frac 1 { 1- p} = \frac p {(1 - p)^2}

当然这是要

p < 1

才可以的。代回就可以得到这边的结论

L = \frac \lambda {\mu - \lambda}

。可以看出这个结论和第8节说的也是类似的。

还有一个比较关注的结论是平均队列等待时间和平均系统等待时间。还记得区别吗？区别就是队列等待时间是不考虑接受服务的时间的。那么在这里，实际上我们就是要刻画出

T_Q

的概率密度函数，这里的

T_Q

就是我们设的“队列等待时间”对应的随机变量。

对于它的刻画就要更小心一些。不过一个简单的情况是

T_Q = 0

。这个时候很明显对应队列为空的情况（不等待，直接接受服务），所以

P(T_Q = 0) = \pi(0) = 1 - \frac \lambda \mu

但是如果

T_Q > 0

，我们不妨设

T_Q = x > 0

，然后看它和什么因素有关。很明显，这个就和队列的长度有关系。如果队列有

个人，那么指望他们全部清空需要多长时间呢？这相当于等待时间为

\sum_{i = 1}^n T_i

，并且

T_i \sim \exp(\mu)

（相当于服务完，离开队列了），独立同分布。所以如果我们设

T = \sum_{i = 1}^n T_i

，那么

T \sim \Gamma(n, \mu)

。这个也是概率论的结论，可以参考《数理统计》的第1节的Properties 5。

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

那么队列有

个人的概率，其实我们上面说过，就是

\pi(n)

（这个也可以用PASTA性质来解释，理解为顾客到达时，看到

个顾客的时间占比），所以实质上可以得到

f_{T_Q}(x) = \sum_{n = 1}^\infty \pi(n) e^{-\mu x} \frac{\mu^n x^{n - 1}}{(n - 1)!} = \frac \lambda \mu (\mu - \lambda)e^{-(\mu - \lambda )x}, x >0

注意这里的级数求和用到的技巧其实就是

e^x

的Taylor展开式。这个trick在概率论中，求解泊松分布的期望，方差的时候有使用。如果对此感到陌生，说明需要复习概率论了。

密度函数有了，期望，也就是“平均队列等待时间”就好求了。不难得到

E(T_Q) = \frac \lambda \mu \cdot \frac 1 { \mu - \lambda} = \frac \lambda {\mu (\mu - \lambda)}

这个期望如果求不出来，就说明微积分要重新复习了……

平均系统等待时间也不难求，根据之前的公式，就是

E(T) = E(T_Q) + E(s_i) = \frac \lambda {\mu(\mu - \lambda)}+ \frac 1 \mu = \frac 1 {\mu - \lambda}

这个结论和之前也是一致的。

那么最后还有一个“繁忙时间的期望”（

E(B)

）。繁忙时间的比例不难求，就是

1 - \pi(0)

。而繁忙时间的期望，其实对应的就是

E_1(T_0)

。因为"繁忙"的含义，就是从1个人开始，再变成0个人，中间经过的时间。但这个我们在Problem 2里面就已经求解过了，答案就是

\frac 1 {\mu - \lambda}

。

M/M/1

模型的变种：有限等待空间

有限等待空间（Finite Waiting Room）的含义对应的就是上一节的Problem 6。这个题中，顾客看到队列中人数到达一个值，就会直接离开。这也是这一部分会讨论的情况。

在这里，其实对应的转移速率的式子有些不同。我们可以写出

\begin{cases}q(n, n + 1) = \lambda & 0 \le n < N \\ q(n, n - 1) = \mu & 0 < n \le N\end{cases}

这里我们假设，在排队人数到达

的时候，下一个人就会直接离开了。

有了这个之后，其实可以自然的求解出平稳分布，同样是利用细致平衡条件可以得到

\pi(n) = \begin{cases} \frac { 1- \lambda/\mu}{1 - (\lambda / \mu)^{N + 1}}(\frac \lambda \mu)^n & \lambda \ne \mu \\ \frac 1 {N+ 1 } & \lambda = \mu \end{cases},0 \le n \le N

因为在这个例子中，用户存在直接离开的可能，所以

\lambda_a \ne \lambda

（别忘了

\lambda_a

表示真正加入排队的速率，感到陌生的话，可以看第8节补一下背景）。而事实上，在这里，只有

\pi(N)

这种情况下，人才会直接离开，被阻挡。所以对应就有

\lambda_a = \lambda ( 1 - \pi(N))

当然可以通过相同的方式去计算像

L, W_Q, W, E(B)

这样的一些内容。不过这里就不推导具体的式子了。

当然，从这个平稳分布的写法你也可以看出，因为队列长度永远不可能无限长，所以无论

\lambda, \mu

的关系如何，都不会出现平稳分布不存在的情况。

一般的

M/M/s

模型

对于一般的

M/M/s

模型，我们在上一节的Problem 2中已经提到过它的转移速率。这里我们直接写为

q(n, n + 1) = \lambda

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

还是通过细致平衡条件，可以得到

\pi(k) = \begin{cases}\frac c {k !} (\frac \lambda \mu)^k & k \le s \\ \frac c {s! s^{k - s}} (\frac \lambda \mu)^k & k \ge s\end{cases}

当然这里

就是标准化常数，也就是为了保证平稳分布和为1，而存在于分母的常数。

如果你认真的求解一下这个平稳分布的话，会发现这个平稳分布的存在性也是需要条件的，就是

\lambda < s\mu

。这个对应的含义其实和

M/M/1

是一样的，即服务速率大于队列加入的速率。但是这里注意到有多个服务器（理发师），所以服务速率是

s\mu

。反过来，如果

\lambda > s\mu

。那么就和之前一样，队列会变得无穷长，平稳分布也就不复存在了。

可逆性的应用：顾客离开分布

这一部分我们起名为“顾客离开分布”，原因在于研究的不是顾客的到达，而是顾客的离开。事实上，如果达到了稳态，那么我们可以发现一些关于顾客离开速率的有趣的结论，而这些结论通过逆马尔科夫链，可以得到又好理解，又容易的证明方法。

我们先看一下究竟是什么样的结论。

Theorem 1: 如果

s\mu > \lambda

，那么在稳态的情况下，

M/M/s

模型的顾客离开的过程是一个速率为

\lambda

的泊松过程，与原队列的顾客进入的过程独立。

从一个非常general的观点来看。在稳态的时候，进入队列的人数和离开队列的人数应该相同。用这个观点来看，因为进入队列服从一个速率为

\lambda

的指数分布，那么离开肯定也是一样的分布。这个说法肯定是没错的，事实上也是之后逆马尔科夫链这个idea的来源。不过我们还是先看一看，一般的做法是什么。

我们以

s= 1

举例。这是因为

s > 1

的讨论方法类似，但是计算就要复杂很多。

要说明它是一个泊松过程，就要说明等待时间服从一个指数分布。这个需要分情况讨论。因为队列如果有人排队，和没人排队，等待的时间是不同的。注意到如果队列有人排队（繁忙），那么需要等待的时间是

T_1 + T_2

，其中

T_1 \sim \exp(\lambda), T_2 \sim \exp(\mu)

。如果没人排队（空闲），那么需要等待的时间就是一个

\exp(\mu)

。所以这是一个混合分布，求解概率密度的话，怎么做呢？

我们在概率论里说过，两个随机变量和的概率密度需要依赖卷积公式。而繁忙和空闲的比例我们也有提到过，分别是

\frac \lambda \mu

和

1 - \frac \lambda \mu

。所以这里，我们可以把两个情况做一个讨论，就可以得到密度函数。

注意到

f(t) = (1 - \frac \lambda \mu)\int_0^t \lambda e^{-\lambda(t- x) } \mu e^{- \mu x}dx + \frac \lambda \mu \mu e^{-\mu t}

=(1 - \frac \lambda \mu) \frac {\lambda \mu}{\lambda - \mu}(e^{-\mu t} - e ^{-\lambda t}) + \frac \lambda \mu \mu e^{-\mu t} = \lambda e ^{-\lambda t}

而这个就是指数分布的密度函数。所以这就算证明了这个说法的正确性。

这个微积分的计算也是需要一点功夫的，不过为了验证读者的微积分水平，这里就不具体计算了。

但是别忘了，我们这一部分的内容是在说什么？我们是在说可逆性的应用。我们设

Y_t = X_{T - t}

，那么很容易发现，这个时候，其实

Y_t

就是对应的就是离开的过程。也就是说，如果我们设

X(t)

是均衡状态下的

M/M/s

模型，

N(t)

表示在

[0, t]

这一段时间，用户离开的数量，那么甚至可以发现它们俩的独立性。

Proposition 1:

\{N(s): 0 \le s \le t\}

与

X_t

独立。

这是因为，

N(s)

就是对应的

[0, s]

的离开情况，相当于对应到达过程

X(t)

在

[T- s, T]

这一段时间的情况。但是

X_t

其实相当于是在时间点

T - t

用户离开的过程（

Y_{T - t}

），所以可以看出，

N(s)

和

X_t

对应的时间是不交叉的，因此根据泊松过程的性质就可以得到独立性。

不管怎么说，因为我们可以用一个逆马尔科夫链来研究它，而时间上的独立性又存在，因此只需要计算一下逆马尔科夫链的转移速率就可以。而事实上，经过验证可以发现，逆马尔科夫链的转移速率和原始的用户进入的马尔科夫链相同，所以相当于同分布，也就是说离开和进入应该服从一样的连续时间马尔科夫链。这样的话，就可以很方便的解释这个现象。

最后，这一张图直观的描述了这个定理的结论。

排队网络初步

最后一点部分，我们来简单介绍一下简单的排队网络（Queuing Network）问题。排队网络问题在业界的应用还是很多的，常见的运筹学问题也都会有人尝试使用排队网络去做建模。当然因为排队网络本身还是很复杂的一个主题，我们这里只是做一个初步介绍。

Tandem网络

Tandem网络其实就是一种两站网络（two-station network），简单来说就是下面这个意思。

也就是说，到达的速率是

\lambda

，第一个服务站（比方说游乐场）的速率为

\mu_1

，第二个为

\mu_2

。为了均衡，我们额外设

\lambda < \mu_1, \lambda < \mu_2

。

那么对这个例子来说，一个好的方案是分开来看。先来看第一个队列，再来看第二个。这是因为排队进入第一个服务站的人，在离开的时候自然就进入了第二个服务站（这里我们假设这个“离开再进入”的过程不需要时间）。所以这个串联的过程使得一些问题的研究变得方便。

对于第一个队列，很容易得到

P(X_t^1 = m) = (\frac \lambda { \mu_1})^m (1 - \frac \lambda {\mu_1})

X_t^1 = m

表示第一个队列的排队人数为

。这个结果也是先计算平稳分布，再利用上一节的Theorem 2得到的。

同样的，我们有

P(X_t^2 = m) = (\frac \lambda {\mu_2})^n (1 - \frac \lambda {\mu_2})

那么根据

X_t^1, X_t^2

的独立性（Theorem 1，离开和进入独立，而在这里，离开第一个队列相当于进入第二个队列），可以得到

P(X_t^1 = m, X_t^2 = n) = (\frac \lambda {\mu_1})^m(1 - \frac \lambda {\mu_1})(\frac \lambda {\mu_2})^n(1 - \frac \lambda {\mu_2})

这就可以猜测得到

\pi(m, n) = c \frac{\lambda^{m + n}}{\mu_1^m \mu_2^n}

，其中

为与

m, n

无关的标准化常数。

为什么要说是“猜测”呢？是因为我们没有介绍多元的情况下，是否也有类似的和一元一样，平稳分布对应概率/时间占比这样的结论（有没有其实我也不知道……）。同样在这里，如果要验证平稳分布，使用

\pi Q= 0

计算和使用细致平衡条件都是不合理的，一个是因为麻烦，一个是因为压根不满足。

一般对于排队网络，都是推荐使用子图（subgraph）进行验证。对于这个例子，可以画出这样的子图。

这里这个子图被分为了三块。

(a)

对应的部分，其实对应的式子就是

\pi(m, n) \mu_1 = \pi(m - 1, n) = \lambda

当然还需要验证

(b), (c)

的部分，验证完这些部分都成立，这个平稳分布就是正确的。因为我们这里只希望初步介绍一下，所以相关证明我们就略过了。

Tandem网络的延伸：两站网络

一般的两站网络比Tandem网络要复杂一些，大概可以画出这样的图。

也就是说，在这里，不仅仅是一条线，而是一个复杂的交互。到达一个站点（游乐场）之后，有可能就离开队列，但也有可能跑到另外一个站点。那么这个时候怎么刻画这个系统呢？

这个时候，我们会额外定义速率

r_1, r_2

。这两个表示真正意义上，稳态情况下每一个站点的顾客到达和离开的速率。那么事实上可以得到

r_1 = \lambda_1 + p_2 r_2

r_2 = \lambda_2 + p_1r_1

当然这个时候我们需要

r_1 < \mu_1

，

r_2 < \mu_2

来保证稳态的存在性。毕竟如果不是这个结果的话，相当于之前讨论的，顾客到达的速率不小于服务的速率，就会使得队伍变得无限长。

这个时候，其实它的平稳分布是

\pi(m ,n) = (\frac {r_1}{\mu_1})^m(1- \frac{r_1}{\mu_1})(\frac{r_2}{\mu_2})^n(1 - \frac{r_2}{\mu_2})

但是这个怎么推出来其实就不是很容易得到了，虽然形式上和上面类似。在这里，我们还是只说一下如何使用子图进行验证。

对于这个问题，可以画出这样的子图。

还是以

(a)

为例。这个对应的式子就是

\pi(m - 1, n + 1) \mu_2 p_2 + \pi(m- 1, n)\lambda_1 = \pi(m ,n) \mu_1 p _1 + \pi(m, n) \mu_1 ( 1- p_1)

对于

(b), (c)

也是同理。

好的，关于排队网络，我们就介绍这两个例子。剩下的内容到之后如果我们接触到，再进行补充。

小结

本节主要介绍了连续时间马尔科夫链的离出分布和到达时间的相关性质和应用。它对应上的是离散马尔科夫链的离出分布和离出时间。之后我们基本上都关注在它在排队论模型中的应用。包括传统的

M/M/1

与进阶的

M/M/s

等。另外，排队网络也是排队论应用的一个推广，但碍于知识水平有限，没有办法介绍太多。总体上来说，连续时间马尔科夫链提供了一个很好的刻画这一类模型的工具，在应用上也不算困难。

下一节我们会开始介绍鞅的相关概念和应用。这是一个全新的内容。理解它，会需要很多之前的模型铺垫，但也会更多的加深对随机过程的理解。

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

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

队列

本文分享自学弱猹的精品小屋微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

队列