排队论复习笔记

随机过程

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

对于随机过程X(t,s)，若t固定，则这个随机过程就是随机变量，X(t)所取的值成为随机过程在t时刻的状态，所有状态的集合构成随机过程的状态空间S；若s固定，则X(t,s)就是t的函数，称为随机过程的样本函数或样本曲线，也成为现实（曲线）。若随机过程的状态空间是离散的，则称之为离散状态随机过程；若状态空间是连续的，则称之为连续状态随机过程。

马尔可夫过程

当随机过程在$t_n$时刻所处的状态为已知时，过程在大于$t_n$的时刻所处的状态的概率特性只与过程在$t_n$时刻的所处的状态有关，而宇过程在$t_n$时刻以前的状态无关，就成此性质为无后效性。具有无后效性的随机过程成为马尔可夫过程。

离散时间马尔可夫链的性质

互通性

1. 若对某个$n\ge 1$，某两个状态i和j的n步状态转移概率大于0，即$p_{ij}^{(n)}\ge0$，则称系统可以自状态i到达状态j，记为$i\rarr j$。
2. 若有两个状态i和j，$i\rarr j$且$j\rarr i$，则称状态i和状态j互通，记为$i \lrarr j$。

不可约

若一个马尔可夫链的任意两个状态都互通，则此马尔可夫链称为不可约马尔可夫链；否则称为可约马尔可夫链。

周期性

周期：对于一个状态j，若$p_{jj}^{(n)}\ge0$，即过程可以经过n步从状态j返回到状态j，则定义所有正整数n的最大公约数为状态j的周期，记为$d_j$。若对一切$n\ge1，p_{jj}^{(n)}=0$，则约定$d_j=\infty$.

• 如果$d_j\ge1$，那么称状态j是周期性状态；
• 如果$d_j=1$，那么称状态j是非周期状态。

定理：互通的状态有相同的周期。

常返性

常返性分三种：

• 正常返（必定会返回，平均返回时间为有限值）
• 零常返（必定会返回，平均返回时间为$\infty$）
• 非常返（可能不再返回）

为定义常返性，给出如下描述：

$$f_j^{(n)}=P{(在离开状态j后经过n步首次返回j)}\\ f_j = \Sigma_{n=1}^\infty f_j^{(n)} = P(不断返回j)$$

如果$f_j\le 1$，状态j被称为是非常返的（短暂的，滑过的）。

如果$f_j=1$，状态j被称为是常返的（回归的）。

常反的平均返回时间

平均返回时间，定义为：

$$M_j = \Sigma_{n=1}^\infty nf_j^{(n)}$$

它是离散马尔可夫链中离开状态j后第一次返回状态j所需要的平均步数。

• 零常返：具有的平均返回时间$M_j=\infty$的常返态。
• 正常返：满足$M_j\le 0$的常返态。

定理：不可约马尔可夫链的状态集或者全由非常返态组成，或者全为零常返态，或者全为正常返态，且每个状态周期相同。（不可约马尔可夫链的状态一致性）

遍历性

在马尔可夫链中，如果n步状态转移概率$p_{ij}^{(n)}$对一切i，j存在不依赖于i的极限，即$\lim\limits_{n \to \infty}p_{ij}^{(n)}=p_j(\infty)=p_j$，则称马尔可夫链具有遍历性。

定理：如果齐次马尔可夫链的一个状态j是非周期的、正常返的，则此状态j是遍历的。

定理：只有当马尔可夫链是不可约的、非周期性的，并且所有状态都是正常返的时候，才具备遍历性。

肯达尔排队模型

输入过程的分布

• 定长输入（D）：顾客等间隔到达；

• Poisson流输入（M）：增量的满足泊松分布，即

  $$P(M(t+a)-M(a)=k)=\frac{(\lambda t)^k}{k!}e^{-a\lambda}$$

• k阶Erlang输入（$E_k$)：顾客到达过程$\tau_n, n=1,2,\cdots$是独立同分布的随机变量序列，且$\tau_n$的概率密度函数为：

  $$f(t) = \begin{cases} \frac{\lambda(\lambda t)^{k-1}}{(k-1)!}e^{-\lambda t}, &t\ge0 \\ 0, &t\le 0\end{cases}$$

• 一般独立输入（G）：也称通用独立输入，其分布可以是任意函数，但是其均值优先，且方差存在。

服务时间的分布

• 定长服务分布（D）：每个顾客接受服务的时间为正常数c;

• 负指数服务分布（M）：每个顾客的服务时间$v_i$相互独立，并具有系统的负指数分布，其分布函数为

  $$F(t) = P(v_n\le t) = 1-e^{-\mu t},\quad t\ge0,\mu>0$$

• k阶Erlang分布（$E_k$)：此处略

• 一般独立服务分布（G）：也称通用独立服务分布，所有顾客的接受服务的数据是独立同分布的非负随机变量序列，其分布函数可以是任意函数，但是其均值优先，且方差存在。

排队系统的分类和符号

肯达尔排队模型：A/B/C/D/E/F

A：顾客到达间隔时间的分布；B：服务窗服务时间分布；C：服务窗个数；D：系统中允许的最大顾客数，默认无穷；E：顾客源中顾客数，默认为无穷；F：服务规则，默认为先来先服务。

有以下两个公式成立：

$$L=L_w+L_s\\ T_{ws}=T_w+T_s$$

Little公式

$$L=\lambda T \\ L_w=\lambda_wT_w\\ L_s=\lambda_sT_s$$

排队论模型

M/M/1/1

$$P_0=\frac{1}{1+\rho}\\ P_1=\frac{\rho}{1+\rho}$$

系统中的平均顾客数量可以通过数学期望求解：

