Shiryaev–Roberts 变点检测

不知道改变从哪一步开始时，可以保留每一个起点的证据。CUSUM 只取这些证据中最大的一个；Shiryaev–Roberts 方法把它们相加。求和并不会让存储量随时间增长，因为旧候选段都乘同一个新因子，新候选段再贡献一个因子即可。

然而，每一步都加入一个新候选段，也意味着每一步都加入新的预算。因此这个和虽然由似然比组成，却不是初始资本固定为一的检验鞅。它自然控制的是平均报警等待，而不是直接给出无限期误报概率。下面把这个预算算清，再用两次连续成功的例子检查阈值、初值和模型失配。

形式陈述

所有起点的证据和

设观测过滤族为 $\mathcal F_n$ 。在已知独立同分布的改变前后模型中，令

L_n=\frac{f_1(X_n)}{f_0(X_n)}\ge0, \qquad L_{k:n}=\prod_{i=k}^n L_i. \tag{1}

假定 $f_1$ 相对于 $f_0$ 绝对连续，于是在始终正常的分布 $\mathbb P_\infty$ 下， $\mathbb E_\infty L_n=1$ 。零似然比允许出现。改变起点 $k$ 是第一个使用 $f_1$ 的观测下标； $L_{k:n}$ 是从该起点改变相对于始终正常的似然比。

零初值的 SR 统计量以及带确定初值 $r\ge0$ 的版本为

R_n^0=\sum_{k=1}^nL_{k:n},\qquad R_0^r=r,\qquad R_n^r=(1+R_{n-1}^r)L_n. \tag{2}

将递推逐步展开即得

R_n^r=rL_{1:n}+\sum_{k=1}^nL_{k:n}. \tag{3}

$1+R_{n-1}^r$ 中的一，正是为“这一刻才改变”新增的起点权重。 $r$ 叫作 headstart，它沿整段 $1{:}n$ 继续积累，不是在每一步都重复加 $r$ 。

给定 $A>r\ge0$ ，定义报警停时

\tau_A^r=\inf\{n\ge1:R_n^r\ge A\}. \tag{4}

初值必须和阈值一起报告。本文不把 $r\ge A$ 的“开始时已经越界”情形混进这个从下一次观测开始的约定。

每一步多出的均值恰好是一

预算论证实际只需要 $L_n$ 非负、 $\mathcal F_n$ 可测，并满足

\mathbb E_\infty[L_n\mid\mathcal F_{n-1}]=1. \tag{5}

独立且模型正确的似然比是一个充分条件。用拟合参数或忽略依赖关系得到的分数，不能只凭无条件平均接近一就假定式 (5) 成立。

从 $R_0^r=r$ 出发，利用非负条件期望和归纳，有

\mathbb E_\infty[R_n^r\mid\mathcal F_{n-1}] =1+R_{n-1}^r, \qquad \mathbb E_\infty R_n^r=r+n. \tag{6}

因此每个 $R_n^r$ 都可积，并且

M_n=R_n^r-r-n \tag{7}

是鞅。是减去持续注入的预算后才成为鞅，不是 $R_n^r$ 本身。

只用有界停止，就能证明平均等待下界

固定正整数 $N$ ， $\tau_A^r\wedge N$ 是有界停时。对式 (7) 使用有界可选停止：

r+\mathbb E_\infty(\tau_A^r\wedge N) =\mathbb E_\infty R_{\tau_A^r\wedge N}^r \ge A\,\mathbb P_\infty(\tau_A^r\le N). \tag{8}

最后一步只用到报警事件上 $R\ge A$ ，未报警事件上 $R\ge0$ 。如果 $\tau_A^r$ 有正概率为无穷，则它的扩展期望已经是无穷；否则右端随 $N$ 趋于 $A$ ，左端由单调收敛得到

\boxed{\mathbb E_\infty\tau_A^r\ge A-r.} \tag{9}

这就是平均误报运行长度的下界。整个证明没有把 $\mathbb E R_\tau=r+\mathbb E\tau$ 当作无条件成立的等式。若要精确使用停止值和越界量，还需要另证停止过程的尾部控制，或像后面的有限模型一样直接解出均值。

式 (8) 同时给出有限时域界

\mathbb P_\infty(\tau_A^r\le N) \le\min\{1,(r+N)/A\}. \tag{10}

当 $N$ 一直增长，这个界会失去作用。它没有把固定阈值变成随时有效的显著性水平。

直觉

可以把每个起点想成一个独立记账的候选解释：“从这里开始，数据已经换成了 $f_1$ 。”下一次观测到来，所有已启动解释都乘 $L_n$ ；还要加上一个刚刚启动的新解释。所以在正常模型下，这些账户的总期望每天增加一，而不是守着一份固定资本。

