课程「随机过程与排队论」期末复习笔记

2024年6月18日13时至15时，我将要参加课程《随机过程与排队论》的期末考试。幸而在一周前任课老师给了一些指导，稍微有了些复习方向；这里写的是复习期间的笔记。

课本使用的是西安电子科技大学出版社出版的《排队现象的建模、解析与模拟》（ISBN号码为978-7-5606-2678）。

随机过程（第一章）

定义

定义在给定概率空间上的一族随机变量$\{X(t),t\in T\}$即随机过程。其中，参数集$T$是实数集$\mathbb{R}$的一个子集；当$t$取遍$T$中的每一个值时均有一个随机变量$X(t)$与之对应。

Markov性（无后效性／无记忆性）

用公式表达就是

$$P(X(t)\leq x|X(t_0)\leq x_0, X(t_1)\leq x_1, \dots, X(t_n)\leq x_n)=P(X(t)\leq x|X(t_n)\leq x_n)$$

这个式子的含义是“对随机过程${X(t), t\in T}$，若对任意参数$t_0<t_1<\dots <t_n$，在$X(t_0), X(t_1),\dots , X(t_n)$对应值已知的情况下$X(t)$的条件分布仅和$X(t_n)$的状态有关”。在我的理解里，这句话可以理解成“$X(t)$的条件分布只和最后一刻的状态相关”。

现在考虑两种典型概率分布的无记忆性。

几何分布的无记忆性

几何分布指的是在$n$次Bernoulli实验中试验$k$次才得到第一次成功的概率。换言之，若某事件在1次实验中成功的概率是$p$，那么当成功总试验次数$\zeta$满足

$$P(\zeta=k)=p(1-p)^k$$

恒成立时，$\zeta$符合几何分布，也记为$\zeta\sim GE(p)$。

现在，考虑如何证明几何分布的无记忆性。

可以考虑符合几何分布的如下实际问题：

一男子在赌场赌大小。他现在已经连续n场没有出「大」；现在他想要在之后的第m场all-in赌第一次出「大」。

在上述问题中不妨假设“赌第$X$次大小才第一次出现「大」”。显然$X\sim GE(p)$；如果几何分布具备无记忆性，则赌场不会记得这位赌徒在过去$n$场赌博中的任何结果（因为每次开大小都是相互独立的事件）；换言之，在累计$n$场没有出“大”的情况下接下来的第$m$场才出第一次“大”的概率$P(X=m+n|X>n)$必然与赌第$m$次出现第一次“大”的概率$P(X=m)$相等。

因此，只要证明$P(X=n+m|X>n)=P(X=m)$即说明该概率分布具有无记忆性。换言之，在几何分布中失败的前$n$次试验是沉没成本，对之后成功的概率不存在任何影响。

而显然

$$\begin{align} P(X>k) &= \sum_{i=k}^\infty p(1-p)^i=p\sum_{i=k}^\infty (1-p)^i\\ &=p\times\frac{(1-p)^k(1-(1-p)^\infty)}{1-(1-p)}\\ &=\frac{p(1-p)^k(1-0)}{p}=\frac{p(1-p)^k}{p}\\ &=(1-p)^k \end{align}$$

故

$$\begin{align} P(X=n+m|X>n) &= \frac{P(X=n+m \wedge X>n)}{P(X>n)}\\ &=\frac{P(X=n+m)}{P(X>n)}\\ &=\frac{p(1-p)^{n+m-1}}{(1-p)^n}\\ &=p(1-p)^{n+m-1-n}=p(1-p)^{m-1}&=P(X=m) \end{align}$$

得证。

服从几何分布的随机变量是唯一具有无记忆性的离散型随机变量。

负指数分布的无记忆性

负指数分布是用来描述Poisson过程中的事件之间的事件概率分布。在Poisson过程中，事件以恒定平均速率连续且独立发生。对于服从负指数分布的连续随机变量$\epsilon$，可以记作$\epsilon\sim E(\lambda)$。

考虑以下实际问题。

北京铁路局有一个严重故障的CR400BF型5033号电力动车组列车，这趟列车平均每周故障2次，求下周不发生故障的概率。

不妨把上述问题中的“一周”看作一个单位时间。那么在这一单位时间中列车的故障率$\lambda=2$。显然，单位时间内发生故障的次数$\xi$符合关于$\lambda$的Poisson分布（即$\xi\sim Po(\lambda=2)$）。

故在下周发生$x$次故障的概率是

$$P(\xi=x; \lambda)=e^{-\lambda}\frac{\lambda^x}{x!}$$

而在下周不发生故障的概率相当于发生故障数为0的概率，代入数据得

$$P(\xi=0; \lambda=2)=e^{-2}\frac{2^0}{0!}=e^{-2}$$

因此易得安全行驶时长$T$超过两个单位时间的概率

$$P(T>2)=P^2(\xi=0; \lambda=2)=e^{-4}$$

而注意到“安全行驶时长超过两周”可以理解成“在平均每个单位时间内故障4次的情况下实际发生0次故障”，也即$P(T>2)=P(\xi=0,2\lambda)$，因此

$$P(\xi=0, 2\lambda)=e^{-4}$$

类似地，不难推广至任意时间间隔$t$，对应有

$$P(T>t)=P(\xi=0; \lambda t)=e^{-\lambda t}$$

换言之，连续安全行驶时间$t$的概率是$e^{-\lambda t}$。因此显然在$t$的时长内发生过故障的概率就是

$$P(T\leq t)=1-e^{-\lambda t}$$

对此问题进行一般化。对平均每个单位时间内发生次数为$\lambda$的事件，若其在间隔为$\epsilon$的时间段内发生至少一次的概率为

$$F(\epsilon;\lambda)=P(\xi\leq\epsilon; \lambda\epsilon)=1-e^{-\lambda\epsilon}$$

其中暂记连续不发生的时长为$\xi$；式中的$F(\epsilon;\lambda)$即负指数分布的概率分布函数，求导不难知对应概率密度函数为

