定理 D.2 Hoeffding 不等式

定理 D.2 Hoeffding 不等式

• 设 $X_1,\dots ,X_m$ 为独立随机变量，
  • $X_i$ 取值在 $\left[a_i,b_i\right]$ 内对所有 $i\in \left[m\right]$ 成立。
• 那么，对于任意 $ϵ>0$
  • 以下不等式对 $S_m=\sum _{i=1}^m{X}_i$ 成立:

$$\begin{array}{rl}\mathbb{P}\left[S_m-\mathbb{E}[S_m]\ge ϵ\right]& \le e^{-2{ϵ}^2/{\sum }_{i=1}^m{(b_i-a_i)}^2}\\ \mathbb{P}\left[S_m-\mathbb{E}[S_m]\le -ϵ\right]& \le e^{-2{ϵ}^2/{\sum }_{i=1}^m{(b_i-a_i)}^2}.\end{array}\text{\hspace{1em}(D.4)(D.5)}$$

\begin{proof} 使用 Chernoff 边界技巧和引理 D.1，我们可以写出:

$$\begin{array}{rl}& \mathbb{P}\left[S_m-\mathbb{E}[S_m]\ge ϵ\right]\\ & \le e^{-tϵ}\mathbb{E}\left[e^{t(S_m-\mathbb{E}[S_m])}\right]\\ & =e^{-tϵ}\prod _{i=1}^m\mathbb{E}\left[e^{t(X_i-\mathbb{E}[X_i])}\right]\text{(independence of }{X}_i\text{s)}\\ & \le e^{-tϵ}\prod _{i=1}^m{e}^{t^2(b_i-a_i{)}^2/8}(\text{lemma D.1})\\ & =e^{-tϵ}{e}^{t^2{\sum }_{i=1}^m(b_i-a_i{)}^2/8}\\ & \le e^{-2{ϵ}^2/{\sum }_{i=1}^m(b_i-a_i{)}^2}.\end{array}$$

其中我们选择 $t=4ϵ/\sum _{i=1}^m{\left(b_i-a_i\right)}^2$ 以最小化上界。 这证明了定理的第一个陈述，第二个陈述以类似方式证明。 \end{proof}