2026-08-09 · 当指数代价压过候选数

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

起点问题。 前两日的随机图证明反复出现同一种动作：先固定一个可能制造障碍的对象，再估计它成为坏对象的概率，最后对所有候选作 union bound（并合界）。例如：

• 固定一个顶点，估计它孤立的概率；
• 固定一个顶点集，估计它与补集之间没有边的概率；
• 固定一个探索根，估计其分量异常大的概率。

这些计算何时足以控制所有候选？关键并非一句“概率很小”，而是比较两个都可能随 $n$ 指数增长或衰减的量：

$$\underset{\text{combinatorial entropy（组合熵）}}{\underbrace{\log (\text{候选数})}}\text{与}\underset{\text{probability cost（概率代价）}}{\underbrace{-\log (\text{固定候选为坏的概率})}}.$$

当后者严格压过前者，简单并合界便能封口；二者打平时，依赖结构、精确常数和次指数因子都会重新变得可见。

对象与量词层。 今天有三层对象，不可混同：

1. 对每个 $n$，有一个候选指标集 ${\mathcal{A}}_n$；
2. 对每个固定 $a\in {\mathcal{A}}_n$，有坏事件 $B_{n,a}$；
3. 我们要控制的是存在量词
   $$\mathbb{P}(\mathrm{\exists }a\in {\mathcal{A}}_n:B_{n,a}),$$
   而不是某个预先固定的 $a$ 的概率。

随机图应用中，候选 $a$ 将是顶点集 $S\subset [n]$，坏事件是跨割边数显著低于均值。固定 $S$ 后只有一个二项分布；允许 $S$ 在 $2^n$ 个集合中选择后，问题才成为组合概率。

前置知识。 Markov 不等式、独立 Bernoulli 和、二项系数上界 $(\genfrac{}{}{0ex}{}{n}{k})\le (en/k{)}^k$、凸函数的一阶与二阶导数。Graduate / modern extension 将使用 log-mgf（对数矩母函数）、Legendre–Fenchel transform（Legendre–Fenchel 变换）、relative entropy（相对熵）和 Cramér large-deviation principle（Cramér 大偏差原理）。

主导 proof engines。 本期的机制链是

$$\text{指数倾斜}⟶\text{优化得到率函数}⟶\text{固定候选的指数代价}⟶\text{按候选尺度计数}⟶\text{熵--代价比较}.$$

这不是把昨天的 Chernoff 习题重复一遍。昨日得到一个方便使用的乘性上尾界；今日要识别优化后指数的几何意义，把它写成 $D(q\parallel p)$，并说明它怎样与 $\log (\genfrac{}{}{0ex}{}{n}{k})$ 共同构成阈值证明的“预算表”。

这是三日 anchor micro-arc 的第 3 日，也是收束日。第 1 日的连通窗口由“小分离集的候选数 versus 无跨割边代价”支配；第 2 日的次临界最大分量由“$n$ 个根 versus 分枝总后代指数尾”支配；今天把两者桥接到 probability.large-deviations 与 combinatorics.probabilistic-method。弧结束后，下一期将转向 exploration 节点，而非继续堆叠随机图阈值。

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

1.1 最小抽象：并合界何时自动赢

设 ${\mathcal{A}}_n$ 是有限集，$B_{n,a}$ 是同一概率空间上的事件。Boole inequality（Boole 不等式）给出

$$\mathbb{P}\left(\bigcup _{a\in {\mathcal{A}}_n}{B}_{n,a}\right)\le \sum _{a\in {\mathcal{A}}_n}\mathbb{P}(B_{n,a}).$$

注意这里不要求事件独立。独立性通常只用于估计每个固定事件，而非用于最后的并合。

熵--代价引理。 假设存在实数列 $a_n,b_n$，使

$$|{\mathcal{A}}_n|\le e^{a_n},\underset{a\in {\mathcal{A}}_n}{sup}\mathbb{P}(B_{n,a})\le e^{-b_n}.$$

则

$$\mathbb{P}(\mathrm{\exists }a\in {\mathcal{A}}_n:B_{n,a})\le e^{a_n-b_n}.$$

特别地，若

$$b_n-a_n⟶+\mathrm{\infty },$$

则以概率趋于 $1$，不存在任何坏候选。