CUSUM保留最大的候选证据，SR 保留全部候选证据的和。对 $r=0$ 有 $R_n^0\ge V_n$ ，相同数值阈值下 SR 不晚于 CUSUM 报警。这是逐路径比较；如果要比较检测效率，通常应先把两个规则校准到同一个正常平均等待，再比较改变后的延迟。

图中的阶梯来自一个离散模型：阈值在两个可达统计量之间移动时，报警规则完全不变。因而不能假定指定任意一个目标均值，总能靠一个确定性阈值精确达到。

例子与边界

两次连续成功的精确证书

正常时抛公平硬币，改变后每次必定成功。于是成功给 $L=2$ ，失败给 $L=0$ 。从 $r=0$ 出发，连续 $j$ 次成功后的值为

R=2+2^2+\cdots+2^j=2^{j+1}-2; \tag{11}

一次失败就清零。取 $A=6$ ，两个暂态是 $0,2$ ；从 $0$ 成功到 $2$ ，从 $2$ 成功到 $6$ 并报警。若实际成功概率为 $p\in(0,1]$ ， $q=1-p$ ，状态均值满足

v_0=1+qv_0+pv_2,\qquad v_2=1+qv_0. \tag{12}

解得

v_0=\frac{1+p}{p^2},\qquad v_2=\frac1{p^2}. \tag{13}

$p=1/2$ 时，从零开始平均等 $6$ 次；取 headstart $r=2$ ，平均等 $4$ 次，恰好达到 $A-r=4$ 。连续两次成功的块保证几何尾界，所以这个线性解确实是有限的等待均值。

如果把阈值从 $6$ 提到任何 $6<A\le14$ ，从零开始就必须等三次连续成功，均值变成 $14$ 。注意 $A=6$ 属于前一个区间，因为我们的规则是 $R\ge A$ 。若误写成严格大于，同一个输入就会得到不同答案。

在同一数据和 $A=6$ 下，CUSUM 的后缀最大值依次是 $2,4,8$ ，所以它也要三次连续成功，平均等 $14$ 次。SR 的 $6$ 与 CUSUM 的 $14$ 是不同的正常校准，而非相同误报代价下的速度优势。

除以当前时间，也不自动成为 e-process

$r=0$ 时， $\mathbb E_\infty(R_n^0/n)=1$ 对每个固定 $n\ge1$ 都成立。但e-process要求在允许的数据依赖停时读取后仍满足相应期望预算，固定时刻的结论不够。

仍用公平硬币 $L\in\{2,0\}$ 。设一个有界读取规则 $\sigma$ ：第一步成功便在第一步读数，否则在第二步读数。四条等概率的两步路径给出

\frac{R_\sigma^0}{\sigma}= \begin{cases} 2,&\text{第一步成功，概率 }1/2,\\ 1,&\text{先失败后成功，概率 }1/4,\\ 0,&\text{两步都失败，概率 }1/4. \end{cases} \tag{14}

所以 $\mathbb E_\infty[R_\sigma^0/\sigma]=5/4>1$ 。这是一个实际的有界停时反例，直接排除了这套归一化规则的 e-process 有效性。另一方面，若只检查一步条件均值，会发现 $R_n^0<n$ 时

\mathbb E\left[\frac{R_{n+1}^0}{n+1}\mid\mathcal F_n\right] -\frac{R_n^0}{n} =\frac{n-R_n^0}{n(n+1)}>0. \tag{15}

这个计算本身只证明它不是上鞅；比“不是 e-process”弱，不能单独替代式 (14) 的反例。未归一化的 $R_n^0$ 更直接地有均值 $n$ ，当然不是单位初始预算的检验过程。

固定的起点先验必须保留尚未启动的质量

如果希望控制无限期越界概率，可以预先给起点一个真正的概率分布： $\pi_k\ge0$ 、 $\sum_{k\ge1}\pi_k=1$ ，并定义

B_n=\sum_{k=1}^n\pi_kL_{k:n}+\sum_{k>n}\pi_k, \qquad B_0=1. \tag{16}

后半项是还没到来的起点所占的预算，不能删掉。令 $T_n=\sum_{k>n}\pi_k$ 。已启动部分都乘 $L_n$ ，新启动部分 $\pi_n$ 也乘 $L_n$ ，所以

B_n=L_n(B_{n-1}-T_{n-1}+\pi_n)+T_n. \tag{17}

