论文记录-排队论公式理解

泊松分布

一个随机事件的发生服从泊松分布$P(\lambda)$

$x$: 在单位时间段内事件发生的次数 $P(x=k)=e^{-\lambda}\frac{\lambda^k}{k!}$

如果我们希望将时间段从$[0,1]$拓展到$[0,t]$，则参数会改为$\lambda t$，即事件Event~$P(\lambda t)$，则：$P(x=k)=e^{-\lambda t}\frac{(\lambda t)^k}{k!}$

在$[0,t]$区间内时间发生至少1次的概率=区间内等候时间$\lt t$的概率：

$$\begin{align} P(occur)=P(Waiting\leq t)\\ =1-P(x=0)=1-P(Waiting>t)=1-e^{-\lambda t}\\ P(Waiting\leq t)=1-P(Waiting>t)\\ pdf_T=\frac{d}{dt}(cdf_T)=\lambda e^{-lambda t} \end{align}$$

$p_0(t)$表示在时长t的时间段内没有到达

$p_n(t)$表示在时长t的时间段内有n次到达

期望计算的两种方式

概率密度函数PDF：$f(t)$，累积分布函数CDF：$F(t)$，对PDF直接积分可以得到CDF，即$\int_{-\infty}^t f(t)dt=F(t)$

用PDF计算期望：从期望的定义可知，对所有值，计算$值*概率$并求和就是期望，因此计算公式是$\int_0^\infty tf(t)dt$

用CDF计算期望：

1. 对于任何连续随机变量，累积分布函数（CDF）$F(t)$ 是其概率密度函数（PDF）$f(t)$的积分：$F(t)=\int_{0}^{t} f(u)du$
2. 分部积分的公式是$\int udv=uv-\int vdu$
3. 我们取$u=t, dv=f(t)dt$，那么$du=dt, v=F(t)$，根据分部积分，可得$\int_0^\infty tf(t)dt=tF(t)|_0^\infty-\int_0^\infty F(t)dt$
4. 对于第一部分，t=0时，该项是0；t是无穷大时，F(t)趋向于1，F(t) 趋向于 1 的速度不足以抵消 t的增长，最终还是为0，于是期望就变成了$-\int_0^\infty F(t)dt$（这部分也没完全理解，暂且先接受下来吧）
5. 对于第二部分，由于 $F(t)$ 是从0到t的PDF的积分，其值从0增加到1。所以 $1−F(t)$就是从1减少到0的函数，直观来说$-\int_0^\infty F(t)dt$和$\int_0^\infty 1-F(t)dt$是同一个面积的不同形式，它俩t的取值范围不一致，因此最终期望的计算公式就可以写成$\int_0^\infty 1-F(t)dt$。

另一种证明方式：

$$\begin{align} E(x)=\int_0^\infty yP(y)dy=\int_0^\infty \int_0^y P(y) dxdy \\ =\int_0^\infty \int_x^\infty P(y) dydx=\int_0^\infty 1-F(x)dx \end{align}$$

排队论

$W_q(t)$表示排队时间小于等于t的概率，某顾客在0时刻到达，此时系统已有n个顾客，如果希望在t时刻服务该顾客，则前n个顾客需要在$[0,t]$内完成服务，这个时间服从n阶埃尔朗分布（先不讨论这个分布）。

$$\begin{align} W_q(t)&=Pr\{T_q\leq t\}=W_q(0)+\sum_{n=1}^\infty Pr\{服务完n个顾客所需的时间不超过t|顾客到达时看到系统内有n个顾客\}p_n\\ &=1-\rho+(1-\rho)\sum_{n=1}^\infty \rho^n\int_0^t\frac{\mu(\mu x)^{n-1}}{(n-1)!}e^{-\mu x}dx\\ &=1-\rho+\rho\int_0^t\mu(1-\rho)e^{-\mu(1-\rho)x}dx\\ &=1-\rho e^{-(\mu-\lambda)t} \end{align}$$

这段的解释很直接，顾客排队时间小于等于t的概率是两部分求和，第一部分是不用排队的概率，第二部分是要排队但排队时间小于等于t的概率，而第二部分又可以表达为：排队队列中有1、2、…、n个顾客，并且在时间t内这n个顾客都完成服务离开队列，因此是条件概率再累计求和的形式。

我们用等待时间对这个概率积分，即$\int_0^\infty W_q(t) dt$，得到的应该是计算$等待时间*在这个时间内排到队首的概率$的所有情况并求和。

而相反，$1-W_q(t)$表示顾客排队时间大于t的概率，对之积分，即$\int_0^\infty [1-W_q(t)] dt$，得到的是计算$等待时间*在这个时间内排不到头的概率$的所有情况并求和，

$T_q$的期望是$W_q=\rho/(\mu-\lambda)$

$$W_q=\int_0^\infty[1-W_q(t)]dt=\int_0^\infty\rho e^{-\mu(1-\rho)t}dt=\frac{\rho}{\mu-\lambda}$$

这里之所以写$1-W_q(t)$就是借用了期望的CDF计算方式。

直观来说，$W_q(t)$是等待时间小于等于t的概率，$1-W_q(t)$是等待时间大于t的概率，即顾客在时间 t时刻仍然在等待的概率，对它用t积分，得到的结果可以理解为“顾客预期还需要等待的总时间”的期望，数学上，这个积分表示的是顾客在队列中的预期时间长度，也就是平均等待时间$W_q$。

一个事件的期望发生时间可以通过考虑它在每一时刻未发生的累积概率来估算。在排队理论的背景下，这意味着通过考虑在任一特定时间 tt 内顾客仍未获得服务的概率，来估算整体的平均等待时间。