形式陈述
知道前 个时间单位平均发生多少次更新,还不能知道远处一个固定小窗口内平均发生多少次。Blackwell 更新定理专门回答后一个问题。
设更新过程理路更新过程Renewal process用独立同分布的正间隔构造到达时刻,再由到达时刻反演更新次数。的独立同分布正间隔分布为 ,,以期望理路期望Expectation · Expected value实值或复值随机变量关于概率测度的 Lebesgue 积分,概括加权平均与总体质量平衡。定义 。称 为非格点分布,若不存在 使 。在非格点条件下,对每个固定 ,
若间隔取值于 ,且 是最大格距,则改用格点版本:更新质量 满足 。这里严格正间隔保证同一时刻不会有多次更新;等价地,。
注意“非格点”不等于“有密度”。例如间隔只取 与 且两者概率均正,也没有共同格距,属于非格点情形。
直觉
是把从零开始的巨大窗口平均化。Blackwell 定理则让窗口保持固定大小,只把它推向远方。系统何时启动的影响逐渐消退,固定窗口看到的平均更新密度才成为 。
不能对 直接作差或求导来证明局部结论。一个远小于 的余项仍可能在相邻时间窗之间振荡,而一般更新函数甚至没有导数。
一般非格点情形:先证明能靠近,再比较窗口
下列论证只用 ,不假定密度或二阶矩。先取一个普通更新点列 ,以及独立的平衡延迟点列理路平稳更新过程Stationary renewal process · Equilibrium renewal process以长度偏倚的跨零周期和均匀相位构造平稳更新点过程,并区分点过程平稳与累计计数平稳。 ;,以后两列的间隔都服从 。平衡点列在任意长度 的窗口内平均有 个点。
为何两列能任意靠近。 每一步各抛一枚独立公平硬币;正面时该列向前走一个新间隔,反面时原地等待。两列当前位置之差,是从 出发的随机游走,其 IID 增量分布为
其中四个变量相互独立,、。有 、;增量支撑对称,并包含 支撑的正、负两份。非格点假设使它们生成的闭加法群为整条实线,而非某个 。
这里真正需要的是 Chung–Fuchs 的邻域常返论证,不是“零均值必然跨零”这句直觉。写 ,。把 切成 个长为 的半开区间,按首次进入各区间的时刻分解;之后再落入同一区间,位移必小于 。IID 未来增量和Tonelli 非负换序理路Tonelli 定理Tonelli's theorem非负可测函数的二重积分与两种迭代积分相等,允许共同取无穷。给出
另一方面,大数律理路强大数定律Law of large numbers · Strong law of large numbers · SLLN独立同分布且可积时,样本均值沿几乎每条无限样本路径收敛到共同期望。给 。对任意 ,
所以每个 都有 。
还须从无穷期望访问次数得到几乎必然常返。固定整数 ,令 。事件“,且从 起不再进入 ”在一条路径上至多发生 次;由未来增量独立,其概率至少为 。求和得 ,故 。对所有 取交,并把 换成 ,便得反复返回原点任意邻域。对任意可达的目标邻域,每次回到足够小的原点邻域后,再尝试一条到达目标的有限增量路径;成功概率有一个正常数下界。依次在不重叠的尝试后重启,全部失败的概率至多为 。支撑生成的群稠密,故每个实数目标邻域都可达。从随机起点 出发时,先给定 ,再对其分布积分即可。
因此,对任意 ,几乎必然在有限步找到两个更新点 ,满足 。这个选择是上述逐步探索的停时;对停时的每个整数值分解,未使用的间隔仍是独立的 样本。保留普通列直到 ,之后改用平衡列在 之后的间隔,得到与原普通列同分布的新列 。两列此后保持同一个小于 的时间差;这是一种近似耦合理路耦合法Coupling method · Probability coupling在共同概率空间中构造具有指定边缘的随机变量,并用它们相遇的概率比较分布。,不要求连续分布的更新点精确相遇。
为何能够取期望。 对普通或任意独立延迟的更新列,任意长度 的窗口计数 在首次窗口内更新以后重新开始,所以
最后一步是更新方程中的局部有限性估计理路更新方程Renewal equation按第一次更新分解,利用更新测度求解卷积型递推方程。。这个不随窗口位置改变的几何尾界,保证 。因而若坏事件 的概率趋零,则
(先令 ,再令 )。这里不要求坏事件与窗口计数独立。
令 。在 时,平衡列在 中的点都对应于新普通列在 中的点;后者又都对应于平衡列在 中的点。坏事件 概率趋零,故上面的统一尾界给
再令 ,得到一般非格点结论。整个证明没有把随机窗口的路径接近直接当作期望接近。
格点版本。 缩放成正整数间隔 ,,最大格距等价于支撑的最大公因子为 。取独立首次延迟
其总质量为一。延迟列在整数 处出现更新的概率 满足
从 归纳得 。同样的懒步差游走现在在 上常返,支撑生成整个 ,故可以精确相遇;相遇后共用间隔。两个更新指标之差的绝对值至多为尚未相遇的事件指标,于是 。这里没有给原来固定相位的格点过程擅自增加连续随机相位。
有界失效率下更直接的机制
若 有密度且失效率夹在两个正常数之间,可以用同一条速率足够大的Poisson 候选时钟理路Poisson 过程Poisson process · 泊松过程以独立平稳的 Poisson 增量描述连续时间到达,并与独立指数间隔相互转换。,通过各自失效率决定是否接受候选点。平衡首次等待的失效率也有相同的上下界:其失效率为 ,由原生存函数在 之后的指数上下界即可得到。给候选点配相互独立、且独立于时钟的均匀标记,并让两过程共用这些标记,两者共同接受的概率至少为失效率下界除以候选速率。共同接受点出现后,让以后间隔相同,便完成耦合理路耦合法Coupling method · Probability coupling在共同概率空间中构造具有指定边缘的随机变量,并用它们相遇的概率比较分布。;若上下界为 ,可取候选速率 ;标记不超过 的候选必被两者接受,所以相遇时间 满足 。相遇以后窗口计数相同;相遇前每条计数都不超过候选计数,而 的未来候选与 独立,故两窗口计数的期望差绝对值至多 。这项指数速度来自额外的失效率上下界。一般非格点分布可能没有这种候选时钟;前面的邻域常返与近似耦合证明不依赖这些加强条件,也不承诺同样的收敛速度。