2026-10-16 · 不是把增量减半，而是保住区间宽度

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

2026 年 10 月 16 日，星期五。 Develata，昨天把单坐标敏感度 $c_i$ 转成了鞅差的绝对值界 $|D_i|\le c_i$，得到指数 $-t^2/(2\sum _i{c}_i^2)$。今天不加强函数的假设，却把指数改进为 $-2t^2/\sum _i{c}_i^2$。丢失的信息在哪里？

答案是：给定过去，$D_i$ 落在一个长度至多 $c_i$ 的区间里；粗估计把它扩成了长度 $2c_i$ 的对称区间。 条件均值为零不等于区间中点为零，因而不能靠宣称 $|D_i|\le c_i/2$ 来偷渡改进。

对象与量词分三层：函数在整个乘积空间上满足逐坐标界；随机坐标具有乘积律；固定过去后，增量区间的位置可以改变，而长度有确定上界。结论对每个确定阈值 $t>0$ 成立。

前置：条件期望、有限和求导、方差与 Jensen 不等式。证明引擎：对数指数矩的二阶导数是倾斜方差 → 区间宽度控制方差 → 条件递推与参数优化。这是三日微弧的 2/3 日，明确深化昨日的揭示鞅，而不是另起一遍 Azuma。明日的方向是进一步保留条件方差，尤其照顾稀疏随机图。

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

1.1 为什么宽度能进入指数矩？

Hoeffding 引理（本期先用有限取值版本）。 设实随机变量 $Y$ 有限取值，确定性实数 $a\le b$ 满足 $a\le Y\le b$ a.s.。则

$$\mathrm{\forall }\lambda \in \mathbb{R},\mathbb{E}{e}^{\lambda (Y-\mathbb{E}Y)}\le \exp \left(\frac{{\lambda }^2(b-a{)}^2}{8}\right).$$

[1, §2] 给出此引理的凸弦证明。这里换用一个揭示“宽度为何出现”的证明。

令 $K(s)=\log \mathbb{E}{e}^{sY}$。在原分布的每个取值 $y$ 上定义倾斜分布 (exponentially tilted distribution)

$${\mathbb{P}}_s(Y=y)=\frac{e^{sy}\mathbb{P}(Y=y)}{\mathbb{E}{e}^{sY}},s\in \mathbb{R}.$$

这是概率分布，且支撑仍在 $[a,b]$。有限和可逐项求导，所以

$$K^{\prime }(s)={\mathbb{E}}_{s}Y,K^{″}(s)={\mathrm{Var}}_s(Y).$$

任意支撑于 $[a,b]$ 的概率律，都满足

$$\mathrm{Var}(Y)=\underset{u\in \mathbb{R}}{min}\mathbb{E}(Y-u{)}^2\le \mathbb{E}{(Y-\frac{a+b}{2})}^2\le \frac{(b-a{)}^2}{4}.$$

因此令 $H(s)=K(s)-s\mathbb{E}Y$，有 $H(0)=H^{\prime }(0)=0$ 及 $H^{″}(s)\le (b-a{)}^2/4$。带积分余项的 Taylor 公式给出，对所有实数 $\lambda$，

$$H(\lambda )={\lambda }^2{\int }_0^1(1-u)H^{″}(u\lambda )du\le \frac{{\lambda }^2(b-a{)}^2}{8}.$$

取指数即得。若 $a=b$，中心化变量恒为零，也包含在结论中。

RMK。 方差界对每一个倾斜参数都成立，而不只是对原始概率律成立。这正是它能控制整条指数矩曲线、而非仅控制原点二阶导数的原因。

1.2 保住条件区间，而不是猜一个更小的绝对值界

固定整数 $n\ge 1$、有限非空集合 $E_1,\dots ,E_n$。在同一概率空间上，令 $X_i$ 为相互独立的 $E_i$-值随机变量，$f:\prod _i{E}_i\to \mathbb{R}$。假设存在确定性 $c_i\ge 0$，满足

$$\mathrm{\forall }i\in \{1,\dots ,n\},\mathrm{\forall }x,y\in \prod _j{E}_j,[\mathrm{\forall }j\ne i,x_j=y_j]⟹|f(x)-f(y)|\le c_i.$$

这叫有界差分条件 (bounded differences condition)。记

$${\mathcal{F}}_i=\sigma (X_1,\dots ,X_i),Z_i=\mathbb{E}[f(X)\mid {\mathcal{F}}_i],D_i=Z_i-Z_{i-1},$$

其中 ${\mathcal{F}}_0$ 平凡。塔式性质给出 $\mathbb{E}[D_i\mid {\mathcal{F}}_{i-1}]=0$。

