1.6　Janson 不等式Janson’s inequality

每个 \(A\in\mathcal{A}\) 是一组下标，例如 \(A=\{2,5\}\)。对应的那一项 \(\prod_{j\in A}t_j=t_2 t_5\)，它等于 \(1\) 当且仅当 \(t_2=t_5=1\)（这一组下标“全部被点亮”），否则等于 \(0\)。所以

也就是说，\(X\) 在数“有多少组被完整点亮”。例如下图取 \(n=5\)，\(\mathcal{A}=\{\{1,2\},\{2,3\},\{4,5\}\}\)，若 \(t_1=t_2=t_3=1\)、\(t_4=1,t_5=0\)，则被完整点亮的组是 \(\{1,2\}\) 与 \(\{2,3\}\)，故 \(X=2\)。

若两组共用了下标，例如 \(A=\{1,2\}\) 与 \(B=\{2,3\}\) 都含 \(t_2\)，那么 \(\prod_{j\in A}t_j\) 与 \(\prod_{j\in B}t_j\) 就不独立：知道前者为 \(1\)（说明 \(t_2=1\)）会提高后者为 \(1\) 的概率。这正是 \(X\) 不能直接当成“独立项之和”来处理的根源。

(1.34) 说的是：对于布尔多项式 \(X,Y\)，把 \(e^{-s\,\cdot}\) 看成 \(X+Y\) 的单调函数，由正相关性，“先合后取期望”不小于“各自取期望再相乘”。这是下面证明能“拆开”的唯一缝隙——它取代了独立情形下的等式 \(\mathbb{E}\,e^{-s(X+Y)}=\mathbb{E}\,e^{-sX}\,\mathbb{E}\,e^{-sY}\)，只不过这里是“\(\ge\)”而非“\(=\)”。

求和只跑遍那些相交的有序对 \((A,B)\)（即 \(A\cap B\neq\varnothing\)，含 \(A=B\) 本身）。两组若相交，它们对应的项就互相牵连；\(\Delta\) 把所有这种牵连按 \(\mathbb{E}(\prod_{j\in A\cup B}t_j)\) 加权累加起来——它越大，说明项与项之间的依赖越强。

取 \(T=\mathbb{E}(X)\) 就得到最常用的特例 \(\mathbb{P}(X=0)\le \exp(-\mathbb{E}(X)^2/2\Delta)\)：只要平均还有不少东西（\(\mathbb{E}(X)\) 大）而依赖又不太强（\(\Delta\) 不太大），那么“一个都没有”几乎不可能发生。

当每个 \(A\) 只含一个下标时，两组 \(A=\{i\},B=\{j\}\) 相交当且仅当 \(i=j\)。于是相交对只有“对角线” \(A=B\) 这一种，

代入 \(\mathbb{P}(X\le\mathbb{E}(X)-T)\le\exp(-T^2/2\Delta)\)，就得到 \(\exp(-T^2/2\mathbb{E}(X))\)，正是独立 0/1 和式的标准下尾界（推论 1.9 的下半）。这说明 Janson 不等式是它的真正推广：把“互不相交的单点”换成“可能相交的子集”，代价就是分母从 \(\mathbb{E}(X)\) 变成更大的 \(\Delta\)。

1. 对固定的相交对 \((A,B)\)，把 \(A\cup B\) 分成两块：\(A\) 和 \(B\setminus A\)（两块无公共下标）。由独立性，\(\mathbb{E}\big(\prod_{j\in A\cup B}t_j\big)=\mathbb{E}\big(\prod_{j\in A}t_j\big)\cdot\mathbb{E}\big(\prod_{j\in B\setminus A}t_j\big)\)。
2. 把 \(\Delta\) 中关于 \(B\) 的求和提出来，\(\mathbb{E}\big(\prod_{j\in A}t_j\big)\) 是与 \(B\) 无关的公因子，得到第一个等式。
3. 把内层那个对 \(B\) 的和用它在所有 \(A\) 上的上确界 \(\sup_A\) 放大，再注意外层的 \(\sum_A\mathbb{E}(\prod_{j\in A}t_j)\) 恰是 \(\mathbb{E}(X)\)，便得到 (1.35)。

(1.35) 的意义：要控制 \(\Delta\)，只需对每一个 \(A\) 估出“与它相交的那些 \(B\) 所贡献的、扣掉重叠部分后的期望之和”，取最坏的一个即可。这把全局的双重求和化成了局部的、逐 \(A\) 的检验。

把对称关系 \(i\sim j\) 看成一张图：顶点是 \(1,\dots,n\)，把每个满足 \(i\sim j\) 的对 \(\{i,j\}\) 连一条边。让每个顶点 \(j\) 以概率 \(\mathbb{E}(t_j)\) 独立地“被选中”（\(t_j=1\)）。则 \(t_i t_j=1\) 当且仅当一条边的两个端点都被选中，于是