证明只有一行并合界，但它给出一个重要翻译：候选数本身可能很大，只要单个候选的失败概率更小。若存在一个随机对象落在“无坏事件”集合中的概率为正，则该集合非空，从而得到一个确定性对象。这就是 first-moment existence principle（第一矩存在性原理）的基本形式。

实际问题常有多个尺度。若

$${\mathcal{A}}_n=\underset{k}{⨆}{\mathcal{A}}_{n,k},$$

则不应粗暴地用 $|{\mathcal{A}}_n|$ 乘最坏概率，而应保留

$$\sum _k|{\mathcal{A}}_{n,k}|\underset{a\in {\mathcal{A}}_{n,k}}{sup}\mathbb{P}(B_{n,a}).$$

随机图中 $k=|S|$ 就是天然尺度；小集合与线性大小集合的计数规律不同，危险尺度也未必相同。

1.2 固定候选的精确指数：Bernoulli relative entropy

令 $Y_1,\dots ,Y_m$ 相互独立且

$$Y_i\sim \mathrm{Bernoulli}(p),0<p<1,$$

并令

$$X_m=\sum _{i=1}^m{Y}_i.$$

对 $q\in (0,1)$，定义 binary relative entropy（二元相对熵）

$$D(q\parallel p):=q\log \frac{q}{p}+(1-q)\log \frac{1-q}{1-p},$$

其中对数取自然对数。

定理（Bernoulli Chernoff bound 的率函数形式）。 对每个整数 $m\ge 1$：

• 若 $p<q<1$，则
  $$\mathbb{P}(X_m\ge mq)\le \exp (-mD(q\parallel p));$$
• 若 $0<q<p$，则
  $$\mathbb{P}(X_m\le mq)\le \exp (-mD(q\parallel p)).$$

若 $mq$ 不是整数，事件按通常实数阈值解释；这不会改变证明。

上尾推导。 任取 $t>0$。指数函数递增，故由 Markov 不等式与独立性，

$$\begin{array}{rl}\mathbb{P}(X_m\ge mq)& =\mathbb{P}(e^{t{X}_m}\ge e^{tmq})\\ & \le e^{-tmq}\mathbb{E}{e}^{t{X}_m}\\ & =\exp (-m[tq-\log (1-p+p{e}^t)]).\end{array}$$

因此要最大化

$${\mathrm{\Phi }}_{p,q}(t)=tq-\log (1-p+p{e}^t).$$

求导得

$${\mathrm{\Phi }}_{p,q}^{\prime }(t)=q-\frac{p{e}^t}{1-p+p{e}^t}.$$

驻点满足

$$q=\frac{p{e}^{t_{\ast }}}{1-p+p{e}^{t_{\ast }}},$$

即

$$t_{\ast }=\log \frac{q(1-p)}{p(1-q)}.$$

当 $q>p$ 时 $t_{\ast }>0$，确在允许区域内；而 ${\mathrm{\Phi }}_{p,q}^{″}(t)<0$，故它是唯一极大点。代入并整理，

$${\mathrm{\Phi }}_{p,q}(t_{\ast })=D(q\parallel p).$$

于是得到上尾界。下尾完全平行，只需取 $t<0$；当 $q<p$ 时同一公式给出的 $t_{\ast }<0$。

这个优化有清楚的概率意义。原始 Bernoulli 参数是 $p$，而指数倾斜后的成功概率为

$$\frac{p{e}^t}{1-p+p{e}^t}.$$

最优 $t_{\ast }$ 恰把新均值调到稀有事件要求的 $q$；为把典型值从 $p$ 推到 $q$ 所支付的每次试验代价，就是 $D(q\parallel p)$。

常用乘性下尾界是它的二次简化：对 $0<\delta <1$，取 $q=(1-\delta )p$，可得

$$D((1-\delta )p\parallel p)\ge \frac{p{\delta }^2}{2},$$

这里的常数可直接从同一次优化看出。把上尾推导中的参数改写为下尾参数 $s=-t>0$，使用 $\log (1+u)\le u$，并在

$$s_{\ast }=-\log (1-\delta )$$

处取值，得到

$$D((1-\delta )p\parallel p)\ge p[\delta +(1-\delta )\log (1-\delta )].$$

而函数

$$h(\delta )=\delta +(1-\delta )\log (1-\delta )-\frac{{\delta }^2}{2}$$

