Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Suppose $X_1,X_2,...$ are i.i.d. random variables such that $E[X_j]=0$ and $P\{|X_j|>K\}=0$ for $K<\infty$. Show that $\forall t>0,\epsilon>0, P\{X_1+...+X_n\geq \epsilon n\}\leq [M(t)e^{-t\epsilon}]^n$, where $M(t) = E[e^{tX_j}]$.

Here's my attempt so far:
I note that $P\{X_1+...+X_n\geq \epsilon n\}=P\{X_1\geq\epsilon n\}+...+P\{X_n\geq\epsilon n\}$ but I'm not sure what to make of it. Maybe I should start from the right hand side and use the fact that $M(t) = E[e^{tX_j}]=E[1+tX_j+t^2X^2/2!+t^3X_j^3/3!+...]$?

share|cite|improve this question
up vote 2 down vote accepted

$P\{X_1+...+X_n\geq n\epsilon\} \le \prod_{j=1}^n P\{X_j \geq\epsilon\}$ since there are also other ways that the sum can be greater than or equal to $n\epsilon$. So now you want to show that $P\{X_j\ge\epsilon\}\le M(t)e^{-t\epsilon}$.

This is actually known as exponential Chebyshev inequality. To derive this, note by the same reasoning that $P\{X\ge\epsilon\}\le P\{|X|\ge\epsilon\}$ (I'm not sure whether this simplification is really necessary). Then we need a general version of the Chebyshev inequality thanks to @sos440 (see her/his comment below), which is also (up to absolute value) equivalent to its general measure-theoretic statement given on Wikipedia. The simplification step seems to be necessary if using @sos440's derivation, but not if one uses the general measure-theoretic statement from Wikipedia which does not require the absolute value.

The existence of a finite bound $K$ actually guarantees that $X$ has finite moments of each order, so that $E[e^{tX}]$ is finite.

Note, however, that Chebyshev's inequality -- and Bernstein's inequalities, for that matter -- are derived from the more basic Markov's inequality, $P\{|X|>a\}\le\frac{E[|X|]}{a}$. In particular, the latter uses $E[e^{t\sum X_j}]$ in its derivation, so your original thought of using $E[e^{tX_j}]$ might also bear fruit by applying Markov's inequality if you wanted to try your hand at a custom derivation.

share|cite|improve this answer
Then the rest follows simply by Chebyshev's inequality... – Sangchul Lee Apr 3 '12 at 6:39
@sos440: Maybe I'm just being dumb, but how does that follow from Chebyshev's inequality? – bgins Apr 3 '12 at 7:21
The Chebyshev inequality that I know (which is from the celebrated textbook A Course in Probability Theory by Kai Lai Chung) is that, if $\varphi : [0, \infty) \to (0,\infty)$ is increasing and $u >0$, we have $$ \mathbb{P} (|X| \geq u) \leq \frac{\mathbb{E}(\varphi(|X|))}{\varphi(u)}.$$ Now if $t \geq 0$, then the choice $\varphi(x)=x$ gives $$ \mathbb{P} (X \geq \epsilon) = \mathbb{P} (e^{tX} \geq e^{t\epsilon}) \leq \frac{\mathbb{E}(e^{tX})}{e^{t\epsilon}}.$$ – Sangchul Lee Apr 3 '12 at 8:19

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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