2026-10-17 · 方差预算必须随路径记账

0. 导读与元结构 (Orientation & Meta-structure)

2026 年 10 月 17 日，星期六。 Develata，本期是鞅集中微弧的 3/3，承接前两日的 Azuma–Hoeffding 与 McDiarmid。今天的增量不是再改一个常数，而是改“记账单位”：最坏区间仍然很宽，但大多数步几乎不动，能否只为实际可能产生的条件波动付费？

例如独立 $X_i\sim \mathrm{Bernoulli}(p)$，$p\ll 1$。区间长度恒为 $1$，却有 $\mathrm{Var}(X_i)=p(1-p)$。忽略这个因子，会把稀疏对象按稠密对象估计。

对象分三层：适应信息流的鞅差 $D_i$；过去可知的条件二阶矩；沿路径累加的随机预算 $V_k$。结论先固定两个确定数 $t,v$，再控制“某时刻偏差达到 $t$，同时预算尚未超过 $v$”的概率。这个量词顺序不能偷换为把随机 $V_k$ 直接塞进确定参数。

前置：条件期望、Taylor 余项、有限时域停止。证明引擎：条件指数矩界 → 补偿指数超鞅 → 首次越界 → 参数选择。终点是稀疏图的方差敏感估计；研究生延伸是矩阵鞅与自归一化问题。

1. 核心概念、定理与谱系 (Concept, Theorem & Lineage)

1.1 不是总方差，而是逐步条件方差

在概率空间 $(\mathrm{\Omega },\mathcal{F},\mathbb{P})$ 上，给定滤过 $({\mathcal{F}}_k{)}_{k\ge 0}$。设每个实随机变量 $D_k\in L^2$ 都是 ${\mathcal{F}}_k$-可测的，且

$$\mathrm{\forall }k\ge 1,\mathbb{E}[D_k\mid {\mathcal{F}}_{k-1}]=0\text{a.s.}$$

定义

$$S_0=V_0=0,S_k=\sum _{i=1}^k{D}_i,q_i=\mathbb{E}[D_i^2\mid {\mathcal{F}}_{i-1}],V_k=\sum _{i=1}^k{q}_i.$$

$V$ 称为 $S$ 的可预测二次变差 (predictable quadratic variation)。这里“可预测”指第 $i$ 步的收费 $q_i$ 在 ${\mathcal{F}}_{i-1}$ 下已知，不是说整条未来预算事先确定。尤其 $V_k$ 通常随机；它也不同于已实现平方和 $\sum _{i\le k}{D}_i^2$。

条件正交给出 $\mathbb{E}{S}_k^2=\mathbb{E}{V}_k$。但这个期望等式不允许把尾界中的 $V_k$ 换成 $\mathbb{E}{V}_k$；第 4 节会给出明确失败例。

1.2 留下二阶信息的指数矩引理

设确定数 $R>0$，并且 $D_i\le R$ a.s. 对所有 $i$ 成立。上尾只需要上界，不要求 $D_i\ge -R$。 对任意实数 $x\le R$ 与 $\lambda \ge 0$，积分余项给出

$$e^{\lambda x}-1-\lambda x={\lambda }^2{x}^2{\int }_0^1(1-u)e^{u\lambda x}du\le \frac{x^2}{R^2}(e^{\lambda R}-1-\lambda R).$$

这个写法同时处理负 $x$，避免对带符号幂级数逐项误判。若 $0\le \lambda R<3$，由 $m!\ge 2\cdot 3^{m-2}$（$m\ge 2$）得

$$e^{\lambda R}-1-\lambda R\le \frac{(\lambda R{)}^2}{2(1-\lambda R/3)}.$$

记 $g(\lambda )={\lambda }^2/[2(1-\lambda R/3)]$。取条件期望、消去一次项，再用 $1+y\le e^y$：

$$\mathrm{\forall }i\ge 1,\mathrm{\forall }\lambda \in [0,3/R),\mathbb{E}[e^{\lambda D_i}\mid {\mathcal{F}}_{i-1}]\le e^{g(\lambda )q_i}\text{a.s.}$$

与昨日的 Hoeffding 引理相比，右边保留 $q_i$，代价是出现限制 $\lambda R<3$ 与分母修正。

1.3 Freedman：控制低预算区域内的越界

定理（Freedman 的 Bernstein 型形式）。 在上述全部假设下，对每个确定的 $t>0,v>0$，

