直觉
新顾客要先等当前服务者做完剩余工作,再等队列中排在自己前面的顾客。当前服务的剩余时长会被长度偏倚放大:观察时刻更容易落在长服务里。这正是检查悖论理路检查悖论与长度偏倚Inspection paradox · Renewal length bias随机时刻按长度偏倚抽取更新区间,剩余寿命的平均值由二阶矩决定。进入排队公式的位置。把剩余服务和前方工作量取期望之前,还需分别说明平稳观察、到达观察以及均值有限性的依据。
先建立平稳版本和截断均值
在整条实线上取平稳 Poisson 到达点,并为各点独立附上服务标记。负漂移 使从过去累积的净工作量向 趋去;Lindley 页的过去上确界因而有限。按先来先服务从这份过去记录构造队列,给出平稳等待;同一构造与时间平移相容,因而整个队列状态过程也平稳。负漂移还使确定观察时刻的当前忙期只能开始于有限过去;有界窗口内到达有限,所以当时排队人数有限,每位顾客的等待和完成时刻均几乎必然有限。这些结论不先要求等待的期望有限。
先把服务截断为 ,,负载仍小于一。独立到达间隔 给净增量 。其矩母函数理路矩母函数Moment-generating function · MGF在存在邻域内以 E[e^{tX}] 编码随机变量各阶矩的函数。在零附近有限,且在零点的导数为 ,所以可选 使 。对 Lindley 页的反向上确界,并集界理路并集界Union bound · Boole 不等式多个坏事件中至少一个发生的概率,不超过各事件概率之和。与Markov 不等式理路Markov 不等式Markov's inequality非负随机变量超过阈值的概率由其期望除以阈值控制。给出 时
积分尾界证明截断模型的到达顾客平均等待有限。下面先对这个有界服务模型证明均值等式,暂略去上标 ;最后再去掉截断。这样不会在无穷均值之间移项。
服务开始的强度与时间观察的剩余量
记第 位顾客的到达、开始服务时刻为 ,服务标记为 。Little 定律页的平稳标记计数测度理路Little 定律Little law从同一批顾客的占用面积推出平均人数等于有效到达率乘平均逗留时间,并明确系统边界。给出到达与联合标记 的期望测度 。其中 的服务边缘分布仍为原来的 。对非负可测 ,Tonelli 定理理路Tonelli 定理Tonelli's theorem非负可测函数的二重积分与两种迭代积分相等,允许共同取无穷。和时间平移换元给出
只用每个 有限便可完成内层时间积分,不需要 ,也不需要服务开始点构成更新过程。
令 为平稳时刻正在执行的服务的剩余时长,空闲时置零;忙时该服务总长为 、已服务时间为 。将上述服务开始点的强度与每段服务的占用区间结合,对任意非负可测 有
取 得忙概率 ,再除以它,便得到条件忙时的长度律 ,且给定长度 后,所处阶段在 上均匀。零时长服务不占用时间。这个长度—阶段观察律与以 为间隔的平稳更新过程相同,所以检查悖论的剩余时间公式理路检查悖论与长度偏倚Inspection paradox · Renewal length bias随机时刻按长度偏倚抽取更新区间,剩余寿命的平均值由二阶矩决定。在这里也成立;直接取 则给
不预知未来的到达为何看见相同分布
这里的 PASTA 需要过程级的不预知条件:对包含过去到达与已到达顾客独立服务标记的历史 ,未来 Poisson 增量独立于 。队列只按这份历史运行。不能仅凭到达间隔的边缘分布就使用 PASTA,也不能拿到达者已加入后的状态作比较。
其期望版本可直接证明。记 为 内的到达数。若 是有界、左连续、适应于 的观察量,把 分成确定小区间,并在 使用 。未来增量独立性给出
网格趋细时,左连续性使左侧逐条记录趋于 。若 ,其绝对值受 控制,且 ;右侧由 控制。用控制收敛定理理路控制收敛定理Dominated convergence theorem几乎处处收敛且被同一可积函数控制时,可以交换极限与积分。得到
在平稳版本中,右侧等于 。取到达前状态左极限的有界连续测试函数,就说明到达前观察与平稳时间观察同分布;非负无界观察量再由截断和单调收敛处理。队列在有限窗口内只有有限次到达和服务完成(零时长服务也只涉及有限个在场顾客),因此这里所需的左极限观察过程确实存在。
前方工作量与合法移项
令 为时刻零尚未开始服务的人数, 为这些顾客的完整服务时长之和。先来先服务下,本顾客等待 只由更早顾客及到达记录决定,独立于自己的 。再用平稳标记测度和 Tonelli,
第二个恒等式也是等待区的 Little 定律。这一步并未假设“从队列随便选一人”的服务标记没有选择偏差,而是以到达顾客的 明确计算所需的占用加权均值。
到达前总工作量为 ,恰是新顾客的排队等待。PASTA 因而给出
对当前有界服务模型,前面已证明 ,其余各项也有限,所以可以移项,得到
以下省略到达均值的上标,与形式陈述的 一致。
去掉服务截断
让各截断模型共享同一份双向服务与到达序列。每个有限反向和随 增加而增加,上确界与递增极限可交换,故 。由单调收敛定理理路单调收敛定理Monotone convergence theorem非负可测函数单调递增时,积分极限等于极限函数积分。,
有限二阶矩时右边有限;二阶矩无穷时则为 ,而分母仍严格为正。最后逐位顾客有 ,取非负期望便得总逗留时间公式。
例子与边界
固定平均服务时间 和负载 。若服务时间恒为 ,则 ,
若服务指数分布且均值仍为 ,,等待翻倍为 ,与M/M/1理路M/M/1 排队模型M/M/1 queue从单服务台的生灭速率推出几何稳态、负载条件与平均等待,区分队内和系统内指标。吻合。比较并没有改变平均处理能力,差别完全来自服务波动。
若服务以相等概率取 与 ,则均值为 ,二阶矩为 ,平均等待是确定服务情形的 倍。这里两点分布提供可以逐项核验的方差效应。
稳定性 只保证工作量不持续逃向无穷,不保证平均等待有限。例如服务尾部满足 、,仍可选足够小的 使系统稳定,但 。
若到达不是 Poisson,顾客可能系统性地避开或追上忙时,PASTA 这一步失效。先来先服务也很重要:不同优先级会改变谁在谁前面,不能把所有类别的等待直接套进同一个公式。