标量 Freedman 不等式

Azuma 的幅度预算让每一轮都按最坏波动付费。Freedman 仍保留单步上界，以排除稀有但任意巨大的正跳跃；与此同时，它用给定过去后的真实二阶矩为常见小波动定价。

式(2)把两个条件放在同一个事件里。它不要求整条路径永远满足 $V_k\le v$，只控制方差预算仍未超额时是否越过高度 $t$。一旦预算超过 $v$，这个固定预算证书便不再保护后来的时刻。

从一个实变量不等式开始 ​

对实数 $u$，定义

则 $e^u=1+u+u^{2}h(u)$，且 $h$ 单调递增。因此 $d\le b$、$\lambda \ge 0$ 时，

这个论证也处理任意大的负 $d$，没有在单侧定理的证明里偷偷加入双侧有界。对 $0\le z<3$，利用 $j!\ge 2\cdot 3^{j-2}$（$j\ge 2$）逐项求和，

令 $0<\lambda <3/b$，定义 ${\psi }_b(\lambda )={\lambda }^2/[2(1-\lambda b/3)]$。给定过去取条件期望，线性项消失，于是

一个预算保护所有时刻 ​

固定这样的 $\lambda$，由式(4)逐步相乘可知

是初值1的非负上鞅。非负性和条件期望递推也保证其可积。若某时刻有 $S_k\ge t,V_k\le v$，就有 $L_k\ge e^{\lambda t-{\psi }_b(\lambda )v}$。因此Ville 不等式理路Ville 不等式Ville's inequality · Ville inequality非负上鞅在无限时间内达到给定水平的概率，由初始期望除以该水平控制。给

取确定值 $\lambda =t/(v+bt/3)$；因 $v>0$，它严格小于 $3/b$。代回后指数恰为 $-t^2/[2(v+bt/3)]$，证明式(2)。这里优化的是事先给定的两个数 $t,v$；没有根据观察到的路径临时挑 $\lambda$。

最后核对方便阈值。令 $a=\sqrt{2v\ell }$、$d=2b\ell /3$，则 $t=a+d$，且

所以式(3)确实达到要求的指数。

按过去决定是否继续抽样 ​

设 $Y_i$ 独立服从 Bernoulli$(0.01)$。在看到第 $i$ 次结果之前，依据过去选择 $I_i\in \{0,1\}$，表示是否计入该次观测。令

因为 $I_i$ 在给定过去时已经确定，$\mathbb{E}[D_i\mid {\mathcal{F}}_{i-1}]=0$，并且

规则可以遇到某种历史信号后暂停，也可以一直测量到指定条件出现；只要计入决定先于新结果，鞅条件就保留。

取 $b=0.99,v=9.9,\delta =0.01$，式(3)给

所以以至少99%的概率，在所有 $N_k\le 1000$ 的时刻，计入成功数减去 $0.01N_k$ 都小于上述精确阈值 $t$（约12.5883583）。若恰好计入1000项，则成功数至少23会触发该单侧越界；能否看见这种越界不是保证，假设正确时它在整个预算窗口内发生的概率至多1%。

若忽略小方差，固定1000次的 Hoeffding 单侧计数阈值为 $\sqrt{1000\log 100/2}\approx 47.9853$。这个数用于说明幅度预算可能更粗；它本身只有固定时刻含义，不能不经证明就作为此处任意时刻的竞争边界。

四条路径重算适应过程 ​

把上例改为公平硬币，最多看三次，并在首次正面后不再计入。于是 $I_1=1$，随后仅当此前全为反面时 $I_i=1$。四种终局如下：

加权终局均值为0，虽然后来的增量显然不是独立的。事件“某时刻 $S\ge 0.4$ 且 $V\le 0.25$”仅在第一条路径发生，真实概率为 $1/2$。Freedman 取 $b=0.5$ 给上界

确实覆盖真实概率。公式在这种小预算下较松，不应把上界当成精确尾概率。

