Here's a problem I've been struggling with:

Let $X_1, X_2, X_3, \ldots$ be an i.i.d. sequence of random variables with finite moment generating function $M(t)$. Define the sum $S_n = X_1 + \ldots + X_n$. For any $a < \mu = \mathbb{E}X_1$, prove that $$\displaystyle \mathbb{P}(S_n \geq an) \leq e^{-nI(a)},$$ where $I(a) = \sup_{t>0}\{at -\log\ M(t)\} > 0$.

What I've been able to hash out so far:

  • I should be able to simplify $\log\ M(t)$ to something like $\mu t$; this will make it possible to express the right-hand side as some common distribution
  • $\displaystyle \frac{S_n}{n}$ converges in distribution to $\mathbb{E}X$, so the right-hand side should be expressible as something nice, like $\mathbb{P}(\mu n - an \geq 0)$ (not exactly that, but something simple).

I'm having trouble finding a way to rigorously express these intuitions about the problem. In any case, thanks for any and all help.


Hint For any $t \geq 0$, we have by Markov's (exponential) inquality and the independence of the random variables,

$$\begin{align*} \mathbb{P}(S_n \geq a \cdot n) = \mathbb{P}(e^{t \cdot S_n} \geq e^{t \cdot a \cdot n})\leq e^{-a \cdot n \cdot t} \cdot \mathbb{E}e^{t \cdot S_n} = e^{-a \cdot n \cdot t} \cdot \prod_{j=1}^n \mathbb{E}(e^{t \cdot X_j}) \end{align*}$$

Now use that the random variables are identically distributed to obtain the estimate you are aiming for.

(As far as I can see, there is a typo in your question: Instead of $a<\mu$ it should read $a>\mu$; otherwise we cannot expect $I(a)>0$.)

By the way, this estimate is known as Chernoff bound. It leads to the topic of large deviations.

| cite | improve this answer | |
  • $\begingroup$ Your edit was correct, thank you for fixing that. $\endgroup$ – tlonuqbar Oct 31 '13 at 1:12

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.