Tail Bound

释义 Definition

Tail bound（尾部界/尾界）指在概率论与统计中，用不等式或上界来约束随机变量“尾部概率”的工具，即对形如 \( \Pr(X \ge t) \) 或 \( \Pr(|X-\mathbb{E}X|\ge t) \) 的概率给出上界，用于说明“大偏差事件”发生的可能性有多小。（常见于“集中不等式”与随机算法分析中。）

发音 Pronunciation (IPA)

/teɪl baʊnd/

例句 Examples

The tail bound shows that large errors are very unlikely.
尾部界表明出现很大误差的可能性很小。

Using a Chernoff tail bound, we can prove the algorithm fails with probability at most \(n^{-2}\).
利用 Chernoff 尾部界，我们可以证明该算法失败的概率至多为 \(n^{-2}\)。

词源 Etymology

tail 原义是“尾巴”，在概率分布里引申为分布曲线两端的“尾部”（代表极端大/小的取值区域）；bound 表示“界/上界/限制”。合起来 tail bound 就是“对尾部概率给出界限”的意思。该用法主要形成并流行于现代概率论、统计学习与计算机科学（随机过程、随机算法）的写作传统中。

相关词 Related Words

• Concentration Inequality
• Tail Probability
• Chernoff Bound
• Hoeffding’s Inequality
• Markov Inequality
• Chebyshev’s Inequality
• Azuma’s Inequality
• Large Deviations
• Subgaussian

文学与著作 Literary Works

• Probability and Computing: Randomized Algorithms and Probabilistic Analysis（Mitzenmacher & Upfal）中大量使用 tail bounds（如 Chernoff/Hoeffding）分析随机算法。
• Randomized Algorithms（Motwani & Raghavan）以 tail bounds 作为证明算法成功率与误差控制的核心工具。
• Concentration Inequalities: A Nonasymptotic Theory of Independence（Boucheron, Lugosi & Massart）系统整理各类 tail bounds/集中不等式及其应用。