$$f(\epsilon; \lambda)= \begin{cases} 0&, \epsilon\leq 0\\ \lambda e^{-\lambda \epsilon}&, \epsilon>0 \end{cases}$$

现在考虑如何证明负指数分布的无记忆性。和几何分布中的实际问题解释类似，考虑如下实际问题：

北京铁路局的CR400BF-5033已经累计s个单位时间没有故障，因此检修工人估测在接下来的t个单位时间也不会发生故障。

显然，如果负几何分布具备无记忆性，“在累计$s$个单位时间未发生故障的情况下之后的$t$个单位时间也不会发生故障”的概率应该和“$t$个单位时间内不发生故障”的概率相等。这是因为，作为仅与最新状态有关的随机过程（这是无记忆性的定义），已经安全运行的$s$个单位时间已经不构成任何影响。因此只要证明$P(\epsilon\geq s+t|\epsilon\geq s)=P(\epsilon\geq t)$，即可证明负指数分布的无记忆性。而

$$\begin{align} P(\epsilon\geq s+t|\epsilon\geq s) &= \frac{P(\epsilon\geq s+t\wedge\epsilon\geq s)}{P(\epsilon\geq s)}=\frac{P(\epsilon\geq s+t)}{P(\epsilon\geq s)}\\ &=\frac{e^{-\lambda (s+t)}}{e^{-\lambda s}}=e^{-\lambda(s+t-s)}=e^{-\lambda t}&=P(\epsilon\geq t) \end{align}$$

故负指数分布具备无记忆性得证。

负指数分布一般也简称为指数分布；服从指数分布的随机变量是唯一具备无记忆性的连续性随机变量。

离散时间Markov链的五性

具备Markov性的随机过程即Markov过程；离散状态空间的Markov过程即Markov链。一般围绕离散时间的Markov链中各个状态主要讨论其互通性、常返性、周期性、遍历性；对于整个链有时会讨论其可约性。

互通性

显然只要状态$i$与状态$j$间往返均存在机会（概率大于0）就称$i,j$两状态互通。显然互通性还满足自反（$i$与$i$互通）、对称（若$i$与$j$互通，则$j$与$i$互通）和传递（若$i$与$j$互通且$j$与$k$互通，则$i$与$k$互通）三个性质。

常返性

只要从状态$i$经过若干步骤一定能够回到$i$本身，则称状态$i$常返。

常返性分为正常返、零常返两种。正常返指的是在有限时长内即可第一次返回的常返，而零常返的平均返回时长则为$\infty$。对拥有有限个状态的Markov链，常返状态必然是正常返；但若该链的状态数量无限则需仔细考虑。

下面举一个存在零常返状态的例子。

一个拥有∞个状态的Markov链，其中状态1必然转移到状态2。编号为3的整数次幂的状态有50%的概率转移到状态1，另有50%的概率转移到比它的状态编号大1的状态；其他的状态均必然转移到比其编号大1的状态。

在上方的例子中，从状态$1$出发后可以在状态$3$、$9$、$\dots$、$3^\infty$处有机会返回状态$1$，而对应在该位置返回成功的概率分别是$\frac{1}{2}$、$(\frac{1}{2})^2$、$\dots$、$(\frac{1}{2})^\infty$，对应的返回步数则分别为$3$、$9$、$\dots$、$3^\infty$。因此状态$1$的返回概率为

$$\sum_{i=1}^{\infty}(\frac{1}{2})^i=1,$$

也就是说从状态$1$出发一定能回到状态$1$，因此状态$1$是常返状态；对应返回时长期望为

$$\sum_{i=1}^{\infty}(3^i(\frac{1}{2})^i)=\sum_{i=1}^\infty(\frac{3}{2})^i=\infty,$$

换言之，这个Markov链在状态$1$处的平均返回时长无限。所以状态$1$是零常返状态。

若一个状态既不是零常返状态也不是正常返状态，则说明这个状态一定是非常返状态。非常返状态并不是说所有从该状态出发的Markov链都无法返回该状态，而是不一定回来。换言之，存在一条从非常返状态出发的线路，这条线路确定不会回到这个状态；也就是离开非常返状态后回到该状态的概率不等于1。

周期性

对于通过且仅能通过有限非零次转移可以回到其本身的状态，这个转移次数的最大公约数称为该状态的周期。周期大于1的状态称为周期性状态。

因此，有「自环」的状态一定不是周期状态；与非周期状态互通的状态一定是非周期状态。

遍历性

正常返非周期状态称为遍历状态。所有状态均遍历的Markov链称为遍历链。说人话就是，从遍历状态出发可以到达整个Markov链的任意一个状态，且到达这些状态的概率会存在一个极限。

所有与遍历状态互通的状态均遍历。

现在考虑一个例子。

（课本P21，例1.12）

齐次Markov链有状态空间{1, 2, 3, 4}，一步转移矩阵P如下所示。

$$P= \begin{bmatrix} \frac{1}{2} & \frac{1}{2} & 0 & 0\\ 1 & 0 & 0 & 0\\ 0 & \frac{1}{3} & \frac{2}{3} & 0\\ \frac{1}{2} & 0 & \frac{1}{2} & 0 \end{bmatrix}$$

在这一例子中不难看出状态1有$\frac{1}{2}$的概率进入自环，前往状态2的概率为$\frac{1}{2}$；从状态2出发必定回到状态1；状态3有$\frac{2}{3}$的概率进入自环，有$\frac{1}{3}$的概率转移到状态2；状态4有$\frac{1}{2}$概率转移到状态1，另有$\frac{1}{2}$概率进入状态3。

