关于Park和Pham证明Kahn-Kalai猜想论文中不等式推导的技术问询

嗨，我来帮你拆解这个问题——你提到的最后一步不等式，确实是用了集中不等式里的经典结论，而且不是切比雪夫不等式（切比雪夫太松，达不到这里需要的下界），而是更常用的二项分布尾概率的Chernoff界（或者Hoeffding不等式，两者在二项分布场景下效果类似），这是组合概率里的“标准操作”，所以论文里只提了一句“standard concentration bound”。

咱们一步步理清楚：

首先先明确符号含义：

• $X_{p'}$是**$p'$-随机子集**：集合$X$里每个元素独立以概率$p'$被选中，它的大小$|X_{p'}|$服从二项分布$\text{Bin}(n, p')$，其中$n = |X|$。
• $m = (L p \log l)|X|$，就是定理里那个固定大小的子集规模。

第一步：先看前面的不等式铺垫 #

第一个不等式 $P(X_{p'} \in \langle \mathcal{H} \rangle ) \geq P(X_m \in \langle \mathcal{H} \rangle) P(|X_{p'}| \geq m)$ 是利用了$\langle \mathcal{H} \rangle$的上闭性（如果一个集合属于$\langle \mathcal{H} \rangle$，那么它的超集也属于$\langle \mathcal{H} \rangle$）：

假设$|X_{p'}| \geq m$，那么$X_{p'}$包含至少一个大小为$m$的均匀随机子集$X_m$；如果$X_m \in \langle \mathcal{H} \rangle$，那么$X_{p'}$作为超集必然也属于$\langle \mathcal{H} \rangle$。用条件概率展开后，就能得到这个下界。

而论文里前面已经通过那个定理得到了$P(X_m \in \langle \mathcal{H} \rangle) \geq 3/4$（当$l$足够大时，$1-o_{l\to\infty}(1)$可以取到大于3/4的常数），所以现在只需要证明$P(|X_{p'}| \geq m) > 2/3$，就能让$(3/4) \times (2/3) = 1/2$，从而得到最后一步的不等式。

第二步：用Chernoff界估计尾概率 #

这就是论文里说的“标准集中界”：对于二项分布$\text{Bin}(n, p')$，记它的期望$\mu = \mathbb{E}[|X_{p'}|] = n p'$。论文里的$p'$是特意选取的，会让$\mu$比$m$大一个常数倍数（比如$\mu = (1+\epsilon)m$，$\epsilon$是某个固定正数）。

根据Chernoff界的下界形式：对于$0 < \delta < 1$，有
$$P(X \geq (1-\delta)\mu) \geq 1 - e^{-\mu \delta^2 / 2}$$
这里我们取$(1-\delta)\mu = m$，也就是$\delta = 1 - \frac{m}{\mu}$。因为$\mu$和$m$都是$n$的线性倍数，$\delta$是一个固定的正数（比如如果$\mu = 2m$，那$\delta = 1/2$）。

当$n = |X|$足够大（或者随着$l\to\infty$，$n$可以任意大），$\mu = n p'$也会趋向无穷大，此时$e^{-\mu \delta^2 / 2}$会快速趋向0，所以$P(|X_{p'}| \geq m) = 1 - P(|X_{p'}| < m) > 1 - o(1)$。当$l$足够大时，这个概率可以轻松超过$2/3$，这样$(3/4) \times (2/3) = 1/2$，就得到了最后一步的严格不等式。

为什么不是切比雪夫？ #

切比雪夫不等式只能给出$P(|X - \mu| \geq t) \leq \frac{\text{Var}(X)}{t^2}$，它的上界太松，而且我们这里需要的是下界，切比雪夫没法直接给出足够紧的下界来满足我们需要的$>2/3$的概率，所以论文里说的集中界肯定是Chernoff/Hoeffding这类更紧的二项分布尾界。

备注：内容来源于stack exchange，提问作者GG314