Hoeffding's Inequality

In probability theory, Hoeffding's inequality provides an upper bound on the probability that the sum of bounded independent random variables deviates from its expected value by more than a certain amount. Hoeffding's inequality was proven by Wassily Hoeffding in 1963

Let $X_1,\cdots ,X_n$ be independent random variables such that $a_i\le X_i\le 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$

$$\begin{array}{rl}\mathbb{P}\left(S_n-\mathbb{E}\left[S_n\right]\ge t\right)& \le \exp \left(-\frac{2t^2}{{\sum }_{i=1}^n(b_i-a_i{)}^2}\right)\\ \mathbb{P}\left(\left|S_n-\mathbb{E}\left[S_n\right]\right|\ge t\right)& \le 2\exp \left(-\frac{2t^2}{{\sum }_{i=1}^n(b_i-a_i{)}^2}\right)\end{array}$$