显然可以发现状态1与状态2互通，而状态1有自环显然是非周期状态，因此状态2也是非周期状态。另一方面，状态1的返回概率是$\frac{1}{2}+\frac{1}{2}\times 1=1$，返回时长期望为$\frac{1}{2}\times 1+(\frac{1}{2}\times 1)\times 2 = \frac{3}{2} <\infty$，因此状态1是正常返状态；类似算法可以得到状态2返回概率为$1\times\frac{1}{2}+1\times\frac{1}{2}\times\frac{1}{2}+1\times(\frac{1}{2}\times\frac{1}{2})\times\frac{1}{2}+\dots+1\times(\frac{1}{2})^{n-2}\times\frac{1}{2}=1$（其中括号内是在状态1自环中转移若干次的概率），返回时长期望为$\sum_{i=2}^n\frac{i}{2^{i-1}}=3$，因此状态2也是正常返状态。因此，状态1和状态2都是遍历状态；状态3和状态4显然为非周期状态且非常返，所以也不是遍历状态。

实际上，只要存在$m\in\mathbb{N}_+$使给定Markov链的$m$步转移矩阵$\boldsymbol{P}^m$没有零元$\boldsymbol{O}$导致$\boldsymbol{P}^m\boldsymbol{O}=\boldsymbol{O}$，这个Markov链就是遍历链。

考虑下方两个例子。

（课本P24，例1.13）

一个质点在1、2、3三个点上随机游动，其中1、3是两个反射壁。当质点处于2时，下一时刻转移到1、3的概率各为0.5，判断这个链是否有遍历性。

不难根据此例得到一步转移概率矩阵

$$\bf{P}= \begin{bmatrix} 0 & 1 & 0\\ \frac{1}{2} & 0 & \frac{1}{2}\\ 0 & 1 & 0 \end{bmatrix}$$

进而得到二步转移概率矩阵

$$\boldsymbol{P}(2)=\boldsymbol{P}^2= \begin{bmatrix} \frac{1}{2} & 0 & \frac{1}{2}\\ 0 & 1 & 0\\ \frac{1}{2} & 1 & \frac{1}{2} \end{bmatrix}$$

进而得到三步转移概率矩阵

$$\boldsymbol{P}(3)=\boldsymbol{P}^3= \begin{bmatrix} 0 & 1 & 0\\ \frac{1}{2} & 0 & \frac{1}{2}\\ 0 & 1 & 0 \end{bmatrix}$$

显然此时不难得到规律$\boldsymbol{P}^{2n+1}=\boldsymbol{P}$与$\boldsymbol{P}^{2n}=\boldsymbol{P}^2$。由于存在这种循环，从任何一个状态出发都无法找到前往其他任何状态的概率极限，因此根据遍历性定义，这条链不具备遍历性。

（课本P24，例1.14）

一个质点在1、2、3三个点上随机游动，其中1、3是两个反射壁。当质点处于2时，下一时刻转移到1、3抑或是原地不动的概率相等，判断这个链是否有遍历性。

不难看出一步转移概率矩阵

$$\boldsymbol{P}= \begin{bmatrix} 0 & 1 & 0\\ \frac{1}{3} & \frac{1}{3} & \frac{1}{3}\\ 0 & 1 & 0 \end{bmatrix}$$

随后得到二步转移概率矩阵

$$\boldsymbol{P}(2)=\boldsymbol{P}^2= \begin{bmatrix} \frac{1}{3} & \frac{1}{3} & \frac{1}{3}\\ \frac{1}{9} & \frac{7}{9} & \frac{1}{9}\\ \frac{1}{3} & \frac{1}{3} & \frac{1}{3} \end{bmatrix}$$

这时就已经能看出集合$\{\boldsymbol{P}^m\}$中不存在零元了。因此这条链具有遍历性。基于此，可以求解这条链的极限分布$\eta=(\eta_1,\eta_2,\eta_3)$。我总结的列方程思路是根据转移概率横向写转移矩阵，根据转移矩阵纵向写方程系数；比如这里的列式为

$$\begin{cases} \eta_1 &= \frac{1}{3}\eta_2\\ \eta_3 &= \frac{1}{3}\eta_2\\ \sum_{i=1}^{3}\eta_i&=1 \end{cases}$$

这个方程组也可以理解成在等式$[\eta_1,\eta_2,\eta_3]\boldsymbol{P}=[\eta_1,\eta_2,\eta_3]$和“概率总和必须是1”的正则条件中任意挑选若干个的结果——随意挑选的前提是能够确定所有极限概率分布的精确值。解得

$$\begin{cases} \eta_1&=\frac{1}{5}\\ \eta_2&=\frac{3}{5}\\ \eta_3&=\frac{1}{5}\\ \end{cases}$$

即为所求Markov链的极限分布。

可约性

一个所有状态两两互通的Markov链称为不可约Markov链，否则称为可约Markov链。

排队现象（第二章）

输入过程（顾客到达）

根据到达过程的不同概率特性一般分为定长输入（$D$）、Poisson流输入（$M$）、$k$阶Erlang输入（$E_k$）、一般独立输入（$G$）和成批到达5种。

服务分布

与输入过程相对应地，服务分布也分为定长服务分布（$D$）、负指数服务分布（$M$）、$k$阶Erlang服务分布（$E_k$）、一般独立服务分布（$G$）4种。

分类与符号：Kendall模型

使用“A/B/C/D/E/F”模型来划分排队模型。

Kendall模型中各字母含义
A	B	C	D	E	F
顾客到达间隔时间分布	服务窗口服务时间分布	服务窗口个数	系统允许的最大顾客数	顾客源中的顾客数	服务规则
不可省略			省略则默认为无穷		省略则默认先来先服务

现在考虑下面的模型和对应的含义。

M/M/c/k排队系统：

顾客按Poisson流输入，对每个顾客的服务时间为独立同负指数分布，服务窗口c个，系统允许最多k个顾客。顾客源的顾客无限，先来先服务。

上述排队系统显然是“M/M/c/k/∞/先来先服务”的省略版本。

单服务窗Poisson排队模型扩展（第四章）

单服务窗排队制M／M／1／23模型

根据模型名称即可知道，这个模型有如下几个特征：