满足 $h(0)=0$ 且

$$h^{\prime }(\delta )=-\log (1-\delta )-\delta \ge 0,$$

最后一步使用 $-\log (1-\delta )\ge \delta$。故上述二次下界成立。

从而若 $X\sim \mathrm{Bin}(m,p)$、$\mu =mp$，则

$$\mathbb{P}(X\le (1-\delta )\mu )\le e^{-\mu {\delta }^2/2}.$$

精确的 $D$ 适合比较临界常数；二次界则适合只需明确正指数裕量的证明。

1.3 组合熵：候选集合究竟有多少

对 $0<\alpha <1$，定义 binary entropy（二元熵）

$$H(\alpha )=-\alpha \log \alpha -(1-\alpha )\log (1-\alpha ).$$

Stirling 公式给出：若 $k=\alpha n+O(1)$ 且 $\alpha$ 远离 $0,1$，则

$$\log (\genfrac{}{}{0ex}{}{n}{k})=nH(\alpha )+O(\log n).$$

因此线性大小的顶点集有 $e^{nH(\alpha )+o(n)}$ 个。对 $k=o(n)$，更实用的是全范围上界

$$(\genfrac{}{}{0ex}{}{n}{k})\le {\left(\frac{en}{k}\right)}^k,\log (\genfrac{}{}{0ex}{}{n}{k})\le k\log \frac{en}{k}.$$

这里的“熵”首先只是候选集基数的对数。它之所以与 information-theoretic entropy（信息论熵）使用同一函数，不是修辞巧合：$(\genfrac{}{}{0ex}{}{n}{\alpha n})$ 正是在数具有给定 empirical frequency（经验频率）的二元串，即一个 type class（型类）。

1.4 应用：所有随机图割同时浓缩

设

$$G\sim G(n,p),0<p<1.$$

对非空真子集 $S\subset [n]$，记

$$e_G(S,S^{\mathsf{c}})$$

为一端在 $S$、另一端在补集的边数。固定 $|S|=k$ 后，共有 $k(n-k)$ 条可能的跨割边，并且它们独立出现，故

$$e_G(S,S^{\mathsf{c}})\sim \mathrm{Bin}(k(n-k),p).$$

定理（高于连通尺度的统一割下尾）。 固定 $0<\delta <1$。若概率列 $p=p_n$ 满足

$$n{p}_n\ge \frac{8}{{\delta }^2}\log n$$

对所有充分大的 $n$ 成立，则

$$\mathbb{P}(\mathrm{\forall }S\subset [n],1\le |S|\le \frac{n}{2}:e_G(S,S^{\mathsf{c}})\ge (1-\delta )p_n|S|(n-|S|))⟶1.$$

特别地，$G(n,p_n)$ 以高概率连通。

证明。 固定 $S$ 且 $|S|=k\le n/2$。由乘性 Chernoff 下尾界，

$$\mathbb{P}(e_G(S,S^{\mathsf{c}})<(1-\delta )p_{n}k(n-k))\le \exp (-\frac{{\delta }^2}{2}{p}_{n}k(n-k)).$$

因为 $n-k\ge n/2$，右侧至多为

$$\exp (-\frac{{\delta }^2}{4}{p}_{n}kn).$$

现在才允许 $S$ 变化。按 $k$ 分层并合，并使用 $(\genfrac{}{}{0ex}{}{n}{k})\le (en/k{)}^k$：

$$\begin{array}{rl}& \mathbb{P}(\mathrm{\exists }S,1\le |S|\le n/2:e_G(S,S^{\mathsf{c}})<(1-\delta )p_n|S|(n-|S|))\\ & \le \sum _{k=1}^{\lfloor n/2\rfloor }(\genfrac{}{}{0ex}{}{n}{k})\exp (-\frac{{\delta }^2}{4}{p}_{n}kn)\\ & \le \sum _{k=1}^{\lfloor n/2\rfloor }{[\frac{en}{k}\exp (-\frac{{\delta }^2}{4}{p}_{n}n)]}^k.\end{array}$$

由假设

$$\frac{{\delta }^2}{4}{p}_{n}n\ge 2\log n,$$

故方括号至多为 $e/(kn)$。于是上式不超过

