Hoeffding’s inequality 에 대해 알아보겠습니다. 회프딩의 부등식이라고 부를 수 있을것 같네요. 회프딩의 부등식은 random variable 의 특성을 보여주는 부등식 중 하나입니다.
Hoeffding’s inequality (회프딩의 부등식)
$X_1,X_2…,$을 n개의 random variable 이라고 합시다. 그리고 almost surely $a_i \leq X_i \leq b_i$라고 합시다. 그러면 아래와 같은 부등식을 Hoeffding’s inequality 라고 부릅니다.
모든 $t>0$에 대하여
$$P\left(\sum_{k=1}^n X_k – E\left[\sum_{k=1}^n X_k\right] \geq t \right) \leq \exp \left( – \frac{2t^2}{\sum_{k=1}^n (b_k-a_k)^2} \right)$$
혹은 아래와 같은 부등식을 Hoeffding’s inequality 라고 부릅니다.
$$P\left(\left|\sum_{k=1}^n X_k – E\left[\sum_{k=1}^n X_k\right]\right| \geq t\right) \leq 2 \exp \left( – \frac{2t^2}{\sum_{k=1}^n (b_k-a_k)^2} \right)$$