• 顾客输入为Poisson流；
• 对每个顾客的服务时间遵从负指数分布；
• 服务窗口有且仅有1个；
• 服务平台最大容量为23个顾客；
• 顾客源的顾客量无限；
• 先来先服务。

过程分析

显然这个模型中，时刻$t$对应的排队系统队伍总长度$\iota(t)$取值空间$I=\{0,1,2,3,4,\dots,23\}$即为状态空间——这一状态空间中相邻的状态对应的顾客数相差1。由于排队系统中下一时刻的顾客数目变化量不会超过1（即要么减少1个，要么增加1个，要么保持不变），因此对于一个状态，其必然只能向与其相邻的状态转移。假设任意时刻顾客增加的概率为$\lambda$，顾客减少的概率为$\mu$，那么不难得到M/M/1/23排队模型的状态转移图如下所示。

其中，状态$k$对应系统内残留$k$名顾客，其中包括正在服务窗口享受服务的1位顾客。不妨记系统处于状态$k$的概率为$P_k$，则

$$\sum_{i=0}^{23}P_i=1\tag{a}$$

必然成立。这一暗含“系统处于每个状态的概率之和为1”之意的式子也称为概率归一化条件。

概率分布

由于任一状态对应概率守恒，对于状态$k$显然应该有从相邻状态流入的总概率与从本状态流向相邻状态的总概率相等，即

$$\mu P_k+\lambda P_k=\lambda P_{k-1}+\mu P_{k+1}(k<23,k\in\mathbb{N}_+)$$

而注意到同理所得

$$\lambda P_0=\mu P_1 \Rightarrow P_1=\frac{\lambda}{\mu}P_0$$

进而有

$$\mu P_1+\lambda P_1=\lambda P_0+\mu P_2 \Rightarrow P_2=\frac{\mu P_1+\lambda P_1-\lambda P_0}{\mu}=\frac{((\mu+\lambda)\frac{\lambda}{\mu}-\lambda)P_0}{\mu}=\frac{\lambda^2}{\mu^2}P_0$$

类似上述进行重复代入和递推，不难得到

$$P_k=\frac{\lambda^k}{\mu^k}P_0$$

记$\rho=\frac{\lambda}{\mu}$，则$P_k=\rho^kP_0$。事实上，$\rho$的实际意义在于其可以反映整个排队系统的负荷水平和强度。

此时已经可以将所有状态的概率都用含有且仅含有$P_0$的式子来替换；因此等式$(a)$可以代入为

$$\sum_{i=0}^{23}\rho^iP_0=1$$

左式用等比数列求和的方法显然可以得到为$P_0\frac{1-\rho^{24}}{1-\rho}$，故而$P_0=\frac{1-\rho}{1-\rho^{24}}$。

因此

$$P_k=\rho^k\frac{1-\rho}{1-\rho^{24}}$$

即为各状态的概率分布。

队伍均长与忙碌窗口均值

由于概率分布反映了排队系统中有$k$个人的概率，而当平均等待队伍长度$L_w=k$时整个系统中应当含有$k+1$个顾客，因此

$$\begin{align} L_w&=\sum_{i=0}^{22}iP_{i+1}=\sum_{i=0}^{22}i\rho^{i+1}P_0=\rho^2P_0\sum_{i=0}^{22}i\rho^{i-1}\\ &=\rho^2P_0\sum_{i=0}^{22}\frac{d(\rho^i)}{d\rho}=\rho^2P_0\frac{d(\sum_{i=0}^{22}\rho^i)}{d\rho}\\ &=\rho^2P_0\frac{d(\frac{1-\rho^{23}}{1-\rho})}{d\rho}=\rho^2P_0(\frac{d(\frac{1}{1-\rho})}{d\rho}-\frac{d(\frac{\rho^{23}}{1-\rho})}{d\rho})=\rho^2P_0(\frac{-23\rho^{22}}{1-\rho}+\frac{1-\rho^{23}}{(1-\rho)^2})\\ &=\frac{\rho}{1-\rho}-\frac{\rho+23\rho^{24}}{1-\rho^{24}} \end{align}$$

而系统中的顾客为0时，忙碌的服务窗口个数为$0$；当系统顾客超过0时，忙碌窗口的数量就会变为$1$。因此，系统内的平均忙碌窗口数$L_s=1\times(1-P_0)+0\times P_0=\frac{\rho-\rho^{24}}{1-\rho^{24}}$

因此系统中的队伍总均长（含正在享受服务的顾客）为

$$L=L_w+L_s=\frac{\rho}{1-\rho}-\frac{24\rho^{24}}{1-\rho^{24}}$$

这一系统已经有23名顾客时，新顾客自然只能离开，因此损失概率$P_{fail}=P_{23}$；与之相对应的，单位时间内被服务完的顾客数与请求顾客数之比（相对通过能力）$Q=1-P_{fail}$。而顾客到达系统的速率为$\lambda$，因此单位时间内平均进入系统的总顾客数（有效到达率）为$\lambda_{real}=\lambda Q$；因此，顾客在系统中的平均等待时间$T_w$与平均逗留时间$T_{ws}$分别是

$$T_w=\frac{L_w}{\lambda_{real}}=\frac{\rho}{\mu(1-\rho)}-\frac{23\rho^{23}}{\mu(1-\rho^{23})}$$

$$T_{ws}=\frac{L}{\lambda_{real}}=\frac{1}{\mu(1-\rho)}-\frac{23\rho^{23}}{\mu(1-\rho^{23})}$$

其他M／M／1排队模型

根据排队模型名称，不难知这种排队系统的特征如下：

• 顾客输入服从Poisson流；
• 服务窗口对顾客的服务分布服从负指数分布；
• 有且仅有1个服务窗口；
• 系统的容量无限；
• 顾客源的顾客量无限；
• 先来先服务。

可变服务速率的M／M／1排队模型

