ML2

Hoeffding Inequality

Let $x_1$, $x_2$, $x_3$,…,$x_n$ be independent random variables, all bounded within an interval $[𝑎,𝑏]$. Define the empirical mean of these variables as:

$$ S_n = \sum_{i=1}^n x_i$$

Here is the true mean (the expected value) of these variables

$$\mathbb{E}[X]=\sum_{i=1}^n x_iP(X=x_i)$$

Now, here is the inequality equations ($\mathbb{E}[S_n]$ here is not true mean):

for $|X_i| \leq a_i$, for all $t \gt0$ :
$$\mathbb{P}{S_n-\mathbb{E}[S_n] \geq t } \leq exp(\frac{-t^2}{2 \sum_{i=1}^n a_i^2})$$
also
$$\mathbb{P}{\mathbb{E}[S_n]- S_n\geq t } \leq exp(\frac{-t^2}{2 \sum_{i=1}^n a_i^2})$$