关于从n个对象中选取至少k个的非平凡上界的技术问询

嘿，关于从n个对象里选至少k个的非平凡上界，我整理了几个实用的、经过验证的靠谱结论：

• Chernoff界推导的指数上界
  当k > n/2时，这个上界精度很高，特别好用：
  $$\sum_{i=k}^n \binom{n}{i} \leq 2^n \cdot \exp\left(-\frac{2(k - n/2)^2}{n}\right)$$
  它利用二项分布的尾部衰减特性，k离n/2越远，这个上界就越贴近真实值，完全避开了平凡的$2^n$。

• 简洁的代数放缩上界
  如果k ≤ n/2，用这个就很方便，计算简单还够用：
  $$\sum_{i=k}^n \binom{n}{i} \leq \frac{n}{n - k + 1} \binom{n}{k}$$
  这个是靠二项式系数的递推关系推导来的，把后面所有项都用$\binom{n}{k}$做放缩，日常估计完全足够。

• 基于对称性的精确变形上界
  当n是偶数时，$\sum_{i=k}^n \binom{n}{i} = 2^{n-1} + \frac{1}{2}\binom{n}{n/2}$（当k ≤ n/2时），这个其实是精确表达式的变形，直接就能当紧上界用；如果n是奇数，类似的可以写成$2^{n-1}$加上中间两项的一半，同样很精准。

要是你需要更高精度的估计，还可以用斯特林公式近似二项式系数后再对求和项放缩，就是计算起来会繁琐一点，适合对精度要求高的场景。

内容的提问来源于stack exchange，提问作者arl