固定任一正概率前缀 $h=(x_1,\dots ,x_{i-1})$，令

$$g_h(a)=\mathbb{E}f(h,a,X_{i+1},\dots ,X_n),a\in E_i.$$

独立性让不同 $a$ 共用同一个未来分布，因此

$$\underset{a\in E_i}{max}{g}_h(a)-\underset{a\in E_i}{min}{g}_h(a)\le c_i.$$

若 ${\mu }_h=\mathbb{E}{g}_h(X_i)$，则在此前缀下 $D_i=g_h(X_i)-{\mu }_h$，所以它落在

$$[\underset{a}{min}{g}_h(a)-{\mu }_h,\underset{a}{max}{g}_h(a)-{\mu }_h]$$

中。这是长度至多 $c_i$ 的区间，端点依赖 $h$，长度上界不依赖 $h$。对每个前缀的条件分布使用引理，得到

$$\mathrm{\forall }\lambda \in \mathbb{R},\mathbb{E}[e^{\lambda D_i}\mid {\mathcal{F}}_{i-1}]\le e^{{\lambda }^2{c}_i^2/8}\text{a.s.}$$

零概率前缀无需规定条件分布；以上结论是几乎处处的陈述。

1.3 McDiarmid 不等式及其常数来源

定理。 在上述全部假设下，令 $C=\sum _{i=1}^n{c}_i^2$。若 $C>0$，则

$$\mathrm{\forall }t>0,\mathbb{P}(f(X)-\mathbb{E}f(X)\ge t)\le e^{-2t^2/C},$$

$$\mathbb{P}(|f(X)-\mathbb{E}f(X)|\ge t)\le 2e^{-2t^2/C}.$$

若 $C=0$，逐坐标替换连接任意两点，故 $f$ 为常数，偏差概率为零。[1, §3, Theorem 2]

证明收口。 用条件期望逐步剥离 $D_n,D_{n-1},\dots ,D_1$，得到

$$\mathbb{E}{e}^{\lambda (f(X)-\mathbb{E}f(X))}\le e^{{\lambda }^{2}C/8}.$$

于是对每个 $\lambda >0$，上尾概率至多 $\exp (-\lambda t+{\lambda }^{2}C/8)$。取 $\lambda =4t/C$ 得到上尾；对 $-f$ 应用同理，再合并两尾。

“四倍”指同一 $C,t$ 下指数的绝对值是昨日粗界的四倍，不是概率恰好缩小四倍。这也不表示实际尾概率达到此上界。

谱系。 独立和的 Hoeffding 界只需控制每个加数的区间；McDiarmid 把对象推广为独立输入的非线性函数，经揭示鞅把局部区间结构传递下去。此处是机制谱系；[1] 将有界差分方法归于 McDiarmid，并列其 1989 年综述。本期没有另行核验那篇原始综述，不据此补写优先权细节。

1.4 研究生延伸：上确界的集中，不等于均值很小

令 $X_i$ 独立同分布于有限集合 $E$，$\mathcal{A}$ 为 $E$ 的非空子集族。定义经验一致偏差 (uniform empirical deviation)

$$U(X)=\underset{A\in \mathcal{A}}{sup}|\frac{1}{n}\sum _{i=1}^n{\mathbf{1}}_{\{X_i\in A\}}-\mathbb{P}(X_1\in A)|.$$

改变一个输入，对每个 $A$ 都至多改变 $1/n$；由

$$|\underset{A}{sup}{u}_A-\underset{A}{sup}{v}_A|\le \underset{A}{sup}|u_A-v_A|$$

及绝对值的反三角不等式，$U$ 的每个坐标敏感度至多 $1/n$。因此

$$\mathbb{P}(|U-\mathbb{E}U|\ge t)\le 2e^{-2n{t}^2}(t>0).$$

但这不告诉我们 $\mathbb{E}U$ 有多小。估计均值需要利用集合族的大小或复杂度；集中与均值定位须分别完成。[1, §4.2–4.3] 从这里可走向经验过程、对称化与学习理论，但本期不把这些名词当作已证明的结果。

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

题目。 给定整数 $m\ge 2$、常数 $\sigma >0$，以及同一概率空间上的实随机变量 $Y_1,\dots ,Y_m$。不假设独立，假设

$$\mathrm{\forall }j\in \{1,\dots ,m\},\mathrm{\forall }\lambda \in \mathbb{R},\mathbb{E}{e}^{\lambda Y_j}\le e^{{\sigma }^2{\lambda }^2/2}.$$

