# probability question

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!+...]$?

-

$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.
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}}.$$ –  sos440 Apr 3 '12 at 8:19