形式陈述
反复重启的系统通常有两部分贡献:第一次重启以前的贡献,以及重启以后的一份同类问题。更新方程把这次分解写成可以求解的等式。
设 F 是更新间隔 公理库 更新过程 Renewal process 用独立同分布的正间隔构造到达时刻,再由到达时刻反演更新次数。 的分布,间隔严格为正。给定 Borel 可测且局部有界函数 g : [ 0 , ∞ ) → R ,考虑未知的 Borel 可测且局部有界函数 z 满足
z ( t ) = g ( t ) + ∫ ( 0 , t ] z ( t − s ) d F ( s ) . 这里 d F 表示对间隔分布积分;只有 F 有密度 f 时,才可以改写成 f ( s ) d s 。定义更新测度 U = ∑ n ≥ 0 F ∗ n ,其中 F ∗ 0 = δ 0 ,则唯一的局部有界解为
z ( t ) = ∫ [ 0 , t ] g ( t − s ) U ( d s ) = ∑ n ≥ 0 E [ g ( t − S n ) 1 { S n ≤ t } ] . 有限区间上 U 有限,所以局部有界的 g 保证级数绝对收敛。一个核验办法是选 θ > 0 :a = E e − θ X 1 < 1 ,对非负变量 e − θ S n 使用Markov 不等式 公理库 Markov 不等式 Markov's inequality 非负随机变量超过阈值的概率由其期望除以阈值控制。 ,得到 P ( S n ≤ t ) ≤ e θ t a n ,其和有限。
直觉
卷积中的 s 是第一次更新消耗的时间,t − s 是留给新副本的时间。g ( t ) 则必须由具体问题确定,不能看到更新过程就一律填入 F ( t ) 。计数、可用概率与剩余寿命问题的重启机制相同,第一次重启前的贡献却不同。
解中的第 n 项代表经历恰好 n 次重启后,仍在观测范围内的那份初始贡献。逐次展开递推,能看见“从第一次重启递推”怎样变成“汇总所有重启时刻”。
迭代为什么给出唯一解
把方程右侧的 z 连续代回 k 次,得到前 k 项之和加余项 F ∗ k ∗ z 。固定 T ,余项在 0 ≤ t ≤ T 上的绝对值至多为 sup u ≤ T | z ( u ) | P ( S k ≤ T ) ,随 k → ∞ 消失。任何局部有界解都必须等于同一个级数;反过来,绝对收敛允许重新组合级数,核验它确实满足方程。
例子与边界
以更新计数的期望 公理库 期望 Expectation · Expected value 实值或复值随机变量关于概率测度的 Lebesgue 积分,概括加权平均与总体质量平衡。 m ( t ) = E N ( t ) 为例,按首次间隔使用全期望公式 公理库 全期望公式与全方差公式 Law of total expectation · Law of total variance · Iterated expectation 借助条件信息分解总体均值,并把总波动拆成组内与组间两部分。 。若 X 1 > t ,计数为零;若 X 1 = s ≤ t ,已有一次更新,之后的期望计数为 m ( t − s ) 。因此
m ( t ) = F ( t ) + ∫ ( 0 , t ] m ( t − s ) d F ( s ) , m ( t ) = ∑ n ≥ 1 F ∗ n ( t ) . 取 P ( X = 1 ) = P ( X = 2 ) = 1 / 2 ,并将 m ( t ) 在负数上补为零。递推给出 m ( 0 ) = 0 、m ( 1 ) = 1 / 2 ,接着
m ( 2 ) = 1 + 1 2 m ( 1 ) + 1 2 m ( 0 ) = 5 4 , m ( 3 ) = 1 + 1 2 m ( 2 ) + 1 2 m ( 1 ) = 15 8 . 这是一项实际可执行的计算:每个整数时刻只需已有的前两项。若计算到非负整数 T ,只需 O ( T ) 次算术运算,并保存 O ( 1 ) 个有理数。精确分子、分母的位数会随 T 增长,位运算成本与存储位数还须另计。
对交替工作与维修设备,设完整周期向量 ( A n , B n ) 独立同分布,A n , B n ≥ 0 、P ( A n + B n > 0 ) = 1 ,周期内允许相关。一个周期为工作时间 A 加维修时间 B ,其总长分布为 F ,零时刻开始工作。令 时 刻 正 常 工 作 z ( t ) = P ( 时刻 t 正常工作 ) ,则首次周期中的贡献是 g ( t ) = P ( A > t ) ,不是 P ( A + B ≤ t ) 。于是同样的方程求的是可用概率,不再是计数。
若间隔恒为零,则递推变成 z = g + z ,一般无解;严格正间隔在此排除了零时刻无穷次重启。仅写一个形式上的 Laplace 变换商,也不能绕过解的函数类别、积分收敛和初值约定。
推论与应用
有限时间可以通过级数、递推或适用的变换求解;长期极限则交给关键更新定理 公理库 关键更新定理 Key renewal theorem 以直接 Riemann 可积性控制尾部,把局部更新极限推广到更新卷积的长期极限。 ,它需要非格点和直接 Riemann 可积等额外条件。方程解存在并不自动意味着 z ( t ) 有极限,确定长度周期就可能保留周期振荡。
参考资料