动机
到达计数把每个事件当作一单位,但数据传输系统常需要另一数量:数据包在随机时刻到达,每包又有随机字节数。事件数与累积负载是不同过程,两者期望均可能随时间线性增加,方差计算却不同,因为负载项的数目本身也随机。
另一个区别在于时钟。指数等待产生泊松(Poisson)过程,但重复的独立周期未必服从指数分布。更新过程保留独立周期结构,同时容许一般等待分布。它把伯努利(Bernoulli)、泊松模型连接到再生论证,也清楚指出哪些结论依赖无记忆性。
以下使用独立可积变量的强大数定律、基本条件化及非负积分。
定义
令 W1,W2,… 独立同分布、严格为正,且几乎必然有限。设 S0=0、Sn=W1+⋯+Wn,以及
NR(t)=max{n≥0:Sn≤t}.对独立同分布的对 (Wn,Yn),完成周期报酬为 C(t)=n=1∑NR(t)Yn。同一对内可相依,例如长周期赚得更多报酬;不同对则须独立。
更新时刻之和几乎必然发散。选 η>0 使 Pr(W1≥η)>0;这些足够长的等待,由独立指示变量的强大数定律可知会出现无限次。因此有限时刻只有有限次更新。若 m=EW1<∞,由严格正性亦知 m>0。报酬可有正负,但其绝对期望须有限。
设 N(t) 为速率 λ>0 的齐次泊松过程。给每个事件配上独立同分布标记 Y1,Y2,…,并独立于整个到达过程。有限类型标记的概率为总和一的 p1,…,pd,各类计数为 Nr(t)。数值标记产生复合过程
Z(t)=k=1∑N(t)Yk,空和为零。数值标记可以是非负负载,也可以是带正负的变化;后者的 Z 未必单调不减。
事件标记不是新事件时刻。零标记不会令 Z 出现可见跳跃,即使到达计数确有跳升。因此只数累积过程的非零跳跃,一般不能还原原始到达速率。
定理/命题
若 m=EW1<∞、E∣Y1∣<∞,则几乎必然有
tNR(t)⟶m1,tC(t)⟶mEY1(t→∞).这些是路径极限,本身不断言相应期望收敛,也不描述尚未完成周期内已赚得的报酬。
独立有限类型标记下,N1,…,Nd 是速率 λpr 的独立泊松过程。数值标记的 Z 有平稳独立增量,且对每个实数 u,
EeiuZ(t)=exp{λt(EeiuY1−1)}.若 E∣Y1∣<∞,则 EZ(t)=λtEY1;若再有 EY12<∞,则 Var(Z(t))=λtEY12。
注意方差公式用标记的二阶矩,而非标记方差。事件数的随机性补上均值平方项。特征函数总是存在,因复指数的绝对值为一;矩母函数则另需指数可积性假设。
证明思路
反转时钟及计算报酬
强大数定律给出 Sn/n→m。由 NR(t)→∞ 及 SNR(t)≤t<SNR(t)+1,除以相应索引并夹逼,得 NR(t)/t→1/m。早期可能有 NR(t)=0,不影响极限。报酬可写为
tC(t)=NR(t)1k=1∑NR(t)YktNR(t).整个报酬序列的强大数定律在概率一的事件上成立,因此沿趋于无限的随机索引亦成立,无须假设 NR(t) 与报酬独立。这正是容许同一周期的长度与报酬相依的原因。
证明透视
随机指标为何不需要独立性
证明有两步。夹逼式 SNR(t)≤t<SNR(t)+1 把以 n 为指标的更新时刻强大数定律,转成以连续时间为指标的叙述:当 NR(t)≥1 时,
NR(t)SNR(t)≤NR(t)t<NR(t)+1SNR(t)+1⋅NR(t)NR(t)+1,两端都趋于 m。这需要 NR(t)→∞,而它来自每个 Sn 几乎必然有限。第二步是逐路径的:报酬平均在整个序列的同一个概率一事件上收敛,因此沿任何趋于无穷的指标,不论是否随机,都会收敛。证明从未使用 NR(t) 与报酬之间的独立性,所以周期报酬可以依赖本周期的长度。假设 m<∞ 只用于确定极限值;若 m=∞,同一夹逼给出 NR(t)/t→0。
另有有限时间方程。若等待分布为 F,M(t)=ENR(t),对首次更新条件化得
M(t)=F(t)+∫(0,t]M(t−s)dF(s).
积分依等待分布进行,故包含原子与确定性等待。为证期望有限,沿用 η,令 p=Pr(W1≥η)>0。当出现 ⌊t/η⌋+1 次这样的等待时,累积时间已超过 t。获得这么多次成功所需试验数的期望为 (⌊t/η⌋+1)/p,并为 NR(t)+1 提供上界。故 M(t) 有限,首次条件化合法。更新方程并未断言其解随时间线性变化。
分开各类计数
在长 t 的时段内给定 N(t)=n,类型计数服从多项分布。对总和为 n 的非负整数 kr,乘上泊松概率得到
Pr(N1(t)=k1,…,Nd(t)=kd)=r=1∏de−λprtkr!(λprt)kr.这分解成独立泊松分布。对多个不相交时段,原增量独立,而各段所属不同事件的标记亦独立。同时使用同一分解,便由有限维分布证明整个类型计数过程互相独立;这比只研究单一时刻提供更多信息。
随机和及其波动
给定 N(t)=n,标记独立给出 EeiuZ(t)=(EeiuY1)n。对泊松级数取平均即得特征函数公式。对不相交时段使用同样条件化,也证明平稳独立增量,标记有负值时亦然。若 b=EY1、s2=Var(Y1) 有限,条件均值及方差为 nb、ns2。全期望及全方差给出
Var(Z(t))=E[N(t)]s2+Var(N(t))b2=λt(s2+b2)=λtEY12.全方差等式可把 Z−EZ 分解为 (Z−E[Z∣N])+(E[Z∣N]−EZ),交叉项的条件期望为零而证。只假设一阶绝对矩时,非负求和给出 Ek=1∑N(t)∣Yk∣=λtE∣Y1∣,先证明绝对可积,再求均值。
概念视角分析
每个事件与每单位时间的平均
平均标记是每事件报酬,到达速率是每时间事件数,相乘才是长期报酬速率。复合泊松方差有两个随机来源:报酬大小及事件次数。量纲可检查计算,条件化才提供证明。
整数负载的有限时间分布计算
非负整数标记的概率母函数不只给矩。写 pj=Pr(Y=j)、G(z)=j≥0∑pjzj、fk(t)=Pr(Z(t)=k),对计数条件化得
Ft(z):=k≥0∑fk(t)zk=exp{λt[G(z)−1]},f0(t)=eλt(p0−1).
0≤z<1 时级数绝对收敛。在内部微分,并在 Ft′(z)=λtG′(z)Ft(z) 比较系数,得到
fk(t)=kλtj=1∑kjpjfk−j(t),k≥1.
右边只有较早概率,故可依次精确计算有限多个负载概率,无须正态近似。单位圆盘内解析幂级数可微分,甚至标记均值无限时亦可比较系数,因每个系数只涉及有限项。初始概率一般不是 e−λt,因零标记不改变总负载。
若每个标记恒为二,p2=1,递推令所有奇数负载概率为零,并给 f2n(t)=e−λt(λt)n/n!,符合 Z(t)=2N(t)。可见累积负载未必在所有非负整数上服从泊松分布;事件数泊松,不代表把跳幅乘二后的总量仍有同一分布形式。
另有两时刻计算。0≤s≤t 且标记平方可积时,写 Z(t)=Z(s)+[Z(t)−Z(s)]。括号增量独立于 Z(s),故
Cov(Z(s),Z(t))=Var(Z(s))=λsEY2.
总量一般相依,即使不相交增量独立。这与普通泊松计数的区别相同,只是如今包含随机跳幅。
零或一标记是有用的模型检查:非零事件形成稀疏化泊松过程,因此累积量确实是较低速率的泊松过程。若有正概率标记大于一,便引入批量跳跃,一般改变分布。只显示总负载的数据表,没有标记规律便不能识别数据包次数。选似然或解读表面到达速率以前,事件时钟及观察规则两者都须交代。
例题详解
数据包以每秒两次到达,各包独立地以概率 3/4 带一负载单位,以概率 1/4 带三单位。则 EY=3/2、EY2=3,在 t 秒后总负载均值为 3t、方差为 6t。若用 λtVar(Y)=2t(3−9/4)=3t/2,便遗漏事件数波动。一单位与三单位数据包计数,分别是速率 3/2、1/2 的独立泊松过程。
令每个 Wk=2、Yk=5 均确定。则 NR(t)=⌊t/2⌋、C(t)=5⌊t/2⌋,长期速率为 1/2、5/2,符合定理。但它不是泊松过程:0.2 至 0.7 之间不可能到达,包含时刻二的长 0.5 时段却有一次。增量不平稳。与速率 1/2 泊松过程有相同平均等待,并不令时钟等价。
只用一枚独立公平硬币决定所有到达的颜色:全部红或全部蓝。固定时刻令 m=λt,则 R+B=N(t)、RB=0,且 ER=EB=m/2,所以 t>0 时 Cov(R,B)=−m2/4<0。各色计数有共同硬币产生的原子,两者并不独立。每次到达各自的红色概率都是 1/2,但相同标记边际并不保证事件间独立标记。
常见错误
反例模式
跨周期共用的报酬破坏报酬定律
声称:同分布且均值有限的报酬总给出长期报酬率 EY1/m,所以周期之间的独立性只是技术细节。取每个 Wk=1,用一枚公平硬币选出 Y∈{0,2},并令所有 Yk=Y。每个 Yk 的均值都是一,所以该声称预测报酬率为一。但 C(t)=Y⌊t⌋,故 C(t)/t→Y,它各以一半概率等于 0 或 2,永远不等于一。平均值不收敛到均值,因为所有报酬共用同一个随机来源。修正就是定理的假设:各对 (Wn,Yn) 在周期之间必须独立;相依只允许出现在同一对之内。
普通更新过程在零时刻开始一次全新等待;在随机选的较后时刻观察,一般得到不同的剩余寿命分布。确定性长度二的等待,其余下时间取决于观察在当前周期的位置。指数无记忆性是特殊性质,并非相邻完整等待独立的结果。本节不宣称一般平衡剩余寿命定理。
报酬定律需要可积性。到达速率有限不会令非负无限均值负载变得可积:固定正时间恰有一次到达的概率已为正,足以令总负载期望无限。
路径极限如 C(t)/t→EY1/m,本身并不给出 EC(t)/t→EY1/m。交换极限与期望需要控制界、一致可积或另一条更新定理。
总结
更新周期把事件速率与特殊指数时钟分开。反转强大数定律得到事件速率,完成周期报酬给出每时间报酬。泊松独立标记分出独立类型过程;复合和保留泊松时刻但加入随机跳幅,方差亦包含事件数不确定性。
练习
快速检查
(更新等待独立,各以相同概率取一或三;每个完成周期赚其长度平方。求长期事件及报酬速率。)
解答 · 答案
平均等待二,平均报酬 (1+9)/2=5,即使同一对内报酬与等待相依也可用定理。速率为每时间 1/2 个事件及 5/2 报酬单位。
快速检查
(速率三的泊松过程,独立标记以概率 1/3 取零、2/3 取二。求 Z(t) 均值、方差及可见跳跃速率。)
方差公式用 EY2,不是 Var(Y)。
解答
EY=4/3、EY2=8/3,故均值 4t、方差 8t。只有非零标记可见,跳跃速率为 3(2/3)=2,大小恒为二;零标记仍是原到达。
快速检查
(速率 λ 泊松过程独立标记为三类,概率 1/2,1/3,1/6。求时刻 t 计数为 (1,0,2) 的联合概率。)
解答 · 答案
类型过程独立给出 e−λt(λt/2)(λt/6)2/2!=e−λt(λt)3/144。第二类零计数提供指数因子,但无正幂项。
快速检查
(等待恒为二,验证 M(t)=⌊t/2⌋ 的更新方程,包括 0≤t<2。)
解答
等待分布在二有单位质量。t<2 时 F(t) 与积分均为零;t≥2 时方程成为 M(t)=1+M(t−2),正是向下取整恒等式。积分范围包含右端点,故包括该原子。