$$\sum _{k\ge 1}{\left(\frac{e}{n}\right)}^k=\frac{e/n}{1-e/n}=o(1).$$

统一下界得证。若图不连通，则存在一个连通分量的顶点集 $S$ 满足 $1\le |S|\le n/2$ 且 $e_G(S,S^{\mathsf{c}})=0$；这与已证下界矛盾，所以连通性随之成立。

这个证明把预算逐项摊开：大小为 $k$ 的候选集至多贡献

$$\exp (\underset{\text{组合熵}}{\underbrace{k\log (en/k)}}-\underset{\text{偏差代价}}{\underbrace{\frac{{\delta }^2}{4}{p}_{n}kn}}).$$

当 $p_{n}n$ 是足够大的 $\log n$ 倍数时，偏差代价在每个 $k$ 上都压过计数。定理中的常数 $8/{\delta }^2$ 是为一条干净证明留下的裕量，并非连通性的尖锐常数。

1.5 历史谱系：从随机染色到方法论

Erdős 1947 年的 Some Remarks on the Theory of Graphs 考虑对 $N$ 个标号顶点的图进行计数。用现代概率语言重写：把完全图 $K_N$ 的每条边独立染成红或蓝，概率各为 $1/2$。固定一个 $k$ 元顶点集，其诱导 $K_k$ 单色的概率是

$$2{\left(\frac{1}{2}\right)}^{(\genfrac{}{}{0ex}{}{k}{2})}=2^{1-(\genfrac{}{}{0ex}{}{k}{2})}.$$

单色 $K_k$ 的候选数为 $(\genfrac{}{}{0ex}{}{N}{k})$，所以

$$\mathbb{P}(\mathrm{\exists }\text{ 单色 }{K}_k)\le (\genfrac{}{}{0ex}{}{N}{k})2^{1-(\genfrac{}{}{0ex}{}{k}{2})}.$$

若右侧小于 $1$，便存在一种染色没有单色 $K_k$，从而

$$R(k,k)>N.$$

Erdős 的原论证由此得到经典指数下界 $R(k,k)>2^{k/2}$。原论文写的是“坏图总数小于全部图数”；现代写法是“坏事件总概率小于 $1$”。二者是同一个 first-moment argument（第一矩论证）。

这条 1947 界不是 Ramsey 理论后来最精细的数值结果；其 surviving core（存续核心）是证明范式：不必显式构造对象，只需在一个可分析的随机模型中证明好对象具有正概率。Alon 与 Spencer 在 2021 年 AMS Steele Prize 回应中回顾，他们把散落的结果组织成 The Probabilistic Method，重点放在 methodology and ideas，而非百科式穷举。后来的 alteration（随机后修正）、Lovász local lemma、二阶矩、相关不等式、容器方法与 derandomization（去随机化），都可看作在简单并合界不够时继续控制“候选熵 versus 约束代价”。

1.6 Graduate / modern extension：Chernoff 上界与 Cramér 原理不是同一句话

设 $Z_1,Z_2,\dots$ 为实值 i.i.d. 随机变量，并令

$$\mathrm{\Lambda }(t)=\log \mathbb{E}{e}^{t{Z}_1}$$

为 cumulant generating function（累积量生成函数）。只要所需 $t$ 上指数矩有限，Markov 不等式就给出单侧 Chernoff 上界

$$\mathbb{P}(\frac{1}{n}\sum _{i=1}^n{Z}_i\ge x)\le \exp (-n\underset{t\ge 0}{sup}\{tx-\mathrm{\Lambda }(t)\}).$$

这只是上界。为给出一个明确版本，进一步假设 $\mathrm{\Lambda }(t)<\mathrm{\infty }$ 对每个 $t\in \mathbb{R}$ 成立。Cramér 定理说明经验均值满足 large-deviation principle，其 good rate function（好率函数）为

$$I(x)=\underset{t\in \mathbb{R}}{sup}\{tx-\mathrm{\Lambda }(t)\}.$$

更准确地，若 Borel 集 $A\subset \mathbb{R}$ 是 $I$-continuity set，即

$$\underset{x\in A^{\circ }}{inf}I(x)=\underset{x\in \bar{A}}{inf}I(x),$$

则概率在对数尺度上满足