因为服务速率可变，所以不妨假设排队长度小于等于$n$时服务速率为$\mu_1$，长度大于$n$时服务速率为$\mu_2$。此时这种排队模型的状态转移图可设如下：

同样运用单一状态进出概率守恒，可以得到

$$P_k= \begin{cases} \frac{\lambda^k}{\mu_1^k}P_0 &,k\leq n\\ \frac{\lambda^k}{\mu_1^n\mu_2^{k-n}}P_0 &,k>n \end{cases}$$

顾客到达速率可变的M／M／1排队模型

不妨设顾客到达后加入队伍的概率与队伍长度成反比，并记排队等候人数已达$k$时的这一概率为$\frac{1}{k+1}$。那么可得到如下的状态转移图：

用同样的状态进出概率守恒可知

$$P_k=\frac{\lambda^k}{\mu^kk!}P_0$$

具有不耐烦顾客的M／M／1排队模型

不耐烦的顾客会在等待一段时间后离开队伍，前往别处寻求服务。急死他得了！

不妨假设顾客离开队伍的强度与队列长度有关。再假设顾客进队后发现有$k$个人在等候后以$k\Delta$的速率按Poisson分布离开队伍，则状态转移图如下。

进而用与先前相同的方法可以得到

$$P_k=\frac{\lambda^k}{\mu(\mu+\Delta)(\mu+2\Delta)\dots(\mu+(k-1)\Delta)}P_0$$

有差错服务的单服务窗M／M／1／m／m排队模型

由于差错服务，顾客需要返回服务窗口进行第二次服务。这会对顾客的到来速率产生一定影响。

显然根据排队模型名称可知这个模型除了输入端服从Poisson分布、服务时间服从负指数分布、服务窗口只有一个之外，系统的容量和顾客源顾客数都被限制在了$m$个。不妨设系统正确服务的概率为$\varepsilon$，则可作状态转移图如下。

不难知

$$P_k=\frac{m!\lambda^k}{(m-k)!\varepsilon^k\mu^k}P_0$$

成批到达的M^k／M／1排队模型

这是一种输入仍然服从Poisson流但是每批到达$k$个顾客的排队系统。服务窗口仍然只有一个，对每个顾客的服务时间仍然服从负指数分布，系统容量和顾客源的顾客量无限，先来先服务。在这种条件下的状态转移图如下：

在这种排队模型中，假设某个时刻系统中已经有$n$个顾客，此时新一批顾客（共$k$位）到来。这些新的顾客必须等待之前的$n$为顾客享受完服务才可以被服务，因此新到达的这批顾客每位的平均逗留时间为

$$\sum_{i=1}^k\frac{i}{\mu}\frac{1}{k}=\frac{k+1}{2\mu}$$

其中，$\frac{1}{k}$的含义是该顾客在这$k$位顾客中排在第$i$位的概率。

多服务窗Poisson排队系统（第五章）

显然这种排队系统可以记为“M/M/N”。在顾客以Poisson到达流抵达系统后，其会被分流至N个服务窗口，每个服务窗口的服务速率均为$\mu$；完成服务后离开。因此状态转移图如下所示。

在到访顾客还没有达到服务窗口总数时，显然这些顾客都有空窗口可以前往享受服务。但当顾客总数超过N时，它们将不得不排队等待。

记状态$k$的概率为$\eta_k$。则根据平稳状态下的状态进出概率守恒可知

$$\lambda\eta_0=\mu\eta_1\Rightarrow\eta_1=\frac{\lambda}{\mu}\eta_0$$

$$\lambda\eta_1+\mu\eta_1=\lambda\eta_0+2\mu\eta_2\Rightarrow\eta_2=\frac{(\lambda+\mu)\frac{\lambda}{\mu}-\lambda}{2\mu}\eta_0=\frac{\lambda^2}{2\mu^2}\eta_0$$

$$\lambda\eta_2+2\mu\eta_2=\lambda\eta_1+3\mu\eta_3\Rightarrow\eta_3=\frac{(\lambda+2\mu)(\frac{\lambda^2}{2\mu^2}\eta_0)-\lambda(\frac{\lambda}{\mu}\eta_0)}{3\mu}=\frac{\lambda^3}{6\mu^3}\eta_0$$

$$\dots$$

$$\lambda\eta_{N-1}+(N-1)\mu\eta_{N-1}=N\mu\eta_N+\lambda\eta_{N-2}\Rightarrow\eta_N=\frac{\lambda^N}{N!\mu^N}\eta_0$$

$$\lambda\eta_N+N\mu\eta_N=\lambda\eta_{N-1}+N\mu\eta_{N+1}\Rightarrow\eta_{N+1}=\frac{\lambda^{N+1}}{\mu^{N+1}N!N}$$

$$\dots$$

也即

$$\eta_k= \begin{cases} (\frac{\lambda}{\mu})^k\frac{1}{k!}\eta_0&,k<N\\ (\frac{\lambda}{\mu})^k\frac{1}{N!N^{k-N}}&,k\geq N \end{cases}$$

而显然

$$\sum_{i=0}^\infty\eta_i=1$$

故

$$\eta_0=(\sum_{k=0}^{N-1}\frac{(N\rho)^k}{k!}+\frac{(N\rho)^N}{N!(1-\rho)})^{-1}$$

对应等待队伍长度为

$$L_w=\sum_{k=0}^\infty k\eta_k=N\rho+\rho\frac{(N\rho)^N}{N!(1-\rho)^2}\eta_0$$

平均忙的服务窗口数为

$$L_s=N\rho$$

其中$\rho=\frac{\lambda}{N\mu}$.

Poisson过程本身对多窗口排队系统中的服务窗口总数下限就有要求。考虑如下实例。

（超市问题）

某超市改进了结账系统。当所有结账柜台忙时，顾客获得一个号码并等待；当一个结账柜台空闲时最小号码的顾客前往柜台结账。超市足够大，顾客到达超市服从Poisson过程，平均每小时来40位；每位顾客结账平均需要4分钟，结账时间服从指数分布。