因为 $T_{n-1}=\pi_n+T_n$ ，在式 (5) 下条件期望正好回到 $B_{n-1}$ 。非负性及归纳给出可积性和均值一。也可以把它看作预先固定概率混合：每个起点的过程在启动前值为一，启动后乘相应似然比。于是Ville 不等式真正给出

\mathbb P_\infty\!\left(\sup_{n\ge0}B_n\ge1/\alpha\right)\le\alpha, \qquad 0<\alpha<1. \tag{18}

若 $\pi_k=2^{-k}$ ，则 $T_n=2^{-n}$ 。只要两模型相同，所有 $L_n=1$ ，就有 $B_n=1$ ；反之 SR 的 $R_n^0=n$ ，仍会在 $\lceil A\rceil$ 报警。这把固定总预算与每步新增预算的区别展示得很清楚。式 (16) 也不把 $R_n^0$ 解释为一个已经归一化的后验概率。

正常模型用错了，下界会真正失效

假设硬币实际成功概率是 $3/5$ ，却仍按公平硬币使用因子 $2$ 和 $0$ 。则实际条件均值为 $6/5$ ，式 (5) 不成立。SR 的 $A=6$ 仍在两次连续成功时报警，但其平均等待为

\frac{1+3/5}{(3/5)^2}=\frac{40}{9}<6. \tag{19}

这不是下界证明出了问题，而是输入不再满足预算条件。若改变后仍为必定成功，正确因子应为成功时 $5/3$ 、失败时零。连续两次成功的 SR 值为 $40/9<6$ ，三次时为 $245/27>6$ ；现在要等三次连续成功，平均等待也是 $245/27\ge6$ 。同一个阈值、不同的正确比值，会改变整个报警规则。

推论与应用

有限状态计算可以同时核阈值与初值

把报警前的可达 $R$ 值列出，就得到一个带吸收的有限 Markov 转移。设暂态矩阵为 $Q$ ，在有统一正概率的有限报警块时，均值和存活概率分别由 $(I-Q)^{-1}\mathbf1$ 、 $e_r^\top Q^n\mathbf1$ 给出。用确切可达状态而不是连续近似，可以保留阈值恰好落在 $6$ 或 $14$ 时的区别。

更一般地，成功概率 $p>0$ 时等待 $b$ 次连续成功的零初值均值是

\sum_{j=1}^{b}p^{-j}. \tag{20}

一个简短推导是设已连续成功 $j$ 次的剩余均值为 $u_j$ ， $u_b=0$ ，并写 $u_j=1+p u_{j+1}+(1-p)u_0$ 。向后代入后， $u_0=(1+(1-p)u_0)(1+p+\cdots+p^{b-1})$ ，整理即得式 (20)； $p=1$ 时也直接得到 $b$ 。正概率全成功块保证这些均值有限。

在线 SR 与有递推尾质量的先验混合都只需常数个状态。精确校准仍需另外分析状态空间；一般连续似然下未必有有限的闭合可达集，本页的有限有理数程序不声称解决任意连续模型。

运行长度证书终点要求核对四件不同的事：阈值规则本身、正常模型下预算是否为一、平均报警等待、指定时域的报警概率。它还让你用有界停止反例检查固定时刻归一化，用失配硬币检查模型前提。把这几项分别报告，才不会把平均等待承诺误写成无限期风险承诺。

参考资料

[1] G. V. Moustakides, A. S. Polunchenko, A. G. Tartakovsky, Numerical Comparison of CUSUM and Shiryaev–Roberts Procedures for Detecting Changes in Distributions, 2009 作者版本，§§2.1–2.2 与 §3：两种统计量、校准目标及首次转移方程。

[2] A. S. Polunchenko, G. Sokolov, W. Du, An Accurate Method for Determining the Pre-Change Run-Length Distribution of the Generalized Shiryaev–Roberts Detection Procedure, 2013 作者版本，§2 与 §3.1：headstart、鞅预算、运行长度和存活递推。本文用有界停时推导一般下界，再独立证明离散例子的有限性；不无条件套用无界停止的期望等式或连续数值近似结论。

[3] M. Pollak, A. G. Tartakovsky, On Optimality Properties of the Shiryaev–Roberts Procedure, 2007 作者版本，模型定义与 §2 的先验似然表示。本文的固定概率混合由式 (16)–(18) 直接证明，不调用后续最优性定理。

形式陈述 ​

所有起点的证据和 ​

每一步多出的均值恰好是一 ​

只用有界停止，就能证明平均等待下界 ​

两次连续成功的精确证书 ​

除以当前时间，也不自动成为 e-process ​

固定的起点先验必须保留尚未启动的质量 ​

正常模型用错了，下界会真正失效 ​

有限状态计算可以同时核阈值与初值 ​

反向链接