$$\mathbb{P}(\frac{1}{n}\sum _{i=1}^n{Z}_i\in A)=\exp (-n\underset{x\in A}{inf}I(x)+o(n)).$$

上界告诉我们某事件不会比给定指数更常见；大偏差原理还需要匹配的下界，才说明该指数是正确衰减率。对 Bernoulli 分布，$I(q)=D(q\parallel p)$，Section 1.2 的 Chernoff 优化因此正好命中真实的大偏差指数。

在随机图中，若 $|S|\sim \alpha n$，跨割边的试验数约为 $\alpha (1-\alpha )n^2$，而候选数约为 $e^{nH(\alpha )}$。于是某类坏割的 union-bound exponent 具有典型形式

$$nH(\alpha )-\alpha (1-\alpha )n^{2}D(q_n\parallel p_n).$$

当 $p_n\asymp 1/n$ 时，两项都可能是 $n$ 量级，真正形成一个 variational competition（变分竞争）；当 $p_n\asymp (\log n)/n$ 时，宏观割的概率代价通常达到 $n\log n$ 量级，远大于 $n$ 量级候选熵，危险对象便转移到小集合。这正是为何阈值证明必须按 $|S|$ 分尺度，而不能只看总共有 $2^n$ 个集合。

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

题目

对 $p,q\in (0,1)$，定义

$$D(q\parallel p)=q\log \frac{q}{p}+(1-q)\log \frac{1-q}{1-p}.$$

证明 Bernoulli Pinsker inequality（Bernoulli 情形的 Pinsker 不等式）

$$\boxed{{\displaystyle D(q\parallel p)\ge 2(q-p{)}^2.}}$$

并说明等号何时成立。最后把结论连续延拓到 $p,q\in [0,1]$ 中散度有限的边界情形。

模板识别

看到“一个光滑函数在某点函数值与一阶导数都为零，希望得到到该点距离的二次下界”，应优先检查 second derivative lower bound（二阶导数下界）。若

$$F^{″}(x)\ge m>0,$$

则 $F$ 是 $m$-strongly convex（$m$-强凸）的，并有

$$F(x)\ge F(x_0)+F^{\prime }(x_0)(x-x_0)+\frac{m}{2}(x-x_0{)}^2.$$

本题中固定 $p$，把 $D(q\parallel p)$ 视为 $q$ 的函数。

分级提示

1. 计算关于 $q$ 的一阶导数，并验证 $q=p$ 是驻点。
2. 证明
   $$\frac{{\partial }^2}{\partial q^2}D(q\parallel p)=\frac{1}{q(1-q)}.$$
3. 使用 $q(1-q)\le 1/4$，得到一个与 $p,q$ 无关的二阶导数下界。
4. 可考虑函数 $G(q)=D(q\parallel p)-2(q-p{)}^2$；证明它在 $q=p$ 取得全局最小值。边界情形最后用连续性或极限处理。

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

人物与文本。 理论计算机科学家 Scott Aaronson 在个人博客 Shtetl-Optimized 的文章 How to upper-bound the probability of something bad（2018-04-13）中，把“控制坏事件概率”写成一份十步 proof-search flowchart（证明搜索流程图）。文章明确以随机算法失败、随机图或随机码不满足所需性质为例，因而不是泛泛的励志建议，而是第一人称的研究程序记录。

核验短引。

“Step 3. See if the bad event you’re worried about involves a sum of independent random variables exceeding some threshold. If it does, hit that sucker with a Chernoff or Hoeffding bound.”

中译。 “第 3 步：检查你担心的坏事件是否涉及一组独立随机变量之和越过某个阈值。若是，就用 Chernoff 或 Hoeffding 界正面处理它。”

评注。 这段话的数学价值在于它同时给出 signal（识别信号）与 tool（工具）：不是一见概率就套 Chernoff，而是先核验“独立和 + 越界事件”。今天的随机图割正符合该类型，因为固定 $S$ 后，跨割边指标相互独立；一旦让 $S$ 变化，Chernoff 只完成固定候选层，仍须另加候选计数与并合界。

Aaronson 的流程还依次放入 Markov/union bound、martingale/Azuma、variance/Chebyshev、variation distance 及更精细不等式。这揭示一种克制的研究次序：先使用结构需求最少、代价最低的工具；若失败，再问失败来自指数不够、依赖过强，还是待证命题本身错误。方法表不是定理清单，而是“先辨对象类型，再升级证明机器”的决策树。

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

