Hoeffding 不等式

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

对独立 Bernoulli 样本均值及 $\epsilon >0$，

这里每个 Bernoulli 变量的区间宽度为 $1$，将总和偏差取为 $n\epsilon$，就得到均值中的指数 $-2n{\epsilon }^2$。

给定 $\epsilon >0$ 和 $0<\delta <1$，若希望独立 $[0,1]$ 变量的样本均值以至少 $1-\delta$ 的概率落在其期望的 $\epsilon$ 邻域内，令 $2e^{-2n{\epsilon }^2}\le \delta$，解得

例如要求误差至多 $0.1$、失败概率至多 $0.05$，取 $n=185$ 就满足这一充分条件。

独立性使增加样本有效。若 $X_i=Z$ 全部复制同一个 Bernoulli$(1/2)$ 变量，则任何样本量下平均都等于 $Z$，偏离均值至少 $1/4$ 的概率始终为 $1$，与指数衰减不同。有方差信息时，Bernstein 类界还能利用实际波动尺度细化范围界。

不等式把独立性公理库独立性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 型界相比，它给指数尾。

对固定整数 $n\ge 1$ 个独立 $[0,1]$ 变量的样本平均，给定 $0<\delta <1$，反解尾界得到半径 $r_n=\sqrt{\log \left(2/\delta \right)/(2n)}$，因此 $[\overline{X}-r_n,\overline{X}+r_n]$ 覆盖平均期望的概率至少为 $1-\delta$，给出有限样本置信区间公理库置信区间Confidence interval · Confidence set以重复抽样覆盖率校准参数区间，并从正态枢轴与二项等尾检验反演算出有限样本端点。。若要同时覆盖多项统计量，可为每项分配失败概率，再用并集界控制总失败概率。

学习中，Hoeffding 控制一个固定假设的经验风险；有限假设类界公理库有限假设类泛化界Finite-class generalization bound固定假设的集中加上对有限类并集，得到同时成立的风险偏差界。对全部假设使用并集界公理库并集界Union bound · Boole 不等式多个坏事件中至少一个发生的概率，不超过各事件概率之和。，构造共同事件，从而覆盖看过数据后选出的假设。统计查询公理库统计查询模型statistical query model · SQ model让学习器查询有界统计量的近似期望，并以查询数、容差和计算量衡量效率。可借有界样本平均估计期望；UCB公理库UCB 算法UCB1 · upper confidence bound algorithm在有界随机多臂赌博机中选择经验均值加置信半径最大的手臂。则先对各臂及确定的样本数建立共同置信事件，再在这个事件中读取自适应时刻的均值。

独立的随机舍入公理库随机舍入randomized rounding从连续松弛解生成随机离散解，以覆盖补选证明每次可行性与期望成本，并区分独立坐标与共享超平面的舍入。也会产生有界变量之和，区间宽度直接进入 Hoeffding 界。依赖输入的集中分析则从相应结构出发：鞅差分使用条件指数矩，负相关变量使用能够保留乘积上界的性质。