考虑超市需要多少个结账柜台。

显然，若超市柜台数为$c$，则这家超市的结账系统属于M/M/c型排队系统；既然顾客到达超市符合Poisson过程，那么一定有$\rho=\frac{\lambda}{c\mu}<1$；代入$\lambda=40, \mu=\frac{60}{4}=15$（以1小时为1个单位时间）后可得

$$c>2.67$$

因此超市至少需要3个柜台才能使顾客到达超市服从Poisson过程。

上述情况是排队系统中所有顾客共享一个队列所对应的结果。现在思考如果将队列分为若干份会否缩短等待时间。

现有两种排队方案。

方案一：两个速率为0.5λ的Poisson流分别进入各自的一个服务窗口；

方案二：一个速率为λ的Poisson流进入两个服务窗口。

试比较哪一个排队方案更好。

在上例中衡量方案好坏的关键是平均等待时间。不难知道方案一中为两个相互独立的M/M/1排队模型，因此只要算其中一个的平均等待时间即可。

对方案一，$\rho=\frac{\frac{\lambda}{2}}{\mu}=\frac{\lambda}{2\mu}$。代入先前的结论可知

$$P_k=\rho^kP_0$$

进而等待队伍均长为

$$\begin{align} \sum_{i=0}^\infty iP_{i+1}&=\sum_{i=0}^\infty\rho^{i+1}iP_0=\rho^2\sum_{i=0}^\infty i\rho^{i-1}P_0\\ &=P_0\rho^2(\sum^{\infty}_{i=0}\rho^i)'=P_0\rho^2(\frac{1-\rho^\infty}{1-\rho})'&=\frac{P_0\rho}{(1-\rho)^2} \end{align}$$

对应平均等待时间

$$\frac{\frac{P_0\rho}{(1-\rho)^2}}{\frac{\lambda}{2}}=\frac{2P_0\rho^2}{\lambda(1-\rho)^2}$$

另一方面，

$$P_0\sum_{i=0}^\infty\rho^i=1\Rightarrow\frac{1-\rho^\infty}{1-\rho}P_0=1$$

即

$$P_0=1-\rho$$

故平均等待时间为$\frac{2\rho}{(1-\rho)\lambda}=\frac{2}{2\mu-\lambda}$.

而对于方案二显然也有$\rho=\frac{\lambda}{2\mu}$，结合本章节内容知

$$P_0=(1+2\rho+\frac{(2\rho)^2}{2!}\frac{1}{1-\rho})^{-1}=\frac{1-\rho}{1+\rho}$$

对应等待队伍长度

$$L_w=2\rho+\rho\frac{(2\rho)^2}{2!}\frac{1}{(1-\rho)^2}P_0=\frac{2\rho}{1-\rho^2}$$

进而平均等待时间为$\frac{L_w}{\frac{\lambda}{2}}=\frac{4\mu}{4\mu^2-\lambda^2}$

现在比较两个方案的平均等待时间，知方案二的平均等待时间必然小于方案一，因此方案二更好。

现有两个排队方案。

方案一：两个速率为20和15的Poisson流分别进入各自的一个服务窗口；

方案二：一个速率为35的Poisson流进入两个服务窗口。

已知服务窗口对顾客的服务速率均为30个/小时，试比较哪一个排队方案更好。

由题意可知$\lambda_1=20,\lambda_2=15, \lambda '=35, \mu=30.$据此，$\rho_1=\frac{\lambda_1}{\mu}=\frac{2}{3},\rho_2=\frac{\lambda_2}{\mu}=\frac{1}{2}, \rho '=\frac{\lambda '}{2\mu}=\frac{7}{12}$.

那么这两个方案的3个平均等待时长分别为

$$T_{w1}=\frac{\frac{1}{\mu}}{1-\rho_1}=\frac{1}{10}=0.1$$

$$T_{w2}=\frac{\frac{1}{\mu}}{1-\rho_2}=\frac{1}{15}\approx 0.067$$

$$T_{w}'=\frac{\frac{1}{\mu}}{1-\rho '^2}\approx 0.0505$$

因此依然是方案二更好。

综合上述两个结果，采用多服务台排队系统显然会优于将这些服务台分散使用的方案。

下面考虑两个实际例子。

有一火车售票处，其设有一个售票窗口，顾客到达为Poisson流，平均到达率为0.3人/分。服务时间服从负指数分布，平均服务率为0.4人/分，求：

①服务系统的服务强度；
②系统状态的概率分布；
③系统中平均顾客数量；
④顾客的平均逗留时间；
⑤等待服务的顾客数量；
⑥顾客的平均等待时间；
⑦顾客逗留时间超过15分钟的概率。

由题可得此火车售票处属于M/M/1排队模型，其中$\lambda=0.3,\mu=0.4$.故服务强度$\rho=\frac{\lambda}{\mu}=0.75$，进而$P_0=1-\rho=0.25$.

因此，概率分布不难得到为

$$P_k=\rho^kP_0=\frac{\rho^k}{4}=\frac{3^k}{4^{k+1}}$$

进而得系统中顾客的平均等待时间

$$T_w=\frac{\frac{1}{\mu}}{1-\rho}=10(\min)$$

对应等待服务的队伍长度期望

$$L_w=\lambda T_w=3$$

而窗口的忙碌期望为

$$L_s=1-P_0=0.75$$

因此整个系统里的顾客总数期望为$L=L_w+L_s=3.75$.进而顾客逗留时间为

$$T_{ws}=\frac{L}{\lambda}=12.5(\min)$$

对于顾客逗留时间超过15分钟的概率，本质上是寻找实际$T_{ws}>15$的概率；此时对应的整个系统的人数是$\lambda T_{ws}>4.5$。换言之只要求整个系统的人数大于等于5的概率即可。

先求系统人数小于5的概率为

$$P_{<5}=P_0+P_1+P_2+P_3+P_4=\sum^{4}_{i=0}(\frac{3^i}{4^{i+1}})=\frac{781}{1024},$$