4.1 $\sum _a\mathbb{P}(B_a)<1$ 只是充分条件，不是必要条件

取概率空间

$$\mathrm{\Omega }=\{0,1\},\mathbb{P}(0)=\frac{2}{5},\mathbb{P}(1)=\frac{3}{5}.$$

令

$$B_1=B_2=\{1\}.$$

逐项检查：

1. 每个坏事件的概率都是 $3/5$；
2. 概率和为
   $$\mathbb{P}(B_1)+\mathbb{P}(B_2)=\frac{6}{5}>1;$$
3. 但两个事件完全重合，所以
   $$\mathbb{P}(B_1\cup B_2)=\frac{3}{5};$$
4. 好事件仍有正概率
   $$\mathbb{P}(B_1^{\mathsf{c}}\cap B_2^{\mathsf{c}})=\frac{2}{5}>0.$$

因此“并合界上界不小于 $1$”只表示该证明没有成功，绝不表示好对象不存在。失败原因是第一矩把重复覆盖全部重复相加，看不见 overlap（重叠）。

在组合问题里，不同候选坏事件往往高度相关：一个局部缺陷可能同时制造大量坏候选。此时可能需要重新定义更少的 witness（见证）、使用 Lovász local lemma 利用稀疏依赖、用 Janson inequality 处理共享底层随机变量造成的依赖，或用 container method（容器方法）压缩候选熵。

4.2 指数恰好打平时，相同边际可以给出相反结局

令

$${\mathrm{\Omega }}_n=\{0,1{\}}^n$$

带均匀分布，并令候选集也为 ${\mathcal{A}}_n=\{0,1{\}}^n$。于是候选数是 $2^n$。考虑两族坏事件。

模型 A：单点分割。 对每个 $x\in {\mathcal{A}}_n$，令

$$B_x=\{x\}.$$

则

$$\mathbb{P}(B_x)=2^{-n}$$

对每个 $x$ 都成立，但

$$\bigcup _x{B}_x={\mathrm{\Omega }}_n,\mathbb{P}(\mathrm{\exists }x:B_x)=1.$$

不存在好结果。

模型 B：完全重叠。 对每个 $x\in {\mathcal{A}}_n$，都令

$$B_x=\{0^n\}.$$

每个坏事件仍满足

$$\mathbb{P}(B_x)=2^{-n},$$

候选数仍为 $2^n$，但现在

$$\mathbb{P}(\mathrm{\exists }x:B_x)=2^{-n}⟶0.$$

几乎所有结果都好。

两模型具有完全相同的“候选熵” $n\log 2$ 和“单候选代价” $n\log 2$，却因依赖结构不同而得到相反结论。这精确暴露了边界：当 $b_n-a_n\to +\mathrm{\infty }$ 时，第一矩不需要知道依赖；当主指数打平时，重叠、精确常数及次指数项不能再被抹去。

4.3 今日全割定理为何不能冒充尖锐连通阈值

Section 1.4 要求

$$n{p}_n\ge \frac{8}{{\delta }^2}\log n,$$

并推出每个单点割都满足

$$\mathrm{deg}(v)\ge (1-\delta )p_n(n-1).$$

而在尖锐连通窗口

$$p_n=\frac{\log n+c}{n},$$

孤立点数仍收敛到非退化 Poisson 分布；图以非零极限概率含孤立点。故不可能在该窗口以概率趋于 $1$ 得到上述统一相对误差下界。

这里不是 Chernoff 界错了，而是目标性质比“连通”强得多：它要求所有顶点度数及所有割边数都接近各自均值。尖锐连通性只需排除零跨边割，并允许低度但非孤立的顶点。若要找回精确常数，必须针对“割边数恰为零”重新计算，按 $k$ 细分候选，并保留临界小集合的 Poisson 结构；不能用一个方便但过强的浓缩目标替代原问题。

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

今日一问。 令

$$p_n=\frac{\log n+c_n}{n},c_n\to +\mathrm{\infty },$$

并假设 $0\le p_n\le 1$ 对所有充分大的 $n$ 成立。

并令 $Z_n$ 为满足

$$1\le |S|\le \frac{n}{2},e_G(S,S^{\mathsf{c}})=0$$

