Skip to content

定理Theorem

Blackwell 更新定理

Blackwell renewal theorem

在有限平均间隔及非格点条件下,远处固定时间窗的期望更新数趋于窗长除以平均间隔。

形式陈述 ​

知道前 t 个时间单位平均发生多少次更新,还不能知道远处一个固定小窗口内平均发生多少次。Blackwell 更新定理专门回答后一个问题。

设更新过程的独立同分布正间隔分布为 F,μ=EX∈(0,∞),以期望定义 m(t)=EN(t)。称 F 为非格点分布,若不存在 d>0 使 P(X∈{d,2d,3d,…})=1。在非格点条件下,对每个固定 h>0,

m(t+h)−m(t)=E[N(t+h)−N(t)]⟶hμ.

若间隔取值于 dN,且 d 是最大格距,则改用格点版本:更新质量 un=P(某个更新发生在 nd) 满足 un→d/μ。这里严格正间隔保证同一时刻不会有多次更新;等价地,m((n+1)d)−m(nd)→d/μ。

注意“非格点”不等于“有密度”。例如间隔只取 1 与 2 且两者概率均正,也没有共同格距,属于非格点情形。

直觉

EN(t)/t→1/μ 是把从零开始的巨大窗口平均化。Blackwell 定理则让窗口保持固定大小,只把它推向远方。系统何时启动的影响逐渐消退,固定窗口看到的平均更新密度才成为 1/μ。

不能对 m(t)∼t/μ 直接作差或求导来证明局部结论。一个远小于 t 的余项仍可能在相邻时间窗之间振荡,而一般更新函数甚至没有导数。

证明机制与它的适用范围 ​

一个直观的证明路线先构造平衡延迟更新过程:首次等待取分布 Fe(x)=μ−1∫0xP(X>s)ds,以后的间隔仍服从 F。它在任意长度 h 的窗口内期望更新数恰为 h/μ。接着比较普通过程与这一平衡过程,证明起点差异对远处窗口的影响趋零。

若 F 有密度且失效率夹在两个正常数之间,可以用同一条速率足够大的Poisson 候选时钟,通过各自失效率决定是否接受候选点。平衡首次等待的失效率也有相同的上下界:其失效率为 P(X>x)/∫x∞P(X>u)du,由原生存函数在 x 之后的指数上下界即可得到。给候选点配相互独立、且独立于时钟的均匀标记,并让两过程共用这些标记,两者共同接受的概率至少为失效率下界除以候选速率。共同接受点出现后,让以后间隔相同,便完成耦合;若上下界为 0<c1≤hF,hFe≤c2,可取候选速率 c2;标记不超过 c1/c2 的候选必被两者接受,所以相遇时间 τ 满足 P(τ>t)≤e−c1t。相遇以后窗口计数相同;相遇前每条计数都不超过候选计数,而 (t,t+h] 的未来候选与 {τ>t} 独立,故两窗口计数的期望差绝对值至多 2c2he−c1t。一般非格点分布可能没有这样的时钟耦合,完整证明还需更新测度的逼近论证。这个加强假设下的机制说明了结论的原因,但不能冒充所有非格点情形的完整证明。

例子与边界

若间隔为速率 λ 的指数分布,m(t)=λt,所以每个窗口的期望次数已经精确等于 λh=h/μ,无需等到远处。若间隔为两个独立速率 λ 指数时间之和,平均周期为 2/λ,定理给出的远处长度 h 窗口期望为 λh/2;这并不使该窗口计数变成 Poisson 分布。

反例取 X≡2、h=1。当 t=2n,(t,t+1] 内没有更新;当 t=2n+1,窗口内恰有一次。期望因此在 0 与 1 之间振荡,并不趋于 1/2。与此同时 N(t)/t→1/2 完全成立,明确区分了局部与全局结论。若改取 h=2,每个窗口恰有一次更新,与格点版本吻合。

固定 h 也不可偷偷换成随 t 缩小的 ht。定理没有宣称 [m(t+ht)−m(t)]/ht→1/μ,更没有在没有密度时给出逐点更新密度。

推论与应用

将一般响应函数切成小区间上的阶梯函数,每块贡献由本定理控制,再对尾部给出统一估计,可以得到关键更新定理。这一步需要响应函数的直接 Riemann 可积性,不能仅把无限多个窗口极限相加。

参考资料
关系图谱15 个相邻概念 · 2 类关系

拖动节点调整位置。

显示关系

显示:依赖

  1. 前置三跳
  2. 前置二跳
  3. 前置一跳
  4. 当前条目
  5. 后续一跳
  6. 后续二跳
  7. 后续三跳
文字版关系按与当前条目的最短距离分组
类型化关系