证明 $\underset{1\le j\le m}{max}{Y}_j$ 可积，并证明

$$\mathbb{E}\underset{1\le j\le m}{max}{Y}_j\le \sigma \sqrt{2\log m}.$$

模板识别。 已知单变量指数矩，要求有限族最大值的期望。把最大值送进指数，再用一个和控制；目标中的 $\log m$ 提示最后需要取对数，而不是逐对计算协方差。

分级提示。

1. 对任意 $\lambda >0$，比较 $e^{\lambda \underset{j}{max}{Y}_j}$ 和 $\sum _j{e}^{\lambda Y_j}$。这一步需要独立性吗？
2. 先用 $e^{|y|}\le e^y+e^{-y}$ 验证可积性，再对指数函数用 Jensen。
3. 得到含 $\lambda$ 的上界后，平衡一个 $1/\lambda$ 项与一个 $\lambda$ 项。

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

语境。 Terence Tao 在个人网站 What's new 的研究学习建议 “Ask yourself dumb questions” 中，讨论成品证明与实际探索过程的差异。本次直接读取作者文章；正文首发日期未能确认，故不补日期。页面开头另引 Halmos，本期不把那段二手引文冒充已核验的 Halmos 原文。[2]

Tao 自己的正文写道：

“However, the process of discovering new mathematics is much messier, full of the pursuit of directions which were naïve, fruitless or uninteresting.”

译： 然而，发现新数学的过程凌乱得多，其中充满了对那些天真、徒劳或无趣方向的追寻。

转述（非引文）： 他接着建议，面对标准引理，不妨删掉一个假设、加强一下结论，或尝试另一种证明；即便新路线失败，也会帮助辨认原有方法为何有效，以及不同方法各自的能力。

本刊评论。 昨天已有正确结论，今天仍追问“能不能把 $c_i$ 减半？”这个问题的直接答案是不能，但失败诊断把我们引向了正确对象——不是绝对值半径，而是条件支撑宽度。朴素追问的价值不是保证出现新定理，而是逼迫我们指出：究竟哪一步丢了信息？这一点也区别于昨日的“把直觉写成细节”：今天关心的是通过失败的加强，选择更准确的中间对象。

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

4.1 中心化不保证半径减半

取 $X\sim \mathrm{Bernoulli}(1/10)$，$f(x)=x$。逐项检查：

• 坐标替换界是 $c=1$。
• $D=X-\mathbb{E}X$ 的取值为 $-1/10$ 与 $9/10$，条件中心化（此处过去平凡）成立。
• 支撑宽度恰为 $1$，但 $\mathbb{P}(|D|>1/2)=1/10>0$。

所以 $|D|\le c/2$ 是假命题。本期的宽度引理仍完全适用；改进结论是真的，偷换中间假设的证明是假的。

4.2 典型配置平坦，不等于全局敏感度为零

取整数 $n\ge 3$，令 $X_1,\dots ,X_n$ 独立且均匀取值于 $\{0,1\}$。定义

$$f(x)={\mathbf{1}}_{\{x=(1,\dots ,1)\}},x\in \{0,1{\}}^n.$$

对每个配置 $x$ 定义其局部替换振幅

$$L_i(x)=\underset{a\in \{0,1\}}{max}|f(x)-f(x_1,\dots ,x_{i-1},a,x_{i+1},\dots ,x_n)|.$$

1. 若 $x$ 至少含两个零，改动任一坐标仍至少剩一个零。因此 $f(x)=0$ 且对所有 $i$ 都有 $L_i(x)=0$。
2. 不满足“至少两个零”的配置共 $n+1$ 个：全一配置及恰有一个零的 $n$ 个配置。所以

$$\mathbb{P}(\mathrm{\forall }i,L_i(X)=0)=1-\frac{n+1}{2^n}⟶1.$$

3. 然而 $f(X)\sim \mathrm{Bernoulli}(2^{-n})$，其方差为 $2^{-n}(1-2^{-n})>0$，并非 a.s. 常数。
4. 真正的全局坐标界仍是每个 $c_i=1$：比较全一配置与仅第 $i$ 位为零的配置，函数差恰为 $1$。

这驳倒了把“以高概率观察到的局部界 $c_i=0$”直接代入 McDiarmid 零宽度情形的做法。对每个固定 $n$，例外集概率虽小却严格为正；定理要求的是全局替换量词，不是一个逐渐高概率的好事件。

边界的精确位置： 坐标平均 $g_h(a)$ 会遇到未来的罕见配置；不能在没有补偿项或额外论证的情况下把它们删除。本例不否定带例外集修正的集中方法，只否定不付代价地替换假设。以上是精确计数推导，不是模拟结果。

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

