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

Question

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.

Answer 1

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.