$$\mathbb{P}(\mathrm{\exists }k\ge 1:S_k\ge t\text{且}{V}_k\le v)\le \exp [-\frac{t^2}{2(v+Rt/3)}].$$

这正是 [1, Theorem 1.1] 的标量结论；本文额外明确采用平方可积增量，便于所有条件二阶矩无歧义。

证明。 固定 $\lambda \in (0,3/R)$，定义

$$Z_k=\exp \{\lambda S_k-g(\lambda )V_k\},Z_0=1.$$

由于 $q_k$ 对过去可测，上一引理推出

$$\mathbb{E}[Z_k\mid {\mathcal{F}}_{k-1}]\le Z_{k-1}.$$

故 $Z$ 是非负超鞅 (nonnegative supermartingale)。令 $\tau$ 为首次同时满足 $S_k\ge t,V_k\le v$ 的时刻，未发生时置 $\tau =\mathrm{\infty }$。这是停止时刻，因为是否已发生由当前与过去决定。

对每个确定整数 $N\ge 1$，有界停止给出 $\mathbb{E}{Z}_{\tau \wedge N}\le 1$。这一点也可不调用停时定理：展开停止过程的有限个增量，每项乘以过去可测的 $1_{\{\tau \ge i\}}$，其期望都非正。在 $\{\tau \le N\}$ 上，

$$Z_{\tau \wedge N}\ge e^{\lambda t-g(\lambda )v}.$$

所以 $\mathbb{P}(\tau \le N)\le e^{-\lambda t+g(\lambda )v}$。令 $N\to \mathrm{\infty }$，使用事件单调收敛，再选择

$$\lambda =\frac{t}{v+Rt/3}\in (0,3/R)$$

即得所示界。这里是方便的参数选择，不宣称它是此有理函数上界的精确极小点。证毕。

预算版本。 若 $V_n\le v$ a.s.，便有同样的固定时刻上尾界。若没有确定预算，则仍可分解为

$$\mathbb{P}(S_n\ge t)\le \exp [-\frac{t^2}{2(v+Rt/3)}]+\mathbb{P}(V_n>v).$$

尾部控制不能省掉后面一项。若还有 $D_i\ge -R$，对 $-S$ 重复论证得到下尾；仅有上界时不能自动声称对称双尾结论。

1.4 稀疏对象为何受益？

独立 $X_i\sim \mathrm{Bernoulli}(p)$，$0<p<1$，令 $D_i=X_i-p$。此时 $|D_i|\le 1$，且 $V_n=np(1-p)$ 为确定数。于是

$$\mathbb{P}(|\sum _{i=1}^n{X}_i-np|\ge t)\le 2\exp [-\frac{t^2}{2(np(1-p)+t/3)}].$$

当 $t\ll np(1-p)$ 时，分母由方差控制；当 $t$ 很大时，线性项阻止我们不加条件地宣称全尺度高斯尾。这是 Bernstein 型简化界的两种区域，不是对真实尾部的精确渐近断言。

更一般地，令 $X_1,\dots ,X_n$ 独立，$X_i\sim \mathrm{Bernoulli}(p_i)$，其中每个 $0<p_i<1$，并在 $\{0,1{\}}^n$ 上逐步揭示实值函数 $f$，取 ${\mathcal{F}}_i=\sigma (X_1,\dots ,X_i)$。固定前缀后定义

$${\delta }_i=\mathbb{E}[f\mid {\mathcal{F}}_{i-1},X_i=1]-\mathbb{E}[f\mid {\mathcal{F}}_{i-1},X_i=0].$$

未来坐标仍独立，故 Doob 鞅差满足

$$D_i=(X_i-p_i){\delta }_i,q_i=p_i(1-p_i){\delta }_i^2.$$

若全局单坐标敏感度至多 $c_i$，则 $|{\delta }_i|\le c_i$，从而 $|D_i|\le c_i$ 且

$$V_n\le \sum _i{p}_i(1-p_i)c_i^2.$$

取 $R=\underset{i}{max}{c}_i>0$ 即可应用定理；若全为零则 $f$ 恒定，无需尾界。这给出昨日问题的实质答案：条件方差恢复了稀疏参数，而区间宽度本身看不到它。 在随机图边揭示中，这可用于有全局边敏感度的统计量；它并不替代对各统计量敏感度的实际证明。

