Stat/Junk
Inequalities
Hoeffding's inequality Let $X_1, \cdots , X_n$ be independent random variables such that $a_{i} \leq X_{i} \leq b_{i}$ almost surely. Consider the sum of these random variables, $S_n = X_1 + \cdots + X_n.$ Then Hoeffding's theorem states that, for all $t > 0$, $$ P \left( S_{n} - E \left[S_{n}\right] \geq t \right) \leq \text{exp} \left( - \frac{2t^2}{\sum _{i = 1}^{n}(b_{i} - a_{i})^2} \right) ..
