# 霍夫丁不等式

## 2. 定义

$\begin{array}{c} P[\bar{\boldsymbol{X}} - E(\bar{\boldsymbol{X}}) \geq t] \leq \exp{(-\frac{2N^2t^2}{\sum_{i=1}^N(b_i-a_i)^2})} \\ P[E(\bar{\boldsymbol{X}}) - \bar{\boldsymbol{X}} \geq t] \leq \exp{(-\frac{2N^2t^2}{\sum_{i=1}^N(b_i-a_i)^2})} \\ \end{array}$

### 证明

$\begin{array}{cc} E(e^{s(\boldsymbol{X}-E(\boldsymbol{X}))}) \leq \exp{(\frac{1}{8} s^2 (b_i - a_i)^2)} & (1 \leq i \leq n) \end{array}$

$\boldsymbol{S}_n = \boldsymbol{X}_1 + \boldsymbol{X}_2 + \cdots + \boldsymbol{X}_n$，对于 $\forall s,t \gt 0$，可得

$\begin{array}{c} P(\boldsymbol{S}_n - E(\boldsymbol{S}_n) \geq t) = P(e^{s(S_n - E(S_n))} \geq e^{st}) \end{array}$

$\begin{array}{rl} P(e^{s(S_n - E(S_n))} \geq e^{st}) & \leq e^{-st} E(e^{s(\boldsymbol{S}_n-E(\boldsymbol{S}_n))}) \\ & = e^{-st} \prod_{i=1}^n E(e^{s(\boldsymbol{X}_i-E(\boldsymbol{X}_i))}) \\ & \leq e^{-st} \prod_{i=1}^n e^{\frac{s^2(b_i-a_i)^2}{8}} \\ & = \exp{(-st + \frac{1}{8} s^2 \sum_{i=1}^n (b_i - a_i)^2)} \end{array}$

$g(s) = -st + \frac{s^2}{8} \sum_{i=1}^n (b_i - a_i)^2$，则 $g(s)$ 为关于 $s$ 的二次函数，从而易得

$\begin{array}{c} s = \frac{4t}{\sum_{i=1}^n (b_i - a_i)^2} \end{array}$

$g(s)$ 的最小值点。由于

$\begin{array}{c} P(e^{s(S_n - E(S_n))} \geq e^{st}) \leq \exp{(-st + \frac{1}{8} s^2 \sum_{i=1}^n (b_i - a_i)^2)} \end{array}$

$\forall s \gt 0$ 都成立，因此当 $s$$g(s)$ 的最小值点时，得到 $P(e^{s(S_n - E(S_n))} \geq e^{st})$ 的紧上界，即

$\begin{array}{c} P(e^{s(S_n - E(S_n))} \geq e^{st}) \leq \exp{(-\frac{2t^2}{\sum_{i=1}^n (b_i - a_i)^2})} \end{array}$