谱系与研究生延伸。 独立情形预算确定，回到 Bernstein 型集中；Freedman 将方差敏感机制放入鞅框架，[1] 将原始标量结果归于 Freedman（1975）。这里的谱系不是“旧定理被否定”，而是独立性被条件结构替代。Tropp 的矩阵版本用自伴矩阵增量、最大特征值与矩阵条件平方和，并引入维数因子 [1, Theorem 1.2]。其指数矩推进需要 Lieb 凹性工具，不能把标量指数乘法直接照搬到不交换矩阵。

2. 固定模板习题 (Template Exercise)

题目。 沿用平方可积鞅差 $D_1,\dots ,D_N$，但不要求增量有界。设停止时刻 $\tau$ 取值于 $\{0,\dots ,N\}$。证明

$$\mathbb{E}{S}_{\tau }^2=\mathbb{E}{V}_{\tau }.$$

模板识别。 出现“随机上限的平方和”，先将随机上限改成确定上限与示性函数，再检查示性函数在第几层信息中可测；不要直接把确定 $n$ 的等式里的 $n$ 改成 $\tau$。

分级提示。

1. 写出 $S_{\tau }=\sum _{i=1}^N{1}_{\{\tau \ge i\}}{D}_i$。
2. 为什么 $\{\tau \ge i\}\in {\mathcal{F}}_{i-1}$？停止后的增量仍有条件零均值吗？
3. 展开平方。对交叉项先在较晚一步的过去上取条件期望；对对角项再引入 $q_i$。

3. 大家之言 (Mathematician in Their Own Words)

来源语境。 Terence Tao 的第一人称数学研究建议《Learn the limitations of your tools》，发表于其个人网站 What’s new 的 Career advice 栏目 [2]。本次提取正文未提供可靠首发日期，因此不补造日期。以下引文来自正文，不是页首所引他人的题词：

“Thus, knowing a library of counterexamples, or easily analysed model situations, is very important”

中译：“因此，掌握一个反例库，或一批易于分析的模型情境，是非常重要的。”

转述。 Tao 随后区分工具能处理与不能处理的障碍，并主张在使用某工具的论文中也说明它的已知局限。他还提醒：若一个工具只像不可拆解的“魔杖”，使用者可能并未真正理解它。

本期评论。 昨日的朴素追问关心“为什么丢掉区间宽度”；今天更进一步，拿一个可完全计算的随机环境，测试“平均方差是否足够”。这不是用反例否定 Freedman，而是给它画出准确的参数边界。反例的作用是辨认哪类信息不能压缩：把随机预算压成一个均值，会把少量高波动路径藏起来。

所以掌握集中不等式不只是记住指数分母，而是能回答：这个分母里的量，是确定常数、逐路径控制，还是仅仅一个期望？三者对应不同定理。

4. 反例与边界 (Counterexample & Boundary)

错误命题： 在 $|D_i|\le 1$ 的鞅差假设下，固定时刻上尾总可以用 $\mathbb{E}{V}_n$ 代替 $V_n$ 的确定上界，即

$$\mathbb{P}(S_n\ge t)\stackrel{?}{\le }\exp [-\frac{t^2}{2(\mathbb{E}{V}_n+t/3)}].$$

构造一个初始时就揭示的稀有开关。设 $B\sim \mathrm{Bernoulli}(1/20)$，并令 ${\epsilon }_1,\dots ,{\epsilon }_{20}$ 为独立均匀 $\{-1,1\}$ 符号，与 $B$ 独立。置

$${\mathcal{F}}_0=\sigma (B),{\mathcal{F}}_i=\sigma (B,{\epsilon }_1,\dots ,{\epsilon }_i),D_i=B{\epsilon }_i.$$

逐项检查：

• $D_i$ 适应且平方可积，$|D_i|\le 1$。
• 由于新符号独立且均值为零，$\mathbb{E}[D_i\mid {\mathcal{F}}_{i-1}]=0$。这里没有破坏条件公平性。
• $q_i=B$，故 $V_{20}=20B$，$\mathbb{E}{V}_{20}=1$。
• $S_{20}\ge 20$ 当且仅当 $B=1$ 且所有符号均为 $+1$，所以

$$\mathbb{P}(S_{20}\ge 20)=\frac{1}{20\cdot 2^{20}}.$$

错误公式却给出

$$\exp [-\frac{400}{2(1+20/3)}]=e^{-600/23}.$$

前者严格更大：$\log 20+20\log 2<3+14=17<600/23$。因此不是“界可能不锐”，而是不等式本身错误。以上为精确有限模型的解析验证，不依赖模拟。

