形式陈述
知道前 个时间单位平均发生多少次更新,还不能知道远处一个固定小窗口内平均发生多少次。Blackwell 更新定理专门回答后一个问题。
设更新过程公理库更新过程Renewal process用独立同分布的正间隔构造到达时刻,再由到达时刻反演更新次数。的独立同分布正间隔分布为 ,,以期望公理库期望Expectation · Expected value实值或复值随机变量关于概率测度的 Lebesgue 积分,概括加权平均与总体质量平衡。定义 。称 为非格点分布,若不存在 使 。在非格点条件下,对每个固定 ,
若间隔取值于 ,且 是最大格距,则改用格点版本:更新质量 满足 。这里严格正间隔保证同一时刻不会有多次更新;等价地,。
注意“非格点”不等于“有密度”。例如间隔只取 与 且两者概率均正,也没有共同格距,属于非格点情形。
直觉
是把从零开始的巨大窗口平均化。Blackwell 定理则让窗口保持固定大小,只把它推向远方。系统何时启动的影响逐渐消退,固定窗口看到的平均更新密度才成为 。
不能对 直接作差或求导来证明局部结论。一个远小于 的余项仍可能在相邻时间窗之间振荡,而一般更新函数甚至没有导数。
证明机制与它的适用范围
一个直观的证明路线先构造平衡延迟更新过程:首次等待取分布 ,以后的间隔仍服从 。它在任意长度 的窗口内期望更新数恰为 。接着比较普通过程与这一平衡过程,证明起点差异对远处窗口的影响趋零。
若 有密度且失效率夹在两个正常数之间,可以用同一条速率足够大的Poisson 候选时钟公理库Poisson 过程Poisson process · 泊松过程以独立平稳的 Poisson 增量描述连续时间到达,并与独立指数间隔相互转换。,通过各自失效率决定是否接受候选点。平衡首次等待的失效率也有相同的上下界:其失效率为 ,由原生存函数在 之后的指数上下界即可得到。给候选点配相互独立、且独立于时钟的均匀标记,并让两过程共用这些标记,两者共同接受的概率至少为失效率下界除以候选速率。共同接受点出现后,让以后间隔相同,便完成耦合公理库耦合法Coupling method · Probability coupling在共同概率空间中构造具有指定边缘的随机变量,并用它们相遇的概率比较分布。;若上下界为 ,可取候选速率 ;标记不超过 的候选必被两者接受,所以相遇时间 满足 。相遇以后窗口计数相同;相遇前每条计数都不超过候选计数,而 的未来候选与 独立,故两窗口计数的期望差绝对值至多 。一般非格点分布可能没有这样的时钟耦合,完整证明还需更新测度的逼近论证。这个加强假设下的机制说明了结论的原因,但不能冒充所有非格点情形的完整证明。
例子与边界
若间隔为速率 的指数分布,,所以每个窗口的期望次数已经精确等于 ,无需等到远处。若间隔为两个独立速率 指数时间之和,平均周期为 ,定理给出的远处长度 窗口期望为 ;这并不使该窗口计数变成 Poisson 分布。
反例取 、。当 , 内没有更新;当 ,窗口内恰有一次。期望因此在 与 之间振荡,并不趋于 。与此同时 完全成立,明确区分了局部与全局结论。若改取 ,每个窗口恰有一次更新,与格点版本吻合。
固定 也不可偷偷换成随 缩小的 。定理没有宣称 ,更没有在没有密度时给出逐点更新密度。
推论与应用
将一般响应函数切成小区间上的阶梯函数,每块贡献由本定理控制,再对尾部给出统一估计,可以得到关键更新定理公理库关键更新定理Key renewal theorem以直接 Riemann 可积性控制尾部,把局部更新极限推广到更新卷积的长期极限。。这一步需要响应函数的直接 Riemann 可积性,不能仅把无限多个窗口极限相加。
参考资料