Chernoff Bound

释义 Definition

Chernoff bound（切尔诺夫界）：概率论与随机算法中常用的一类尾界不等式，用于给出独立（或近似独立）的随机变量之和偏离其期望值的概率上界。它通常说明：偏离越大，发生概率会以指数速度变小。常见于分析二项分布、抽样误差、哈希、随机化算法与复杂度等场景。（也存在多种形式与推广版本。）

发音 Pronunciation (IPA)

/ˈtʃɜːrnɔːf baʊnd/

例句 Examples

The Chernoff bound shows that the error probability decreases exponentially with more samples.
切尔诺夫界表明：样本数越多，出错概率会以指数速度下降。

Using a Chernoff bound, we can prove that the number of collisions in the hash table is tightly concentrated around its expectation.
利用切尔诺夫界，我们可以证明哈希表中的碰撞次数会高度集中在其期望值附近。

词源 Etymology

“Chernoff”来自数学家 Herman Chernoff（赫尔曼·切尔诺夫） 的姓氏；“bound”意为“界/上界”。该术语用来指代以切尔诺夫相关工作为基础发展起来的一系列概率上界工具，后来在计算机科学（随机算法、理论计算机）中被广泛采用。

相关词 Related Words

• Concentration Inequality
• Tail Bound
• Hoeffding's Inequality
• Markov's Inequality
• Chebyshev's Inequality
• Azuma–Hoeffding Inequality
• Union Bound
• Law of Large Numbers

文学与经典著作 Literary Works

• Randomized Algorithms — Rajeev Motwani & Prabhakar Raghavan（随机算法经典教材中系统使用 Chernoff bounds）
• Probability and Computing: Randomized Algorithms and Probabilistic Analysis — Michael Mitzenmacher & Eli Upfal（概率与计算教材中多处给出切尔诺夫界及应用）
• Introduction to Algorithms — Cormen, Leiserson, Rivest, Stein（CLRS；在随机化与概率分析章节中引用/使用切尔诺夫界）
• The Probabilistic Method — Noga Alon & Joel H. Spencer（概率方法经典著作中广泛使用各类集中不等式，包括切尔诺夫界）