Lindley 等待时间递推

下一位到来之前，服务者最多能消化 $A_n$ 时间的工作。原有欠账 $W_n$ 加上本顾客服务 $S_n$，减去可用时间；若结果为负，意味着服务台曾空闲，下一位等待只能归零。正部运算把随机游走在零处反射，而不是让系统储存“负等待”用于抵扣未来服务。

令 $Y_n=S_n-A_n$ 且 $W_1=0$，展开得到

每个后缀和代表从某位过去顾客起累计的净工作量，取最大值等于找到最后一次空闲以后尚未消化的欠账。

取前三位服务时长为 $S_1=2,S_2=4,S_3=1$，相邻到达间隔为 $A_1=3,A_2=1,A_3=5$，所有时间用同一单位。第一位无需等待，逐步执行为

第二位先于第三位一单位到达，却需服务四单位，所以第三位正好等三单位。第三位及前面欠账合计四单位，距离第四位到来还有五单位，因此队伍在第四位之前清空。计算同时解释了每次截零对应的实际空闲。

实现只保留当前 $W$，顺次读入 $(S_n,A_n)$ 并赋值 $W\leftarrow max(0,W+S_n-A_n)$。在每次实数加减与比较为单位操作的计数下，处理 $n$ 对输入的时间为 $O(n)$，工作空间为 $O(1)$；若保存每位等待记录，输出本身需 $O(n)$ 空间。循环不变量是当前值恰等于下一位到达时所有先到顾客尚余的工作量。

负漂移的作用可以从反向累积和看见。把 IID 净增量扩成双向序列 $(Y_n{)}_{n\in \mathbb{Z}}$；当 $E|Y_0|<\mathrm{\infty }$、$E{Y}_0<0$ 时，强大数定律公理库强大数定律Law of large numbers · Strong law of large numbers · SLLN独立同分布且可积时，样本均值沿几乎每条无限样本路径收敛到共同期望。使每个固定 $n$ 的长反向和趋于 $-\mathrm{\infty }$。因此

几乎必然有限，空和为零。逐项展开就有 $W_{n+1}^{\ast }=(W_n^{\ast }+Y_n{)}_{+}$，而双向 IID 序列的平移不变性使 $(W_n^{\ast })$ 平稳。从空队列启动的有限后缀最大值，在分布上等于同一双向过去的截断上确界；截断长度增大时单调趋于 $W_n^{\ast }$，从而得到等待分布的平稳极限。有限均值等待并未由此保证。

若 $EY>0$，从空队列启动时 $W_{n+1}\ge \sum _{j=1}^n{Y}_j\to \mathrm{\infty }$。临界 $EY=0$ 则不能一概判断：$S_n=A_n\equiv 1$ 给出零等待；若 $Y_n$ 为独立对称的 $\pm 1$，递推是在零处截断的对称随机游走。其平稳方程先给 ${\pi }_1={\pi }_0$，再递推得所有 ${\pi }_n$ 相等，无法归一化，因此这个临界模型没有平稳概率。

多服务台、抢占优先级或顾客会放弃时，单个标量不再完整描述未来。需要工作量向量、优先级状态或剩余耐心等信息，不能把原递推当成通用排队公式。

Lindley 递推直接支持仿真，也把稳定性转成随机游走漂移问题。Poisson 到达这一附加结构能将稳态均值化简为Pollaczek–Khinchine 公式公理库Pollaczek–Khinchine 平均等待公式Pollaczek-Khinchine mean formula在稳定 M/G/1 队列中，将平均等待分解为剩余服务与前方顾客工作量，显出二阶矩效应。；一般更新到达仍能运行本递推，却通常没有同样的简单均值表达式。