的顶点集 $S$ 的个数。尝试仅用第一矩法证明

$$\mathbb{P}(Z_n>0)\to 0,$$

但必须把求和

$$\mathbb{E}{Z}_n=\sum _{k=1}^{\lfloor n/2\rfloor }(\genfrac{}{}{0ex}{}{n}{k})(1-p_n{)}^{k(n-k)}$$

分成至少三个尺度：固定或很小的 $k$、$k=o(n)$ 的中观区、$k\asymp n$ 的宏观区。

问题不在于机械估计总和，而在于辨认：哪个尺度给出最慢衰减？为什么宏观区的 $2^n$ 候选并非真正障碍，而 $k=1$ 在临界窗口却决定答案？若把 $c_n\to +\mathrm{\infty }$ 改成固定 $c$，上述第一矩目标的哪一部分不再趋于零？

方向提示。 对小 $k$ 使用 $(\genfrac{}{}{0ex}{}{n}{k})\le (en/k{)}^k$ 与 $(1-p{)}^{k(n-k)}\le e^{-pk(n-k)}$；对宏观 $k=\alpha n$ 比较 $nH(\alpha )$ 与 $p\alpha (1-\alpha )n^2$。不要一开始把所有 $k$ 都替换成最坏上界，否则会抹掉主导尺度。

数学地图。

$$\begin{array}{c}\text{Markov 不等式、独立和、凸优化}\\ \downarrow \\ \text{Chernoff 指数倾斜与 }D(q\parallel p)\\ \downarrow \\ \text{固定候选的 rate cost}\\ \downarrow \\ \text{二项系数、type class 与 combinatorial entropy}\\ \downarrow \\ \text{随机图割、Ramsey 随机染色、概率存在性}\\ \swarrow \searrow \\ \text{Cramér 原理、变化测度}\text{局部引理、Janson、容器、去随机化}\end{array}$$

三日 arc 的结构现已闭合：

$$\text{连通阈值的局部障碍}⟷\text{巨分量的分枝机制}⟷\text{候选熵与指数代价的统一证明预算}.$$

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

展开完整解答

可复用模板：由二阶导数下界建立强凸二次控制。

固定 $p\in (0,1)$，定义

$$F(q)=D(q\parallel p),q\in (0,1).$$

先计算一阶导数：

$$\begin{array}{rl}{F}^{\prime }(q)& =\frac{d}{dq}[q\log \frac{q}{p}+(1-q)\log \frac{1-q}{1-p}]\\ & =\log \frac{q}{p}+1-\log \frac{1-q}{1-p}-1\\ & =\log \frac{q(1-p)}{p(1-q)}.\end{array}$$

因此

$$F(p)=0,F^{\prime }(p)=0.$$

再求二阶导数：

$$F^{″}(q)=\frac{1}{q}+\frac{1}{1-q}=\frac{1}{q(1-q)}.$$

由

$$q(1-q)=\frac{1}{4}-{(q-\frac{1}{2})}^2\le \frac{1}{4},$$

得到

$$F^{″}(q)\ge 4$$

对所有 $q\in (0,1)$ 成立。

令

$$G(q)=F(q)-2(q-p{)}^2.$$

则

$$G^{″}(q)=F^{″}(q)-4\ge 0,$$

所以 $G$ 是凸函数。又有

$$G(p)=0,G^{\prime }(p)=F^{\prime }(p)-4(p-p)=0.$$

凸函数在导数为零的点取得全局最小值，故对每个 $q\in (0,1)$，

$$G(q)\ge G(p)=0.$$

即

$$\boxed{{\displaystyle D(q\parallel p)\ge 2(q-p{)}^2}}.$$

等号。 若 $q=p$，显然两边均为 $0$。反之若 $q\ne p$，连接 $p$ 与 $q$ 的非退化区间中不可能处处满足 $F^{″}=4$：等式 $F^{″}(u)=4$ 只在 $u=1/2$ 成立。因此强凸积分余项在该区间上严格大于 $2(q-p{)}^2$，故等号仅当

$$q=p.$$

边界延拓。 采用约定 $0\log 0=0$。若 $p\in (0,1)$ 而 $q=0$ 或 $q=1$，则由 $q\to 0^{+}$ 或 $q\to 1^{-}$ 的连续极限，结论仍成立：