故系统逗留总人数不少于5的概率为$1-P_{<5}=\frac{243}{1024}\approx 0.2373$.

综合上述计算，这个火车站售票处的服务强度为0.75，概率分布为$P_k=\frac{3^k}{4^{k+1}}$（对应系统状态$k$的概率），系统中平均顾客数量为3.75位，顾客平均逗留时间为十二分半，等待服务的顾客数量为3位，平均等待时间为10分钟；顾客逗留时间超过15分钟的概率为0.2373。

一加油站有3台加油机，加油汽车的抵达过程符合Poisson过程，加油时间服从负指数分布；若平均每小时有30辆车来加油，每辆车的加油时间为5分钟，求加油站的平均汽车数量和每一辆车从进入加油站到完成加油所需要的时间。

显然根据题意知道这个加油站符合M/M/3模型。其中，$\lambda=30, \mu=\frac{60}{5}=12$（以一小时为一个单位时间），进而$\rho=\frac{\lambda}{3\mu}=\frac{5}{6}\Rightarrow L_s=N\rho=2.5$.

故

$$\eta_0=(\sum_{k=0}^{N-1}\frac{(N\rho)^k}{k!}+\frac{(N\rho)^N}{N!(1-p)})^{-1}=(1+\frac{5}{2}+\frac{25}{8}+(\frac{5}{2})^3)^{-1}=\frac{4}{89}$$

因此等待的队伍长度为

$$L_w=N\rho+\rho\frac{(N\rho)^N}{N!(1-\rho)^2}\eta_0=\frac{5}{2}+\frac{5}{6}\frac{(\frac{5}{2})^3}{\frac{1}{6}}\frac{4}{89}=\frac{1070}{178}\approx 6.001$$

从而整个系统里的顾客数（车辆总数）为$L=L_s+L_w=8.501$.

顾客在系统内的逗留时间为$\frac{L}{\lambda}=0.2833$小时。

排队网络（第八章）

定义

一个比较复杂的服务系统，在此系统中经常需要讨论多个队列的互联。

分类

排队网络共分为开环网络、闭环网络和混合网络共3种。

Jackson网络

Jackson网络需要满足以下四个条件：

1. 所有系统外的访问者不论先访问哪一个服务站都服从Poisson分布；
2. 所有服务站的服务时间均服从负指数分布；
3. 所有服务站均可接待无限数量的顾客；
4. 一个顾客被完成一个服务后被转移至另一个服务站的概率与其已接受的服务无关，与其他服务所在的服务站也无关。

现在，考虑三个运用开放Jackson网络系统的两个实际例子。

一个工作站包含加工、细加工、装饰三个服务。顾客访问该工作站首先要进行加工，然后有80%的顾客进行细加工后再被装饰，另外20%则直接被装饰。工作站内有一台机器进行加工，平均加工时间5分钟；有两台机器进行细加工，每台每次平均加工15分钟；还有一台机器用于装饰，平均加工时间为6分钟。这些服务均服从指数分布；现在有服从Poisson分布的顾客流访问工作站，平均7.5分钟来一个新顾客。

显然得到各服务之间的转移矩阵

$$\boldsymbol{P}= \begin{bmatrix} 0 & 0.8 & 0.2\\ 0 & 0 & 1\\ 0 & 0 & 0 \end{bmatrix} ,$$

且加工、装饰两服务为M/M/1模型，细加工为M/M/2模型；其中$\lambda_1=\frac{60}{7.5}=8, \mu_1=\frac{60}{5}=12, \mu_2=\frac{60}{15}=4, \mu_3=\frac{60}{6}=10$.

进而可以得到方程组

$$\begin{cases} \lambda_2=0.8\lambda_1\\ \lambda_3=0.2\lambda_1+\lambda_2 \end{cases}$$

即$\lambda_2=6.4,\lambda_3=8$.进而可得$\rho_1=\frac{\lambda_1}{\mu_1}=\frac{2}{3}, \rho_2=\frac{\lambda_2}{2\mu_2}=0.8, \rho_3=\frac{\lambda_3}{\mu_3}=0.8$.

进而有平均等待时长

$$T_{w1}=\frac{\frac{1}{\mu_1}}{1-\rho_1}=\frac{1}{4},$$

$$T_{w3}=\frac{\frac{1}{\mu_3}}{1-\rho_3}=\frac{1}{2}.$$

对应有平均等待队伍长度

$$L_{w1}=\lambda_1T_{w1}=2,$$

$$L_{w3}=\lambda_3T_{w3}=4.$$

而$P_{0,1}=1-\rho_1=\frac{1}{3}, P_{0,3}=1-\rho_3=\frac{1}{5}\Rightarrow L_{s1}=1-P_{0,1}=\frac{2}{3}, L_{s3}=1-P_{0,3}=\frac{4}{5}$

故系统内总人数

$$L_1=L_{w1}+L_{s1}\approx 2.667,$$

$$L_3=L_{w3}+L_{s3}=4.8.$$

现在看细加工服务站。

显然

$$P_{0,2}=(\sum_{k=0}^{N-1}\frac{(N\rho)^k}{k!}+\frac{(N\rho)^N}{N!(1-p)})^{-1}=\frac{1}{9},$$

对应系统内等待顾客数$L_{w2}=\frac{2\rho_2}{1-\rho_2^2}=\frac{40}{9}\approx 4.44$。进而有系统内总顾客数期望$L_2=L_{w2}+(1-P_{0,2})=\frac{16}{3}\approx 13.33$.

一个工作站包含加工、细加工、装饰三个服务。顾客访问该工作站首先要进行加工，然后有80%的顾客进行细加工后再被装饰，另外20%则直接被装饰。所有被细加工的顾客有10%需要退回到第一种状态重新加工，所有被装饰的顾客也有10%需要退回到第一种状态重新加工。工作站内有一台机器进行加工，平均加工时间5分钟；有两台机器进行细加工，每台每次平均加工15分钟；还有一台机器用于装饰，平均加工时间为6分钟。这些服务均服从指数分布；现在有服从Poisson分布的顾客流访问工作站，平均7.5分钟来一个新顾客。

