变点检测的运行长度证书 ​

这组任务不是“画出一条看起来会报警的曲线”。你的交付物要让别人检查：统计量是否算对，阈值是否包含等号，正常模型是否满足似然预算，平均等待与指定时域的误报概率分别是多少。每个任务都给出小输入、完整计算和必须明确写下的边界。

返回学习路线。先读 CUSUM 变点检测理路CUSUM 变点检测CUSUM change detection · Page CUSUM · 累积和变点检测对所有可能的改变起点取最大似然比，用可重置递推监测分布变化，并以运行长度而非无限期错误概率校准阈值。 与 Shiryaev–Roberts 变点检测理路Shiryaev–Roberts 变点检测Shiryaev–Roberts detection · Shiryaev-Roberts procedure · SR 变点检测 · Generalized Shiryaev–Roberts procedure对每个可能改变起点的似然比求和，以带新增单位预算的递推监测变化，并通过有界停止证明平均误报等待下界。。下载 标准库精确程序 和 发布的检查结果。程序使用 Fraction，不靠模拟精度或浮点容差解释等号。

任务一：把最大后缀、反射递推和有限链对上 ​

输入。 正常成功概率 $p_0=1/3$，改变后 $p_1=2/3$；观察到

令阈值 $A=8$，第一步前统计量为零。用下标 $\nu =5$ 表示“从第五步起改变”；不要误写成第五步仍属于正常段。

计算与交付。 成功和失败的似然比分别为 $2$、$1/2$。逐步列出未垫底的后缀最大值 $V_n$ 和以 $\log 2$ 为单位的反射统计量 $C_n$：

直接枚举每个 $n$ 的所有后缀积，应得到同一个 $V$；递推应满足 $V_n=max(1,V_{n-1})L_n$，而 $e^{C_n}=max(1,V_n)$。前两步已经说明，不能把后两者直接认成一个数。

累计整数增量为 $(-1,-2,-1,-2,-1,0,-1,0,1)$。扣去包括初值零在内的历次最小值，可再次得到 $C/\log 2$。在第九步达到阈值；改变后观测数为 $9-5+1=5$。累计和最小值最后一次出现在第四步，所以约定取最后最小点时，候选起点也是第五步。这只是这条数据上的最大似然定位，不是置信结论。

报警前只有状态 $0,1,2$。写出

从每个状态出发，三步全成功的概率至少为 $p^3$，从而 $\Vert Q^{3k}{\Vert }_{\mathrm{\infty }}\le (1-p^3{)}^k$。这先证明有限吸收与可逆性，再解出正常均值 $(33,30,21)$ 和改变后均值 $(51,39,21)/8$。只写线性求解器返回值而不说明为何是等待均值，交付不完整。

必须解释的边界。 路径上实际用了五个改变后观测，不应和随机重复实验的平均 $51/8$ 混为一谈。这个值也不是对所有检测规则的最优性证明。

任务二：把平均等待与错误概率分开 ​

输入。 继续使用任务一的模型，先从零开始监测十步，再把阈值改为 $16$。

计算与交付。 对 $A=8$，把初始行分布 $(1,0,0)$ 乘 $Q(1/3)$ 十次，求所有暂态概率之和。结果为

另用所有 $2^{10}$ 条二进制路径和各自的精确概率求和，核对同一个事件；不能把“第十步的统计量超过阈值”当成“十步内曾报警”，因为越界后若继续计算，统计量还可能下降。

将不重叠的三步块全成功事件用于证明 ${\mathbb{P}}_{\mathrm{\infty }}({\tau }_8<\mathrm{\infty })=1$。再说明这个结论如何与平均等待 $33$ 相容。把阈值 $8$ 解释成无限期错误概率 $1/8$，应判为错误报告。

用同一串未来增量耦合两个不同初值，较高状态不会晚报警。因此改变后从状态 $0,1,2$ 出发的均值以零状态最大，最坏历史条件延迟为 $51/8$；$\nu =1$ 达到此值，已经提前误报的历史则给零延迟。

现在 $A=16$，需要四格才报警。重新建立四状态链，而不是把旧均值简单乘二。正常和改变后均值分别为

报告零初值正常均值从 $33$ 变为 $78$，最坏历史延迟从 $51/8$ 变为 $147/16$。若改变前状态已经为一，改用相应第二个分量。

必须解释的边界。 SR 预算给出的 ${\mathbb{E}}_{\mathrm{\infty }}{\tau }_A\ge A$ 是保守下界；$A=8$ 时的有限时域粗界 $min(1,10/8)=1$ 没有信息，不能代替矩阵算出的准确概率。不同阈值的实际误报等待需要重新校准。

