Hoeffding's inequality (霍夫丁不等式)

引入

1. 设定投掷硬币的实验场景，其中出现正面的概率记为p，反面的概率则为1-p。在进行n次独立投掷后，正面出现的期望次数可表示为np。若希望确定在n次投掷中正面最多出现k次的概率，可通过以下公式进行计算

H(n)表示在n次硬币投掷过程中，正面出现的总次数。

2. 若设定k=(p-\varepsilon)n，且满足\varepsilon >0，则可推导出相应结果

3. 同样地，若设定k=(p+\varepsilon)n，则可得出对应的结论

4. 综合2与3的结果可知

常用形式解析

1. 设X_1,X_2,...,X_n为具有界性的独立随机变量，且满足0\le X_i\le1，设\overline X的期望为E(\overline X)，定义经验均值变量为

其满足如下不等式

其中$0

2. 在更为普遍的情形下，若随机变量X_i严格限定在区间[a_i,b_i]内

霍夫丁不等式同样适用于随机变量之和的情形，即对于S_n = X_1+X_2+...+X_n，其满足