“\(X=0\)” 就是“没有任何一条边的两端同时被选中”。下面验证那个不等式里 \(1+2\sup_i(\cdots)\) 是怎么来的：固定一条边 \(A=\{i,j\}\)，与它相交的边 \(B\) 分三类。

三类相加正好给出上界 \(1+2\sup_i\sum_{j:i\sim j}\mathbb{E}(t_j)\)。再把它放进 (1.35) 的 \(\sup_A\) 处、令 \(T=\mathbb{E}(X)\) 用定理 1.28，分母里的 \(2\Delta\) 就被 \(2\mathbb{E}(X)\cdot\big(1+2\sup(\cdots)\big)=\mathbb{E}(X)\cdot\big(2+4\sup(\cdots)\big)\) 代替，约去一个 \(\mathbb{E}(X)\) 后即得推论 1.30。

原始 \(r_{P+B+B}(n)\) 把所有满足 \(i+j=n-p\) 的对都算进来，包括 \(i=j\)（重复计数）和很小的 \(i,j\)（那里 \(\mathbb{P}(i\in B)=\min(c/i,1)\) 可能等于 \(1\)，破坏估计）。\(Y_n\) 只保留 \(i>j\ge n^{2/3}\)（去掉小下标、去掉对角线 \(i=j\)），正好凑成推论 1.30 里那种“对称关系下的二次多项式”。因为 \(Y_n\le r_{P+B+B}(n)\)，证明 \(Y_n>0\) 的概率高，就更强地保证了 \(r_{P+B+B}(n)>0\)。\(n-P\) 表示集合 \(\{n-p:p\in P,\ p

1. 分母（依赖项）：\(\sum_j \mathbb{E}(t_j)=O(c)\)，所以推论 1.30 的分母 \(2+4\cdot O(c)=O(c)\)。
2. 分子（平均值）：\(\mathbb{E}(Y_n)=\Theta(c^2\log n)\)，它随 \(n\to\infty\) 而趋于无穷，正是“平均上有很多种表示”。
3. 相除：指数里的量 \(=\dfrac{\Theta(c^2\log n)}{O(c)}=\Theta(c\log n)\)，故 \(\mathbb{P}(Y_n=0)\le e^{-\Theta(c\log n)}=n^{-\Theta(c)}\)。
4. 选 \(c\)：把 \(c\) 取大到使 \(\Theta(c)\ge 2\)，便有 \(\mathbb{P}(Y_n=0)=O(1/n^2)\)。再用 Borel–Cantelli，几乎必然只有有限个 \(n\) 表示不出来——把这有限个补进 \(B\)，并不破坏 (1.36) 的 \(O(\log n)\) 稀疏性。

关键点：分子是 \(c\) 的二次、分母是 \(c\) 的一次，所以增大 \(c\) 能让“失败概率”任意快地变小——这正是 Janson 不等式（经推论 1.30）赋予我们的杠杆。

1. Markov / 指数矩：对任意 \(t>0\)，事件 \(\{X\le \mathbb{E}(X)-T\}\) 等价于 \(\{e^{-tX}\ge e^{-t(\mathbb{E}(X)-T)}\}\)（因 \(x\mapsto e^{-tx}\) 递减）。对非负量 \(e^{-tX}\) 用 Markov 不等式即得第一行。我们的目标就是为某个聪明选取的 \(t\) 把右边压到 \(e^{-T^2/2\Delta}\)。
2. 用积分表示 \(\log F\)：因为 \(F(0)=\mathbb{E}(e^0)=1\)，\(\log F(t)=\log F(t)-\log F(0)=\int_0^t (\log F)'(s)\,ds=\int_0^t \frac{F'(s)}{F(s)}\,ds\)。把对数化成积分，是为了能逐点（对每个 \(s\)）做估计。
3. \(F'\) 的分解：\(F'(s)=\frac{d}{ds}\mathbb{E}(e^{-sX})=-\mathbb{E}(Xe^{-sX})\)。再把 \(X=\sum_A\prod_{j\in A}t_j\) 代入，每一项 \(\mathbb{E}(e^{-sX}\prod_{j\in A}t_j)\) 中的 \(\prod_{j\in A}t_j\) 是 \(0/1\) 的指示量，等于 \(1\) 恰好就是事件 \(E_A\)；于是 \(\mathbb{E}(e^{-sX}\prod_{j\in A}t_j)=\mathbb{E}(e^{-sX}\mid E_A)\mathbb{P}(E_A)\)。这就把整体期望换成了“在 \(A\) 已被点亮的条件下”的期望——为下一步“拆掉与 \(A\) 无关的部分”做准备。

固定 \(A\)，把所有 \(B\in\mathcal{A}\) 按“是否与 \(A\) 相交”分成两堆：

• \(Y_A\)：与 \(A\) 相交的那些 \(B\) 的项之和——它们与“\(A\) 是否点亮”相互牵连。
• \(Z_A\)：与 \(A\) 不相交的那些 \(B\) 的项之和——它们只用到 \(A\) 之外的变量，因此与 \(E_A\) 完全独立。

1. 由正相关 (1.34)，\(\mathbb{E}(e^{-sX}\mid E_A)=\mathbb{E}(e^{-s(Y_A+Z_A)}\mid E_A)\ge \mathbb{E}(e^{-sY_A}\mid E_A)\mathbb{E}(e^{-sZ_A}\mid E_A)\)。
2. \(Z_A\) 独立于 \(E_A\)，故取条件没影响：\(\mathbb{E}(e^{-sZ_A}\mid E_A)=\mathbb{E}(e^{-sZ_A})\)。又 \(Z_A\le X\)（少了若干非负项），所以 \(e^{-sZ_A}\ge e^{-sX}\)，取期望得 \(\ge F(s)\)。
3. 把这个 \(\ge F(s)\) 代回，分母上的 \(F(s)\) 正好被约掉——这就是为何上一步要凑出 \(\frac{\mathbb{E}(e^{-sX}\mid E_A)}{F(s)}\) 这个比值。剩下只需控制带 \(Y_A\) 的项。

1. 第一次 Jensen（对一个 \(A\)）：\(e^{-sx}\) 是凸函数，凸函数的期望不小于期望处的函数值，即 \(\mathbb{E}(e^{-sY_A}\mid E_A)\ge e^{-s\mathbb{E}(Y_A\mid E_A)}\)。把“先指数后平均”换成“先平均后指数”的下界。
2. 第二次 Jensen（对所有 \(A\) 加权平均）：把权重 \(\frac{\mathbb{P}(E_A)}{\mathbb{E}(X)}\)（它们之和为 \(1\)，因 \(\sum_A\mathbb{P}(E_A)=\mathbb{E}(X)\)）作用在凸函数 \(e^{-s\,\cdot}\) 上，得到加权平均的下界，指数上出现 \(\frac{\sum_A\mathbb{P}(E_A)\mathbb{E}(Y_A\mid E_A)}{\mathbb{E}(X)}\)。
3. 认出 \(\Delta\)：\(\mathbb{P}(E_A)\mathbb{E}(Y_A\mid E_A)=\mathbb{E}(\mathbb{I}(E_A)Y_A)\)，展开 \(Y_A\) 即 \(\sum_{B:A\cap B\neq\varnothing}\mathbb{E}(\mathbb{I}(E_A)\prod_{j\in B}t_j)\)。又 \(\mathbb{I}(E_A)=\prod_{j\in A}t_j\)，故 \(\mathbb{I}(E_A)\prod_{j\in B}t_j=\prod_{j\in A\cup B}t_j\)（重复的 \(t_j\) 因 \(0/1\) 而 \(t_j^2=t_j\)）。对 \(A,B\) 求和恰好就是 \(\Delta\) 的定义。
4. 积分：\(\int_0^t e^{-s\Delta/\mathbb{E}(X)}ds=\frac{\mathbb{E}(X)}{\Delta}\big(1-e^{-t\Delta/\mathbb{E}(X)}\big)\)，乘上前面的 \(\mathbb{E}(X)\) 得 (1.38) 的第一项。
5. 代入 \(t=T/\Delta\) 并用二阶泰勒下界 \(1-e^{-u}\ge u-u^2/2\)（这里 \(u=T/\mathbb{E}(X)\in[0,1]\)），逐项展开化简，最后三项合并恰好得到 \(\frac{T^2}{2\Delta}\)。

这一串不等式全是“\(\ge\)”方向：每一步都把目标量往下压，最终仍不小于 \(\frac{T^2}{2\Delta}\)，于是回到取对数前就是 \(\mathbb{P}(X\le\mathbb{E}(X)-T)\le e^{-T^2/2\Delta}\)。

整个证明的命脉是 (1.34)：\(\mathbb{E}\,e^{-s(X+Y)}\ge\mathbb{E}\,e^{-sX}\mathbb{E}\,e^{-sY}\)。它来自正相关，而正相关只在 \(e^{-s\,\cdot}\)（\(s>0\) 时递减）这一个方向上给出我们需要的“\(\ge\)”。若想控制上尾 \(\mathbb{P}(X\ge\mu+T)\)，需要 \(\mathbb{E}\,e^{+sX}\) 的上界，而正相关此时给的是反向的不等号，论证就断了。因此上尾要用别的工具（下一节）。