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 的余项仍可能在相邻时间窗之间振荡,而一般更新函数甚至没有导数。

一般非格点情形:先证明能靠近,再比较窗口 ​

下列论证只用 EX<∞,不假定密度或二阶矩。先取一个普通更新点列 T0=0,T1,…,以及独立的平衡延迟点列 T0′=D,T1′,…;D∼Fe,以后两列的间隔都服从 F。平衡点列在任意长度 h 的窗口内平均有 h/μ 个点。

为何两列能任意靠近。 每一步各抛一枚独立公平硬币;正面时该列向前走一个新间隔,反面时原地等待。两列当前位置之差,是从 −D 出发的随机游走,其 IID 增量分布为

Y=ηX−η′X′,

其中四个变量相互独立,X,X′∼F、η,η′∼Bernoulli(1/2)。有 E|Y|<∞、EY=0;增量支撑对称,并包含 F 支撑的正、负两份。非格点假设使它们生成的闭加法群为整条实线,而非某个 dZ。

这里真正需要的是 Chung–Fuchs 的邻域常返论证,不是“零均值必然跨零”这句直觉。写 Wn=Y1+⋯+Yn,G(r)=∑n≥0P(|Wn|<r)。把 (−mr,mr) 切成 2m 个长为 r 的半开区间,按首次进入各区间的时刻分解;之后再落入同一区间,位移必小于 r。IID 未来增量和Tonelli 非负换序给出

G(mr)≤2mG(r),m≥2.

另一方面,大数律给 Wn/n→0。对任意 A>0,

G(r)≥12m∑n≤⌊Am⌋P(|Wn|<nr/A)⟶A2.

所以每个 r>0 都有 G(r)=∞。

还须从无穷期望访问次数得到几乎必然常返。固定整数 K≥1,令 qK=P(|Wn|≥2r 对所有 n≥K)。事件“|Wj|<r,且从 j+K 起不再进入 (−r,r)”在一条路径上至多发生 K 次;由未来增量独立,其概率至少为 P(|Wj|<r)qK。求和得 K≥qKG(r),故 qK=0。对所有 K 取交,并把 r 换成 r/2,便得反复返回原点任意邻域。对任意可达的目标邻域,每次回到足够小的原点邻域后,再尝试一条到达目标的有限增量路径;成功概率有一个正常数下界。依次在不重叠的尝试后重启,全部失败的概率至多为 (1−p)k→0。支撑生成的群稠密,故每个实数目标邻域都可达。从随机起点 −D 出发时,先给定 D,再对其分布积分即可。

因此,对任意 ε>0,几乎必然在有限步找到两个更新点 TJ,TK′,满足 |TJ−TK′|<ε。这个选择是上述逐步探索的停时;对停时的每个整数值分解,未使用的间隔仍是独立的 F 样本。保留普通列直到 TJ,之后改用平衡列在 TK′ 之后的间隔,得到与原普通列同分布的新列 T″。两列此后保持同一个小于 ε 的时间差;这是一种近似耦合,不要求连续分布的更新点精确相遇。

为何能够取期望。 对普通或任意独立延迟的更新列,任意长度 L 的窗口计数 Q 在首次窗口内更新以后重新开始,所以

P(Q≥k)≤P(Sk−1≤L)≤eθLak−1,a=Ee−θX<1.

最后一步是更新方程中的局部有限性估计。这个不随窗口位置改变的几何尾界,保证 supE[Q1{Q>M}]→0。因而若坏事件 Bt 的概率趋零,则

E[Q1Bt]≤MP(Bt)+E[Q1{Q>M}]⟶0

(先令 t→∞,再令 M→∞)。这里不要求坏事件与窗口计数独立。

令 0<2ε<h。在 TJ≤t 时,平衡列在 (t+ε,t+h−ε] 中的点都对应于新普通列在 (t,t+h] 中的点;后者又都对应于平衡列在 (t−ε,t+h+ε] 中的点。坏事件 {TJ>t} 概率趋零,故上面的统一尾界给

h−2εμ≤lim inft→∞E[N(t+h)−N(t)]≤lim supt→∞E[N(t+h)−N(t)]≤h+2εμ.

再令 ε↓0,得到一般非格点结论。整个证明没有把随机窗口的路径接近直接当作期望接近。

格点版本。 缩放成正整数间隔 Z=X/d,ν=EZ,最大格距等价于支撑的最大公因子为 1。取独立首次延迟

P(D=j)=P(Z>j)ν,j=0,1,….

其总质量为一。延迟列在整数 n 处出现更新的概率 vn 满足

vn=P(D=n)+∑j=1nP(Z=j)vn−j.

从 v0=1/ν 归纳得 vn=1/ν。同样的懒步差游走现在在 Z 上常返,支撑生成整个 Z,故可以精确相遇;相遇后共用间隔。两个更新指标之差的绝对值至多为尚未相遇的事件指标,于是 un→1/ν=d/μ。这里没有给原来固定相位的格点过程擅自增加连续随机相位。

有界失效率下更直接的机制 ​

若 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 可积性,不能仅把无限多个窗口极限相加。

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

拖动节点调整位置。

显示关系

显示:依赖

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