设 $X_i$ 独立且 $X_i\sim \mathrm{Bernoulli}(p)$，$0<p<1$，$f$ 满足坐标界 $c_i$。沿用第 1 节，在固定过去 $h$ 后记

$${\mathrm{\Delta }}_i(h)=g_h(1)-g_h(0).$$

今日一问： 能否写出 $D_i$ 关于 $X_i-p$ 与 ${\mathrm{\Delta }}_i(h)$ 的精确乘积表达式，进而证明

$$\mathbb{E}[D_i^2\mid {\mathcal{F}}_{i-1}]\le p(1-p)c_i^2\text{a.s.}?$$

只得到此式后，为什么仍不能直接把 McDiarmid 中的 $C$ 换成 $p(1-p)C$，并宣称对全部偏差阈值都有同样的纯高斯尾？请比较第 1.1 节“所有倾斜分布的方差”与“原分布的方差”。这保留了真正的证明缺口，留给明日。

地图：

$$\text{区间内方差界}⟶\text{Hoeffding 引理}⟶\text{条件宽度与 McDiarmid}⟶\text{条件方差预算}⟶\text{方差敏感的鞅集中}.$$

随机图接口：对 $G(N,p)$ 的最大割，边坐标敏感度至多一；McDiarmid 改进了昨日常数，却仍不含 $p$。今天的问题指出稀疏性应从何处进入，但不提前声称已经得到精确大偏差速率或最可能的偏差结构。

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

展开完整解答

模板：指数和控制最大值 (log-sum-exp bound for maxima)。

先用题设在 $\lambda =1,-1$ 处的估计，得到对每个 $j$，

$$\mathbb{E}{e}^{|Y_j|}\le \mathbb{E}{e}^{Y_j}+\mathbb{E}{e}^{-Y_j}\le 2e^{{\sigma }^2/2}<\mathrm{\infty }.$$

由 $|y|\le e^{|y|}$，所有 $Y_j$ 可积。令 $M=\underset{j}{max}{Y}_j$，则 $|M|\le \sum _j|Y_j|$，故 $M$ 可积。

对任意 $\lambda >0$，逐点有 $e^{\lambda M}\le \sum _j{e}^{\lambda Y_j}$，从而

$$\mathbb{E}{e}^{\lambda M}\le m{e}^{{\sigma }^2{\lambda }^2/2}.$$

Jensen 不等式给出 $e^{\lambda \mathbb{E}M}\le \mathbb{E}{e}^{\lambda M}$。两边取对数并除以 $\lambda$：

$$\mathbb{E}M\le \frac{\log m}{\lambda }+\frac{{\sigma }^2\lambda }{2}.$$

由于 $m\ge 2$、$\sigma >0$，可取 $\lambda =\sqrt{2\log m}/\sigma$，即得

$$\mathbb{E}M\le \sigma \sqrt{2\log m}.$$

整个论证没有将指数矩相乘，所以无需 $Y_j$ 独立。这个模板把“同时看 $m$ 个量”的代价放进 $\sqrt{\log m}$；它也可在有限函数族的一致偏差问题中帮助估计均值，而 McDiarmid 负责该偏差围绕均值的集中。两者作用不同。

资料与来源 (Sources)

1. Maxim Raginsky, Concentration inequalities, 2013-08-29，大学课程讲义，§2（Lemma 1，Hoeffding 引理）、§3（Theorem 2，McDiarmid 不等式及条件区间构造）、§4.2–4.3（经验一致偏差）。本次下载并读取完整 PDF；自动文字提取有数学字体错码，因此公式按证明重新推导，不照抄损坏符号。第 1.1 节的倾斜方差证明是本刊展开，并非声称讲义采用该证明。 https://maxim.ece.illinois.edu/teaching/fall13/notes/concentration.pdf
2. Terence Tao, “Ask yourself dumb questions”, What's new, “Career advice” 栏目，首发日期本次未确认。作者本人关于数学学习与研究实践的文章；英文短引已与本次直接取得的正文核对，中文为本刊翻译。 https://terrytao.wordpress.com/career-advice/ask-yourself-dumb-questions/

查证范围。 截至 2026-10-16（Asia/Shanghai）；按数学质量选材，不设发表时间回看门槛。当日 RSS 发现投影状态为成功，但只作选题线索，本期未用其中条目作引文。先读本地来源目录，再检索学术讲义与打开作者原文；PDF 首次网页提取只返回首尾摘要，已改为下载并阅读全文。第 4 节反例及附录均为本刊完整推导，不冒充外部引文或已运行的计算实验。