Hoeffding 不等式（霍夫丁不等式）简介

霍夫丁（Hoeffding）不等式

内容主要来自网络上的各个博客。

简介

从一个装有绿色和黄色的罐子里随机地摸出小球，根据摸出小球的概率来估计整个罐子中绿色球和黄色球的所占的比例。

那么当抽出的样本数越多，最终预测出的绿球占整个罐子中小球的概率 u 会越趋近于实际罐子中绿色小球占整个罐子小球的概率 v。

\mathbb P(\left | v-u \right |<\epsilon) \leq 2\cdot e^{-2\cdot \epsilon^2 \cdot N}

所以就有了霍夫丁不等式，在一个含有 N 个样本数（N 足够大）的数据集中，在误差允许的范围内，u 和 v 可以不断地靠近。左侧的概率随着 N 的增大而减少，所以，要减少预测和实际之间的误差，就要增大样本数量。

证明思路

根据目前搜集到的资料，霍夫丁（Hoeffding）不等式似乎适用于符合伯努利分布的问题，因此基础的证明思路如下：

后面补吧，暂时有事。