$$D(0\parallel p)=\log \frac{1}{1-p},D(1\parallel p)=\log \frac{1}{p}.$$

若 $p=0$，则只有 $q=0$ 时散度有限，并且两边都为 $0$；对任意 $q>0$，$D(q\parallel 0)=+\mathrm{\infty }$，不等式在扩展实数意义下成立。$p=1$ 同理。于是结论延拓到所有 $p,q\in [0,1]$。

这个模板并不限于相对熵：若损失函数 $L(x)$ 在参数区间上满足 $L^{″}\ge m>0$，并在 $x_0$ 有 $L(x_0)=L^{\prime }(x_0)=0$，则自动得到

$$L(x)\ge \frac{m}{2}(x-x_0{)}^2.$$

它把“散度控制参数距离”归约为一项可重复的曲率检查。

资料与来源 (Sources)

1. Herman Chernoff, “A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the Sum of Observations,” The Annals of Mathematical Statistics 23(4), December 1952, 493–507, DOI 10.1214/aoms/1177729330。Project Euclid 页面给出论文摘要、书目信息，以及由矩母函数最小值控制和的尾概率这一原始语境：https://doi.org/10.1214/aoms/1177729330。
2. MIT OpenCourseWare, 6.265/15.070J Advanced Stochastic Processes, Lecture 2, “Large Deviations for i.i.d. Random Variables,” 9 September 2013。用于核对指数矩 Chernoff 推导、log-mgf 优化、Legendre transform 与“上界指数”的陈述：https://ocw.mit.edu/courses/15-070j-advanced-stochastic-processes-fall-2013/ed35842f2e902421e4a6cdd4d9eca6fe_MIT15_070JF13_Lec2.pdf。
3. Markus Fischer, Large Deviations, Weak Convergence, and Relative Entropy, University of Padua, revised 20 June 2013，Sections 2.1–2.3。用于核对 Bernoulli rate function $D(q\parallel p)$、Cramér 定理及大偏差上下界与单纯 Chernoff 上界的区别：https://www.math.unipd.it/~fischer/Didattica/WeakConvergenceRE.pdf。
4. P. Erdős, “Some Remarks on the Theory of Graphs,” Bulletin of the American Mathematical Society 53 (1947), 292–294, DOI 10.1090/S0002-9904-1947-08785-1。原文以标号图计数证明 Ramsey 指数下界；Section 1.5 将其等价改写为随机二染色的第一矩论证：https://www.ams.org/journals/bull/1947-53-04/S0002-9904-1947-08785-1/S0002-9904-1947-08785-1.pdf。
5. Noga Alon and Joel Spencer, “Response from Noga Alon and Joel Spencer,” in “2021 Leroy P. Steele Prizes,” Notices of the American Mathematical Society 68(4), April 2021, 629–630。用于核对 Alon 对 Erdős 1947 Ramsey 概率证明的回顾，以及该书以 methodology and ideas 组织概率方法的作者自述：https://www.ams.org/journals/notices/202104/rnoti-p629.pdf。
6. Scott Aaronson, “How to upper-bound the probability of something bad,” Shtetl-Optimized, 13 April 2018。Section 3 的英文短引、发布日期与上下文均逐字核对自作者原页：https://scottaaronson.blog/?p=3712。
7. Alan Frieze and Michał Karoński, Introduction to Random Graphs, online manuscript dated 20 February 2026，尤其 Chapter 1（thresholds）、Chapter 4（connectivity）、Chapter 29（first and second moment methods）与 Chapter 30（sums of independent bounded variables）。用于核对随机图语境中的候选计数、第一矩与 Chernoff 工具链：https://www.math.cmu.edu/~af1p/BOOK.pdf。
8. 《每日数学》2026-08-07，“最后一个孤点消失时：Erdős–Rényi 连通阈值与 Poisson 临界窗”，本地归档：/opt/data/output/daily-mathematics-journal/2026/08/2026-08-07.md；《每日数学》2026-08-08，“平均度越过一时：分枝过程、巨分量与临界双跃迁”，本地归档：/opt/data/output/daily-mathematics-journal/2026/08/2026-08-08.md。本期明确复用两期中的候选计数与指数尾机制，并新增相对熵率函数、统一割浓缩及概率方法桥梁。