霍夫丁不等式---机器学习数学原理

霍夫丁不等式

霍夫丁不等式（Hoeffding’s inequality），在概率论中，该不等式给出了随机变量的和与其期望值偏差的概率上限。霍夫丁不等式被Wassily Hoeffding于1963年提出并证明。

霍夫丁不等式是一个Azuma-Hoeffding不等式的特例，并且他比Sergei Bernstein于1923年证明的Bernstein不等式更加具有广泛性。这几个不等式都是McDiarmid’s不等式的特例。这样，我们基本就把这几个不等式的关系理清楚了。

1 伯努利随机变量的特例

霍夫丁不等式经常被应用于一些独立分布的伯努利随机变量的重要特例中，这也是为什么这个不等式在计算机科学以及组合数学中如此常见。我们认为一个抛硬币时一个硬币A面朝上的概率为p，B面朝上的概率则为1-p。我们抛n次硬币，那么A面朝上次数的期望值为np。那么进一步我们可以知道，A面朝上的次数不超过k次的概率能够被下面的表达式完全确定：

这里的H(n)为抛n次硬币其A面朝上的次数。

对某一ε>0，当k=(p-ε)n时，上面不等式确定的霍夫丁上界将会按照指数级变化：

相似的,对某一ε>0,当k=(p+ε)n，霍夫丁不等式的概率边界同样可以确定为：

这样根据上面两个式子我们可以得到：

比如说现在我们令

那么可以得到

2 普遍情况

现在令X1，X2，…，Xn为[0,1]的独立随机变量，即0<=Xi<=1。我们定义这些变量的经验均值为：

在1963年霍夫丁提出该不等式，其中霍夫丁定理一中的一个不等式为：

当知道Xi严格的边界范围ai，bi（即Xi属于[ai,bi]）时，霍夫丁定理二更加广泛：

这个不等式也可以写成和的形式：

其中

需要注意的是对于Xi为不放回的抽样该等式依然成立；在这样的例子中这些随机变量不在是独立的了。这种情形的证明可以看Hoeffding在1963年发表的论文。如果需要一个在无放回抽样的例子中更好的边界，可以查看Serfling在1974年发表的论文。

3 证明

在这个部分，我们给出了霍夫丁不等式的证明。改证明使用了霍夫丁引理：

假设X为一均值为0的实数随机变量并且满足

那么有如下的不等式成立

使用这个引理，我们可以证明霍夫丁不等式。加入X1，X2，…，Xn为n个独立分布的随机变量并且满足

令

那么对于s,t>=0，Markov不等式以及Xi的独立性表明：

为了得到最好的概率上限，我们发现将不等式右边等为一个关于s的函数，现在关于s最小化该式子。定义

注意到g是一个二次函数，若要获取其最小值则虚满足

这样我们可以得到

4 使用实例

置信区间

霍夫丁不等式被用来分析样本的置信区间，我们可以通过定理一得到：

这个不等式说明了估计值比真值大t的概率被指数边界控制。对称的，以下的不等式同样成立：

将两式相加我们可以得到如下不等式：

上述不等式可以理解为：

即真值的估值范围。其中

所以，我们要求至少上述不等式右边式子的样本数量从而使得估值边间更加靠近真值。