Hoeffding 不等式

每个变量被限制在有限区间内，所以单次观测不可能对总和施加任意大的冲击；独立性又让指数矩按乘积拆开。优化指数 Markov 界后，偏差 $t$ 以 $e^{-c{t}^2}$ 的速度衰减。该界只使用取值范围而忽略实际方差，因此稳健但有时并不锐利。

对独立 Bernoulli 样本均值，

变量相关或无界时不能直接使用；有方差信息时 Bernstein 类界可能更紧。

若 $X_1,\dots ,X_{100}$ 是独立 $[0,1]$ 变量，则

样本量增到 $1000$ 时同一偏差上界降为 $2e^{-20}$。若所有 $X_i$ 实际上相同，平均并未降低随机性，直接套用独立版 Hoeffding 会给出虚假的指数集中。

不等式把独立性公理库独立性Statistical independence若干事件、σ-代数或随机元素的所有有限联合概率都按边缘概率乘积分解。、期望公理库期望Expectation · Expected value实值或复值随机变量关于概率测度的 Lebesgue 积分，概括加权平均与总体质量平衡。和有界性组合成有限样本保证，并可视为大数律公理库强大数定律Law of large numbers · Strong law of large numbers · SLLN独立同分布且可积时，样本均值沿几乎每条无限样本路径收敛到共同期望。的定量强化。对有界 IID 被积函数，Monte Carlo 样本均值公理库Monte Carlo 积分Monte Carlo integration · Monte Carlo quadrature将积分改写为随机变量期望，以独立样本均值估计并用方差和概率假设量化随机误差。可直接使用这个非渐近界；它不同于中心极限定理公理库中心极限定理Central limit theorem适当归一化的独立随机变量和在分布上趋于正态分布。给出的渐近正态误差条。与只使用方差公理库方差Variance随机变量相对其均值的平方偏差期望，也是最佳常数平方预测的剩余误差。的 Chebyshev 型界相比，它给指数尾。

若检验统计量是固定的有界样本平均，Hoeffding 可直接校准有限样本拒绝阈值；反演同一尾界还能构造保守的置信区间公理库置信区间Confidence interval · Confidence set由样本决定、在重复抽样下以规定概率覆盖固定参数目标的随机集合。。这只处理预先规定的一项统计量和一次覆盖事件；数据依赖选择、多重检验或可选停止必须把选择路径纳入共同概率界，不能继续引用单次尾界。

学习中，Hoeffding 首先控制一个预先固定假设的经验风险；有限假设类界公理库有限假设类泛化界Finite-class generalization bound固定假设的集中加上对有限类并集，得到同时成立的风险偏差界。再用并集界公理库并集界Union bound · Boole 不等式多个坏事件中至少一个发生的概率，不超过各事件概率之和。形成所有假设同时成立的事件。若 $h$ 是看过同一训练集后才挑出的，直接把它当固定 $h$ 会遗漏选择偏差。统计查询公理库统计查询模型statistical query model · SQ model让学习器查询有界统计量的近似期望，并以查询数、容差和计算量衡量效率。可用有界样本平均模拟近似期望；UCB公理库UCB 算法UCB1 · upper confidence bound algorithm在有界随机多臂赌博机中选择经验均值加置信半径最大的手臂。则在自适应拉臂过程中反复读取经验均值，必须先对确定的臂内样本数建立共同置信事件，不能把随机 $N_i(t)$ 无条件代入固定 $n$ 公式。

哈希负载、流式计数与随机舍入公理库随机舍入randomized rounding把分数解解释为选择概率，以期望、浓缩和修补把凸松弛转成离散近似解。也常把许多有界随机量相加。只有当所需独立性或条件独立性成立时才能直接使用本页；cuckoo hashing 的位移链、同一随机种子生成的 Sketch 坐标或满足全局约束的舍入变量可能彼此依赖，需要 martingale、有限独立性分析或负相关版本。漂亮的指数式不能代替依赖检查。