# Chernoff Bound: Prove that $P[u \geq \alpha] \leq (e^{-s\alpha} U(s))^N$

Let $u_1, ..., u_N$ be random variables, and let $u = \frac{1}{N} \sum_{n=1}^N u_n$. If $U(s) = E_{u_n}(e^{su_n})$ (for any $n$), prove that $P[u \geq \alpha] \leq (e^{-s\alpha} U(s))^N$.

$s > 0$ and $\alpha$ is a positive constant. E is the expectation. P is the probability.

I can show that for one variable case, $P(u \geq \alpha) \leq e^{-s\alpha}E_{u}(e^{su})$. However, I can't relate it to the case when we take the weighted average of the random variable.

• Please add the [self-study] tag & read its wiki. – gung - Reinstate Monica Jun 7 '15 at 9:27
• The random variables should be independent too? A suggestion/plea- use upper case letters for random variables! How have you tried to generalise your $N=1$ proof? – P.Windridge Jun 7 '15 at 12:29

Assuming your random variables are independent: $$\mathbb{P}\!\left( \sum_{i=1}^N u_i / N \ge \alpha \right) = \mathbb{P}\!\left( s\sum_{i=1}^N u_i / N \ge s\alpha\right) = \mathbb{P}\!\left( e^{s\sum_{i=1}^N u_i} \ge e^{Ns\alpha}\right) \\ \le \mathbb{E}\!\left[ e^{s\sum_{i=1}^N u_i}\right] e^{-Ns\alpha} = \mathbb{E}\!\left[\prod_{i=1}^N e^{su_i}\right] e^{-Ns\alpha} \\ = \prod_{i=1}^N \mathbb{E}[ e^{su_i}] e^{-Ns\alpha}.$$
The last equality follows from $\mathbb{E}[g(X)h(Y)] = \mathbb{E}[g(X)]\mathbb{E}[h(Y)]$ for $X,Y$ independent.
• +1 Actually, the last equality follows from $\mathbb{E}[g(X)h(Y)] = \mathbb{E}[g(X)]\mathbb{E}[h(Y)]$ for $X, Y$ independent. $\mathbb{E}[XY] = \mathbb{E}[X]\mathbb{E}[Y]$ also holds for uncorrelated random variables $X$ and $Y$, but the Chernoff bound does not follow from this. – Dilip Sarwate Jun 7 '15 at 13:19
• Well, if $X$ and $Y$ are independent random variables then $g(X)$ and $h(Y)$ are also independent random variables :) – P.Windridge Jun 7 '15 at 13:36