Hoeffding’s Inequality

Let {X_1,...,X_n} be independent zero-mean real valued variables and let {S_n= \sum\limits_{i=1}^{n} X_i.} Then

\displaystyle \begin{array}{rcl} \text{If } a_i \leq X_i \leq b_i; \qquad &i&=1,..,n \text{ where } a_1, b_1,...,a_n, b_n \text{ constant then } \\ P(|S_n| \geq t) &\leq& 2 \exp \left( - \frac{2t^2}{\sum\limits_{i=1}^{n} (b_i-a_i)^2} \right), \qquad t>0 \end{array}

Continue reading “Hoeffding’s Inequality”

Advertisements