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.

  • 2
    $\begingroup$ Please add the [self-study] tag & read its wiki. $\endgroup$ – gung - Reinstate Monica Jun 7 '15 at 9:27
  • $\begingroup$ 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? $\endgroup$ – 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.

| cite | improve this answer | |
  • 3
    $\begingroup$ +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. $\endgroup$ – Dilip Sarwate Jun 7 '15 at 13:19
  • $\begingroup$ Well, if $X$ and $Y$ are independent random variables then $g(X)$ and $h(Y)$ are also independent random variables :) $\endgroup$ – P.Windridge Jun 7 '15 at 13:36
  • $\begingroup$ (I accept your point though, and have edited accordingly!) $\endgroup$ – P.Windridge Jun 7 '15 at 13:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.