看完当前结果才选择，不是可预测 ​

若改成 $I_i=\mathbf{1}\{Y_i=1\}$，仍写 $D_i=I_i(Y_i-p)$，则 $D_i=(1-p)Y_i$，条件均值为 $p(1-p)>0$。只收录成功记录引入了漂移，第一步的鞅条件已经失败。把所得计数代回方差公式不能修复这种选择偏差。

此外，$V_k=\sum _i\mathbb{E}[D_i^2\mid {\mathcal{F}}_{i-1}]$ 不是观测平方和 $\sum _i{D}_i^2$，也不是围绕样本平均的样本方差。它可能含未知参数；实际报告前要有模型下可计算的上界，或在候选参数下构造合法检验。经验 Bernstein理路经验 Bernstein 均值界Empirical Bernstein mean bound · 经验方差均值界对已知有界范围的 IID 观测，以经过校准的样本方差构造固定样本均值区间，解释标准差估计误差、零样本方差与重复查看的边界。用校准后的样本方差，承担的是不同任务。

何时真的可以适应观察到的方差 ​

式(2)没有直接证明 $S_k<t(V_k,\delta )$ 对所有 $k$ 同时成立。要让阈值随随机方差变化，可以提前列出预算并分配错误概率。

固定 $v_0>0$，设 $v_j=2^j{v}_0$，$j=0,1,\dots$，并设

对每个 $j$ 使用式(2)–(3)，再对这些可数事件取并集。令 $j(V)$ 为满足 $V\le v_j$ 的最小非负整数，则以至少 $1-\delta$ 的概率，对所有 $k$，

实际 $V_k$ 可以随机；现在有效性来自整张预算表共同覆盖，不是未经校准地把随机值代入一个固定预算定理。例如 $b=1,v_0=10,\delta =0.05$，观测到 $V_k=13$ 时属于 $j=1$，用 $v_1=20,{\delta }_1=1/120$，阈值为17.0300017。不能仍使用 $v=13$ 和完整的0.05预算冒充同一证明。

若所有增量独立，并采用它们的自然滤过（或另证每个 $D_i$ 与整个 ${\mathcal{F}}_{i-1}$ 独立），则 ${\sigma }_i^2=\mathrm{Var}(D_i)$ 为确定数。在固定时刻 $n$，取 $v=\sum _{i\le n}\mathrm{Var}(D_i)$，式(2)包含该时刻事件并恢复标量 Bernstein理路有界标量 Bernstein 不等式Scalar Bernstein inequality · Bernstein inequality for bounded random variables在已知中心化幅度与方差预算时控制独立标量和，以初等指数矩证明解释两种偏差尺度，并计算罕见事件均值的充分样本量。型界。独立情形的原证明更短；这里新增的是条件方差、适应性和预算内全时间控制。

本页不要求条件对称。若没有幅度界、但有条件对称结构，可考察混合边界的自归一化支路理路混合序贯边界Mixture boundary · Method of mixtures · Normal mixture boundary对指数上鞅作预先固定的概率混合，再把财富阈值反解为对所有时间同时有效的偏差边界。；若既无幅度、也无其他尾部结构，仅有限条件方差不能凭空给指数尾。

自测与答案 ​

1. 在稀有故障例中，把计入读数变成原值的5倍，$b,V,t$ 各如何变化？若要双侧99%保证，对数项怎样调整？
2. $V_k\le v$ 只在某条已观察路径上成立，能否使用式(2)？这是否意味着任意随机 $v=V_k$ 都可直接代入？

答案：第一题 $b$ 乘5，$V$ 乘25，阈值乘5。双侧还要有绝对增量界；原中心化读数可用 $b=0.99$ 的双侧界，因为负幅度0.01较小；总预算0.01时每侧用0.005，对数变为 $\log 200$。第二题式(2)本来就控制偏差与预算的联合事件，因此不要求所有路径满足预算；但数字 $v$ 必须预先固定，随机选择预算需要式(5)这样的共同校准。