$$L = E(N) = 0\times\frac{1}{1+\rho}+1\times\frac{\rho}{1+\rho} = \frac{\lambda}{\lambda+\mu}$$

当系统中已经有一个顾客时，新来的顾客只能离去，因此$P_损=P_1$。

单位时间真正进入系统的顾客速率为：

$$\lambda_{有效}=\lambda P_0\\ \lambda_{损} = \lambda P_1$$

绝对通过能力A（单位时间内被服务完顾客的均值）和相对通过能力Q（单位时间被服务完顾客数与请求顾客数之比值）：

$$A = \lambda P_0\\ Q = \frac{A}{\lambda} = P_0$$

M/M/1/23

$$P_0 = \frac{1-\rho}{1-\rho^{24}}\\ P_k = \rho^kP_0\\ \begin{aligned} L_w &= \sum_{k=0}^{22}kP_{k+1}\\&=P_0\sum_{k=0}^{22}k\rho^{k+1}\\ &=\frac{\rho}{1-\rho}- \frac{\rho+23\rho^{24}}{1-\rho^{24}} \end{aligned}$$

系统中忙的服务员的平均个数$L_s$也可以由概率分布求得：

$$L_s = 1\times (1-P_0)+0\times P_0 = \frac{\rho-\rho^{24}}{1-\rho^{24}}$$

显然还有：

$$P_损=P_{23}\\ Q = 1-P_损$$

注意到顾客以速率$\lambda$到达系统，如果系统内总人数到达23才会离开，因此单位时间内平均进入系统的顾客数，即有效到达效率为：

$$\lambda_{有效}=\lambda(1-P_{23})= \lambda Q$$

根据Little公式可以求得平均等待时间和平均逗留时间：

$$T_w = \frac{L_w}{\lambda_{有效}}= \frac{\rho}{\mu(1-\rho)}-\frac{23\rho^{23}}{\mu(1-\rho^{23})}\\ T_{ws} = \frac{L}{\lambda_{有效}} = \frac{1}{\mu(1-\rho)} - \frac{23\rho^{23}}{\mu(1-\rho^{23})}$$

可变服务速率M/M/1

服务的速度会受当前排队顾客数目影响，当顾客数目小于等于n时服务速率为$\rho_1$，当顾客数目大于n时服务速率为$\rho_2$

$$P_k = \begin{cases} \rho_1^kP_0, &k\le n\\ \rho_1^n\rho_2^{k-r}P_0,& k>n \end{cases} \\ P_0 = \left[\frac{1-\rho_1^{n+1}}{1-\rho_1}+\frac{\rho_1^n\rho_2}{1-\rho_2}\right]^{-1}$$

系统中顾客总数量的均值也可以用数学期望来求解：

$$L = \sum_{k=0}^\infty kP_k\\ L_s = 1\times (1-P_0)+0\times P_0 = 1-P_0$$

根据Little公式可以求出顾客平均等待时间：

$$T_w =\frac{L_s}{\lambda}\\ T_{ws} = \frac{L}{\lambda}$$

顾客到来速率可变的M/M/1

当新顾客进入系统时，他会根据系统中排队顾客的长度来选择是否留下，课本中的例子是顾客到达后加入队列的概率与队列的长度成反比，即当顾客到达系统后发现有k个顾客在排队等候，那么他就以概率$\frac{1}{k+1}$加入队列。如此以来，实际上顾客进入队伍的速度也会受到影响。

$$P_k = \frac{\rho^k}{k!}P_0 P_0 = \left(\sum_{k=0}^\infty \frac{\rho^k}{k!}\right)^{-1} = e^{-\rho}$$

同样，排队人数可以用数学期望来求：

$$L = \sum_{k=0}^\infty kP_k=\rho\\ L_s =L_s = 1\times (1-P_0)+0\times P_0 = 1-P_0$$

根据Little公式可以求出顾客平均等待时间：

$$T_w =\frac{L_s}{\lambda}\\ T_{ws} = \frac{L}{\lambda}$$

这个例子中损失概率并不像之前那样简洁，当顾客发现排队人数多时会离开，损失的途径又增加了。当顾客到达系统后发现有k个顾客在排队等候，那么他就以概率$\frac{1}{k+1}$加入队列，可以看成以$\frac{k}{k+1}$离开系统。

$$\begin{aligned} P_损 &= \sum_{k=0}^\infty P_k\frac{k}{1+k}\\ & = \sum_{k=0}^\infty P_k - \sum_{k=0}^\infty \frac{P_k}{k+1}\\ & = 1-\frac{1-e^{-\rho}}{\rho} \end{aligned}$$

具有不耐烦顾客的M/M/1模型

这个部分的公式过于复杂（上面几个也是），只要知道生灭过程图怎么画就行。

有差错的单服务窗排队模型M/M/1/23/23

$$L = m-\frac{\epsilon\mu(1-P_0)}{\lambda}\\ L_w = m - (1-P_0)(1+\frac{\epsilon\mu}{\lambda})\\ T_w = \frac{m}{\epsilon\mu(1-P_0)}-\frac{1}{\epsilon\mu}-\frac{1}{\lambda}\\ T_{ws} = \frac{m}{\epsilon\mu(1-P_0)}-\frac{1}{\lambda}$$

成批到达的$M^k/M/1$模型

$$T_{ws}=\frac{k+1}{2(\mu-\lambda k)},\quad\mu>\lambda k\\ L_{ws} = \frac{\lambda k(k+1)}{2(\mu-\lambda k)}, \quad \mu>\lambda k$$

多服务窗模型M/M/N

多服务窗模型过于复杂， 大概率只会考N=2的情况，此时有两个重要的公式需要记忆：

$$T=\frac{\frac{1}{\mu}}{1-\rho^2}\\ L_w = \frac{2\rho}{1-\rho^2}$$