首次清空要回答什么问题?
一名顾客到来,服务员立即开始工作。在服务完成之前,新顾客仍可到来;他们接受服务时又可能有更多人到来。服务员要连续工作多久,系统才首次清空?单知道平均到达率不足以回答:服务时间的分布和两种时钟的独立性同样重要。
本节把已有的泊松(Poisson)过程和生灭链连到首次到达问题。
模型与首次回到零
设到达构成速率 λ>0 的泊松过程;各次服务时间独立,均服从速率 μ>0 的指数分布,并且与到达过程独立。系统只有一名服务员,等待空间无限,按先到先服务的次序处理;只要有顾客,服务员便不停工作。令 X(t) 为时刻 t 系统中的人数,包含正在接受服务的人。
由 X(0)=1 开始,定义繁忙期 B=inf{t≥0:X(t)=0};若永不清空,则取 B=∞。负载定义为 ρ=λ/μ。
指数分布的无记忆性保证,只需知道当前人数,便足以决定下一事件的条件分布。由状态 n≥1 出发,到达率为 λ,离开率为 μ;在零状态则只可能有到达。总跳跃率有界,所以跳跃构造不会爆炸。若服务时间不是指数分布,已服务多久一般会影响剩余时间,单记录 X(t) 未必是马尔可夫(Markov)过程。
对 s>0,定义 L(s)=E[e−sB;B<∞]。则
L(s)=2λλ+μ+s−(λ+μ+s)2−4λμ.而且
Pr(B<∞)=min(1,λμ),EB={(μ−λ)−1,∞,λ<μ,λ≥μ.这里期望容许取无限大;若 B=∞ 有正概率,期望便是无限大。
设第一个事件的时间为 T。两个独立指数时钟竞争,得到 T∼Exp(λ+μ);事件为离开的概率是 μ/(λ+μ),为到达的概率是 λ/(λ+μ),事件种类与 T 独立。若第一事件是离开,繁忙期便结束;若是到达,人数增至二。由二到零必先由二到一,再由一到零。在正状态的平移对称性及首次到达时的强马尔可夫性下,由二到零的时间与两个独立 B 的和具有相同的广义分布。这是分布上的构造:即使第一个副本为无限大,仍可独立抽取第二个副本;在该路径上第二段实际上并未开始。以 e−s∞=0 约定,可得
L(s)=λ+μ+sμ+λ+μ+sλL(s)2.此二次方程有两个正根。由于 s>0,二次式在零处为正,在一处为负,故较大根大于一。由 0≤L(s)≤1,只能取所写的较小根。
令 s↓0,单调收敛定理给出 L(s)↑Pr(B<∞),于是得到上述最小值。若 λ<μ,对明确根式求导,得 −L′(0+)=(μ−λ)−1。再利用 (1−e−sB)/s 随 s↓0 单调增加,便得到期望。若 λ=μ,右导数的负值为无限大,故虽然清空几乎必然发生,平均时间仍无限。若 λ>μ,永不清空有正概率,期望也为无穷大。
证明透视
为什么不能只解二次方程?
证明分两个阶段,需要小心的是第二阶段。
- 首步方程用到第一事件的竞争指数时钟,并以正状态的平移对称性及强马尔可夫性,把从二到零的时间写成两个独立的 B 之和。约定 e−s∞=0 使方程在 B=∞ 有正概率时仍然成立。
- 在 s=0,二次方程的根为 1 及 μ/λ;到达较快时两者都落在 [0,1],所以代数根不一定是真实事件的概率。关键一步是在 s>0 下处理:对 f(L)=λL2−(λ+μ+s)L+μ 有 f(0)=μ>0、f(1)=−s<0,故 [0,1] 内恰有一个根。
- 之后令 s↓0,单调收敛确定 Pr(B<∞),并通过 (1−e−sB)/s↑B 确定期望。
论证最后把三种情形分开:繁忙期无限、繁忙期有限但期望无限,以及繁忙期有限且期望有限。
若起初有有限的 n 人,人数必依次经过 n−1,n−2,…,0。同一首次到达论证给出变换 L(s)n 和最终清空概率 min(1,μ/λ)n。当 λ<μ 时,平均清空时间是 n/(μ−λ)。
数值例子
例题 3.7.3
(每小时一名到达,平均可服务两名)
令 λ=1、μ=2,时间单位为小时。此时 ρ=1/2,繁忙期几乎必然结束,平均长度为一小时。其变换为
L(s)=23+s−(3+s)2−8.对二次方程求两次导数,得 EB2=4 平方小时及 Var(B)=3 平方小时。平均繁忙期是平均服务时间 1/2 小时的两倍,因为服务期间的到达延长了工作。若开始时有三人,平均清空时间是三小时,而非一小时。
该例的二阶矩来自一个一般公式;它表明仅看平均值可能掩盖拥挤程度。
例题 3.7.4
(平均繁忙期相同,波动却大不相同)
把 λL2−(λ+μ+s)L+μ=0 对 s 求导:L′(2λL−λ−μ−s)=L。当 λ<μ,代入 s=0 及 L(0)=1,得 L′(0)=−1/(μ−λ)。再求导一次并令 s=0,
L′′(0)(λ−μ)=2L′(0)−2λL′(0)2=−(μ−λ)22μ,EB2=L′′(0)=(μ−λ)32μ.λ=1,μ=2 时得 4,与上例一致。λ=9,μ=10 时平均繁忙期仍是 1/(10−9)=1 小时,但 EB2=20、Var(B)=19;一个繁忙期的平均服务人数由 2 升至 1/(1−0.9)=10。
在临界负载下,同一变换仍决定行为,只是零处的导数为无穷大。
例题 3.7.5
(临界负载:必然清空但平均时间无限)
取 λ=μ=1。此时 (2+s)2−4=s2+4s,且
L(s)=22+s−s2+4s,L(0+)=1,所以繁忙期几乎必然结束。至于期望,(1−e−sB)/s 随 s↓0 递增到 B,而
s1−L(s)=2ss2+4s−s=21+4/s−1→∞.由单调收敛,EB=∞。由于 ρ=1,下面的平稳定理也表明不存在平稳概率。
一次服务的平均长度为 1/μ,该段时间的平均到达人数为 λ/μ。把这些到达者视为该次服务的子代,把他们服务时的到达者视为下一代,如此类推。对上一有限代作条件化,再利用独立的服务时间与泊松增量,各代期望人数依次是 1,ρ,ρ2,…。当 ρ<1,由单调收敛,整个繁忙期平均服务人数为 1/(1−ρ)。例子中的答案为二;这是随机总人数的期望,并不是说每次必定服务两人。
概念视角结构
服务人数是一个家族的大小
改为计算顾客人数而非时间。在一次速率为 μ 的指数服务期间,到达人数为 k 的概率是 λ+μμ(λ+μλ)k,各次服务之间相互独立。因此一个繁忙期内服务的人数 N,正是以这一几何后代分布为规律的分枝过程的家族总人数;G(z)=EzN 满足 G=zμ/(λ+μ−λG),即
λG2−(λ+μ)G+μz=0,与繁忙期方程形式相同的二次方程。平均后代数为 ρ,所以 ρ<1 同时支配家族大小与繁忙期。
平稳分布是另一个问题
队长链恰在 ρ<1 时有平稳概率分布;此时分布唯一,且
πn=(1−ρ)ρn,n≥0,EπX=1−ρρ.
当 ρ<1,所写的概率总和为一,并满足各相邻状态的流量平衡 πnλ=πn+1μ,包括零状态在内的每个状态均有流入等于流出。有界速率生成元的均匀化构造因此给出连续时间转移半群下的不变性。
反过来,任何平稳概率在零状态满足 π0λ=π1μ。再用状态一的平衡方程得到 π1λ=π2μ,归纳可知 πn=ρnπ0。若 π0=0,所有项均为零;否则只有 ρ<1 才可求和。归一化强制 π0=1−ρ,亦证明唯一性。对几何级数求导即得均值。
平稳分布下空系统所占概率是 π0=1−ρ,繁忙概率是 ρ。它们是平稳分布下的长期状态概率,与“现在开始的一个繁忙期最终是否结束”不同。上例的平稳平均人数为一,而新繁忙期的平均长度是一小时;两个数值相同只是巧合,单位也不同。
公式 EB=1/(μ−λ) 只对 λ<μ 推导。λ>μ 时它是负数,不可能是平均值;λ=μ 时它没有定义。两种情形下广义期望都是无穷大。
临界及超临界两种情形说明,若把最终清空当作稳定的定义,会出现什么问题。
反例模式
必然返回不代表平均返回时间有限
取 λ=μ=1,繁忙期以概率一结束,但平均长度无限,亦不存在平稳概率。若只因最终会清空就称系统“稳定”,便会遗漏这两点。取 λ=2,μ=1,由一人开始的清空概率只有 1/2,其余路径永远不达零。两种情形都由同一首次事件方程得到,但必须选对解。
练习与解答
快速检查
(设 λ=3、μ=5,单位为每小时。求从两人开始的清空概率及平均时间。)
解答 · 答案
因 3<5,清空几乎必然发生。两段向下首次到达时间的平均各为 1/(5−3) 小时,所以总平均为一小时。两个速率同乘一个正数不改变清空概率,但各段时间都除以该数。
快速检查
(设 λ=4、μ=2。从三人开始,最终清空的概率是多少?从一人开始,无条件平均繁忙期是多少?)
每次向下一级成功的概率是 min(1,μ/λ)。
解答 · 答案
每次向下一级成功的概率为 μ/λ=1/2,三段依次成功的概率是 (1/2)3=1/8。从一人开始,永不清空的概率为 1/2,故广义期望为无穷大。1/(μ−λ)=−1/2 是负数,不可能是平均时间;这里不满足次临界公式的条件。
练习 3.7.7
(当 λ>μ 时,求 E[B∣B<∞]。)
核心
解答(3)
1以清空为条件的变换
此时 q=Pr(B<∞)=μ/λ<1,且 E[e−sB∣B<∞]=L(s)/q。
2在零处对根式求导
关键一步
L′(s)=(1−(λ+μ+s)/(λ+μ+s)2−4λμ)/(2λ),所以 −L′(0+)=μ/(λ(λ−μ))=q/(λ−μ)。
依据: λ>μ 时,s=0 处 (λ+μ)2−4λμ=λ−μ。
3除以清空概率
E[B∣B<∞]=1/(λ−μ)。这个条件平均有限,无条件广义平均却是无穷大;无条件计算仍不能忽略永不清空的事件。
快速检查
(在 λ=1,μ=2 的例子中,求平稳时至少两人的概率,以及从一人开始的繁忙期平均服务人数。)
解答 · 答案
平稳几何分布的尾概率为 n≥2∑(1/2)(1/2)n=1/4。按上面的代际计数,繁忙期平均服务人数是 1/(1−1/2)=2。前者是平稳时刻的概率,后者是整段随机时间内的总人数。
本节范围
上述分析使用独立泊松到达、独立指数服务时间及一名持续工作的服务员。一般服务时间、顾客等待时间分布、有限容量系统和到达时刻的抽样都需要进一步论证。