显然得到各服务之间的转移矩阵

$$\boldsymbol{P}= \begin{bmatrix} 0 & 0.8 & 0.2\\ 0.1 & 0 & 0.9\\ 0.1 & 0 & 0 \end{bmatrix} ,$$

且加工、装饰两服务为M/M/1模型，细加工为M/M/2模型；其中$\lambda_0=\frac{60}{7.5}=8, \mu_1=\frac{60}{5}=12, \mu_2=\frac{60}{15}=4, \mu_3=\frac{60}{6}=10$.

进而根据

$$\begin{cases} \lambda_1=\lambda_0+0.1\lambda_2+0.1\lambda_3\\ \lambda_2=0.8\lambda_1\\ \lambda_3=0.2\lambda_1+0.9\lambda_2 \end{cases}$$

解得$\lambda_1=9.662, \lambda_2=7.729, \lambda_3=8.889$，进而知道$\rho_1=\frac{\lambda_1}{\mu_1}=0.8052, \rho_2=\frac{\lambda_2}{2\mu_2}=0.9661, \rho_3=\frac{\lambda_3}{\mu_3}=0.8889$.

随后可得系统平均等待顾客时间

$$T_{w1}=\frac{\frac{1}{\mu_1}}{1-\rho_1}=0.4278,$$

$$T_{w3}=\frac{\frac{1}{\mu_3}}{1-\rho_3}=0.9001$$

故系统各服务站等待队伍长度期望

$$L_{w1}=\lambda_1T_{w1}=4.1334, L_{w2}=\frac{2\rho_2}{1-\rho_2^2}=28.99, L_{w3}=\lambda_3T_{w3}=8.0009$$

而各服务站服务窗口空闲期望

$$P_{0,1}=\frac{1-\rho_1}{1+\rho_1}=0.1079$$

$$P_{0,2}=\frac{1-\rho_2}{1+\rho_2}=0.0172$$

$$P_{0,3}=\frac{1-\rho_3}{1+\rho_3}=0.0588$$

进而得各服务站服务人数期望

$$L_{s1}=1-P_{0,1}=0.8821$$

$$L_{s2}=1-P_{0,2}=0.9828$$

$$L_{s3}=1-P_{0,3}=0.9412$$

所以各服务站总人数期望分别是

$$L_1=L_{w1}+L_{s1}=5.0155$$

$$L_2=L_{w2}+L_{s2}=29.9728$$

$$L_3=L_{w3}+L_{s3}=8.9421$$

顾客在整个系统里逗留的时间为$\frac{L_1+L_2+L_3}{\lambda_0}=5.4913$小时，排队时间为$\frac{L_{w1}+L_{w2}+L_{w3}}{\lambda}=5.140$小时。

（800免费电话问题）

某公司800免费电话服务如下：当用户拨号获得语音提示后可以按「1」进入产品介绍，按「2」进入问题咨询。用户用于听取语音提示并决定按「1」还是「2」的时间平均为30秒且按负指数分布，一次只能有一名用户听取语音提示。大约55%的用户会选择产品介绍功能，在该功能中由3名客服人员负责；产品介绍平均6分钟，服从负指数分布。45%的用户会选择问题咨询功能；该功能有7名客服人员负责，平均耗时20分钟，符合指数分布。大约有2%的用户听完产品介绍后会转到问题咨询，也有1%的用户在问题咨询完后转到产品介绍。每小时平均有35名用户拨打这个电话，且符合Poisson过程；当用户不能获得服务时，他们会聆听悦耳的音乐作为等待。分析每个环节的等待用户平均数和用户的平均通话时间。

显然得到各服务之间的转移矩阵

$$\boldsymbol{P}= \begin{bmatrix} 0 & 0.55 & 0.45\\ 0 & 0 & 0.02\\ 0 & 0.01 & 0 \end{bmatrix} ,$$

且这三个服务分别属于M/M/1、M/M/3、M/M/7模型，其中$\lambda_0=35, \mu_1=\frac{60}{0.5}=120, \mu_2=\frac{60}{6}=10, \mu_3=\frac{60}{20}=3$。

进而列方程组

$$\begin{cases} \lambda_1=\lambda_0\\ \lambda_2=0.55\lambda_1+0.01\lambda_3\\ \lambda_3=0.45\lambda_1+0.02\lambda_2 \end{cases}$$

解得$\lambda_1=35, \lambda_2=19.411, \lambda_3=16.138$，进而$\rho_1=\frac{\lambda_1}{\mu_1}=0.2916, \rho_2=\frac{\lambda_2}{3\mu_2}=0.647, \rho_3=\frac{\lambda_3}{7\mu_3}=0.768$

分别对后两者代入$P_0=(\sum_{k=0}^{N-1}\frac{(N\rho)^k}{k!}+\frac{(N\rho)^N}{N!}\frac{1}{1-\rho})^{-1}$和$L_w=N\rho+\rho\frac{(N\rho)^N}{N!}\frac{P_0}{(1-\rho)^2}$得

$$L_{w2}=0.765$$

$$L_{w3}=1.402$$

进而

$$L_{2}=2.706$$

$$L_{3}=6.781$$

对第一个环节显然可知$P_{0,1}=\frac{1-\rho_1}{1+\rho_1}=0.548\Rightarrow L_{s1}=1-P_{0,1}=0.452$，且$T_{w1}=\frac{\frac{1}{\mu_1}}{1-\rho_1}=0.0117\Rightarrow L_{w1}=\lambda_1T_{w1}=0.412$

故在整个电话里逗留的用户总数为$L_1+L_2+L_3=9.899$，故平均逗留时间为$\frac{9.899}{\lambda_0}=0.283$小时。