Skip to content

方法Method

更新方程

Renewal equation

按第一次更新分解,利用更新测度求解卷积型递推方程。

形式陈述 ​

反复重启的系统通常有两部分贡献:第一次重启以前的贡献,以及重启以后的一份同类问题。更新方程把这次分解写成可以求解的等式。

设 F 是更新间隔的分布,间隔严格为正。给定 Borel 可测且局部有界函数 g:[0,∞)→R,考虑未知的 Borel 可测且局部有界函数 z 满足

z(t)=g(t)+∫(0,t]z(t−s)dF(s).

这里 dF 表示对间隔分布积分;只有 F 有密度 f 时,才可以改写成 f(s)ds。定义更新测度 U=∑n≥0F∗n,其中 F∗0=δ0,则唯一的局部有界解为

z(t)=∫[0,t]g(t−s)U(ds)=∑n≥0E[g(t−Sn)1{Sn≤t}].

有限区间上 U 有限,所以局部有界的 g 保证级数绝对收敛。一个核验办法是选 θ>0:a=Ee−θX1<1,对非负变量 e−θSn 使用Markov 不等式,得到 P(Sn≤t)≤eθtan,其和有限。

直觉

卷积中的 s 是第一次更新消耗的时间,t−s 是留给新副本的时间。g(t) 则必须由具体问题确定,不能看到更新过程就一律填入 F(t)。计数、可用概率与剩余寿命问题的重启机制相同,第一次重启前的贡献却不同。

解中的第 n 项代表经历恰好 n 次重启后,仍在观测范围内的那份初始贡献。逐次展开递推,能看见“从第一次重启递推”怎样变成“汇总所有重启时刻”。

迭代为什么给出唯一解 ​

把方程右侧的 z 连续代回 k 次,得到前 k 项之和加余项 F∗k∗z。固定 T,余项在 0≤t≤T 上的绝对值至多为 supu≤T|z(u)|P(Sk≤T),随 k→∞ 消失。任何局部有界解都必须等于同一个级数;反过来,绝对收敛允许重新组合级数,核验它确实满足方程。

例子与边界

以更新计数的期望 m(t)=EN(t) 为例,按首次间隔使用全期望公式。若 X1>t,计数为零;若 X1=s≤t,已有一次更新,之后的期望计数为 m(t−s)。因此

m(t)=F(t)+∫(0,t]m(t−s)dF(s),m(t)=∑n≥1F∗n(t).

取 P(X=1)=P(X=2)=1/2,并将 m(t) 在负数上补为零。递推给出 m(0)=0、m(1)=1/2,接着

m(2)=1+12m(1)+12m(0)=54,m(3)=1+12m(2)+12m(1)=158.

这是一项实际可执行的计算:每个整数时刻只需已有的前两项。若计算到非负整数 T,只需 O(T) 次算术运算,并保存 O(1) 个有理数。精确分子、分母的位数会随 T 增长,位运算成本与存储位数还须另计。

对交替工作与维修设备,设完整周期向量 (An,Bn) 独立同分布,An,Bn≥0、P(An+Bn>0)=1,周期内允许相关。一个周期为工作时间 A 加维修时间 B,其总长分布为 F,零时刻开始工作。令 z(t)=P(时刻 t 正常工作),则首次周期中的贡献是 g(t)=P(A>t),不是 P(A+B≤t)。于是同样的方程求的是可用概率,不再是计数。

若间隔恒为零,则递推变成 z=g+z,一般无解;严格正间隔在此排除了零时刻无穷次重启。仅写一个形式上的 Laplace 变换商,也不能绕过解的函数类别、积分收敛和初值约定。

推论与应用

有限时间可以通过级数、递推或适用的变换求解;长期极限则交给关键更新定理,它需要非格点和直接 Riemann 可积等额外条件。方程解存在并不自动意味着 z(t) 有极限,确定长度周期就可能保留周期振荡。

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

拖动节点调整位置。

显示关系

显示:依赖

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