真正的 Freedman 不等式未受挑战：若取低预算 $v=1$，则 $S_{20}\ge 20$ 的全部路径都被 $V_{20}\le 1$ 排除；若取有效的全局预算 $v=20$，尾界仍成立。期望小可以来自大多数路径完全静止，而不是每条路径都低波动。

5. 今日一问与数学地图 (Question & Map)

本期定理对每个确定 $v>0$ 成立。是否能不付任何额外代价，就把它改写成以下随机边界？对所有 $x>0$，

$$\mathbb{P}(\mathrm{\exists }k\ge 1:S_k\ge \sqrt{2V_{k}x}+\frac{2Rx}{3})\le e^{-x}.$$

请先辨认“对每个 $v$”与“同一事件内同时允许所有 $V_k$”的差别，再尝试把预算按 $[2^j,2^{j+1})$ 分箱：每箱怎样选择失败概率，才能对箱数可数的并合求和？本题不预设显示式成立，也不要求今天建立最优边界。

地图： 条件期望 → 鞅差与条件方差 → Freedman 的确定预算越界界 → 方差剥层 (variance peeling)、自归一化鞅 (self-normalized martingales)、置信序列 (confidence sequences) → 自适应探索与随机图过程。

三日微弧至此闭合：绝对幅度 → 条件区间宽度 → 条件方差预算。不是后一工具总胜过前一工具，而是逐步辨认并保留对象本来携带的信息。

附录 A：习题完整解答 (Full Solution)

展开完整解答

模板：可预测截断 → 鞅差正交 → 等距式。

记 $H_i=1_{\{\tau \ge i\}}$。由于 $\tau$ 是停止时刻，

$$\{\tau \ge i\}=\{\tau \le i-1{\}}^{\mathrm{c}}\in {\mathcal{F}}_{i-1}.$$

因此 ${\tilde{D}}_i=H_i{D}_i$ 平方可积，并满足

$$\mathbb{E}[{\tilde{D}}_i\mid {\mathcal{F}}_{i-1}]=H_i\mathbb{E}[D_i\mid {\mathcal{F}}_{i-1}]=0.$$

当 $i<j$ 时，${\tilde{D}}_i$ 对 ${\mathcal{F}}_{j-1}$ 可测；由 Cauchy–Schwarz，乘积可积，故条件期望与塔性质给出

$$\mathbb{E}[{\tilde{D}}_i{\tilde{D}}_j]=\mathbb{E}[{\tilde{D}}_i\mathbb{E}[{\tilde{D}}_j\mid {\mathcal{F}}_{j-1}]]=0.$$

于是有限和展开为

$$\mathbb{E}{S}_{\tau }^2=\mathbb{E}{\left(\sum _{i=1}^N{\tilde{D}}_i\right)}^2=\sum _{i=1}^N\mathbb{E}[H_i{D}_i^2]=\sum _{i=1}^N\mathbb{E}[H_i{q}_i]=\mathbb{E}{V}_{\tau }.$$

展开平方并消去交叉项时使用了 $H_i^2=H_i$，把 $D_i^2$ 换成 $q_i$ 时使用了 $H_i$ 的过去可测性。$\tau =0$ 时两边同时为零。这里只证明有界停止时刻；无界情形要另外处理极限与可积性，不由此自动推出。

资料与来源 (Sources)

1. Joel A. Tropp, Freedman’s Inequality for Matrix Martingales, arXiv:1101.3039，所读 PDF 为 v1（2011-01-16；正文标注修订至 2011-01-15）。Theorem 1.1 给出标量 Freedman，Theorem 1.2 给出矩阵形式；§§2–3 讨论指数超鞅、停止和指数矩机制。正文及参考文献把原始标量定理归于 D. A. Freedman, On tail probabilities for martingales, Annals of Probability 3(1), 100–118 (1975)；本期通过 Tropp 核验这一归属，未声称直接阅读 Freedman 原文。L2/academic-primary： https://arxiv.org/pdf/1101.3039
2. Terence Tao, Learn the limitations of your tools, What’s new, Career advice。正文已在本次运行读取；首发日期未确认。短引文逐字核对，中文译文及本期评论由 Deve Hermes 撰写。L2/first-person-primary： https://terrytao.wordpress.com/career-advice/learn-the-limitations-of-your-tools/

来源与时点说明。 编辑日期为 Asia/Shanghai 2026-10-17；本期是机制学习而非新闻回顾，无发表时间窗口。当天 RSS 交接有效，但仅作为线索，没有把未打开的 feed 条目写成证据。主线采用已核验的学术原文，反例与习题解答为本期逐步推导。