任务三：让等号和 headstart 真正改变答案 ​

输入。 正常时成功概率 $1/2$，改变后成功概率一；成功因子 $2$，失败因子零。比较 SR 的 $(A,r)=(6,0),(6,2),(13/2,0)$，以及零初值 CUSUM 的 $A=6$。

计算与交付。 SR 连续成功时的值依次为 $2,6,14,30,\dots$，一次失败清零。对于 $A=6$，零初值的暂态矩阵为

（状态顺序 $0,2$）。解出 $(v_0,v_2)=(6,4)$。初值 $r=2$ 只是从第二个状态开始，因此平均等待 $4$，恰好等于 $A-r$。若程序按自己的广度优先状态顺序列成 $(2,0)$，应同时置换行列和均值，不能拿不同顺序的向量直接比较。

当 $A=13/2$，值 $6$ 还未过线，需要连续三次成功，平均等待 $2+4+8=14$。同样的 $14$ 适用于所有 $6<A\le 14$。在 $A=6$ 本身只需两次成功，平均为六；这里的端点必须写清楚。

CUSUM 最大后缀则依次是 $2,4,8$，所以 $A=6$ 时平均等待也是 $14$。给出表述：“相同阈值下两种规则的正常平均等待不同”，不能仅凭 SR 更早报警就说它在同一个误报要求下更好。

预算证书。 对任意有限 $N$，枚举到第 $N$ 步的路径，验证

这一步冻结已经报警路径上的读数。不要直接取最后时刻 $R_N$，也不要在没有尾部条件时把有界停时删掉。上述有限状态均值另由正概率成功块和首步方程给出。

任务四：核对固定预算、随机读取和模型失配 ​

输入。 先用任务三的正确模型，再让真实正常成功概率变为 $3/5$。

计算与交付。 给起点预先分配 ${\pi }_k=2^{-k}$。混合证据必须写为

最后一项保留尚未启动的质量。前三步全成功时，SR 依次为 $(2,6,14)$，$B$ 为 $(3/2,11/4,43/8)$。对每个可达历史，按正常的两个下一步概率精确加权，核对 $\mathbb{E}[B_{n+1}\mid {\mathcal{F}}_n]=B_n$。若把两模型设为相同，应得到 $B_n=1$、$R_n=n$；后者仍会在有限阈值报警。

不能因为 $\mathbb{E}(R_n/n)=1$ 就把归一化 SR 当成 e-process。第一步成功就读取，否则第二步读取；对应读数为 $2,1,0$，概率分别 $1/2,1/4,1/4$，所以期望为 $5/4$。请用这个有界停时反例，而非只写“它不是上鞅”。

当真实正常成功概率为 $3/5$ 时，若仍使用 $2,0$，一步均值为 $6/5$。阈值六仍等两次连续成功，平均等待 $40/9<6$；这准确指出一般下界的哪个前提被破坏。用正确因子 $5/3,0$ 后，连续成功的 SR 值依次为

阈值六现在需要三次成功。等待均值 $5/3+25/9+125/27=245/27\ge 6$，重新符合下界。报告中应分别列出错误因子、正确因子、实际规则和实际均值，而非只说结果“保守”。

运行、复核与验收 ​

把程序下载到当前目录后，用两个不同输出文件运行，保留普通和优化结果再比较：

python3 foundations-change-detection-check.py --output change-normal.json
python3 -O foundations-change-detection-check.py --output change-optimized.json
cmp change-normal.json change-optimized.json

程序强制显式给出输出路径，避免审核时覆盖发布结果。两份 JSON 应逐字相同。所有检查都使用显式异常，不依赖会被 -O 删除的 assert。再次导入调用 run() 时会清空计数，重复调用不会累积检查数。

公开程序覆盖非负因子中的零与一、非零 headstart、阈值等号、正确条件预算、保留先验尾质量、有限停时恒等式、状态矩阵与完整有限路径枚举、改变阈值、模型失配以及归一化读取反例。它还拒绝非法正常概率、越界改变后概率、负因子或负初值、非正格高、初值已经达到阈值、没有有限逆证书的奇异系统等输入。

有限路径与有限参数测试不能代替正文中的全范围证明。这里的精确程序也不是连续状态积分方程求解器，不提供未知正常分布下的自动校准、变点置信区间或所有检测器之间的最优性结论。完整交付应包括四项计算、各自前提、输出 JSON，以及对每处失败边界的解释。