Suppose that $X_1, X_2, ... $ are i.i.d copies of some real random variable $X_1$ which has finite exponential moment and positive expectation. I am asked to show that there exists some $k > 0$ such that $$\mathbb{P}(X_1 + ... + X_n \leq kn) \leq e^{-kn}$$ for all $n$.

My first attempt was to apply the Chernoff bound, but that seems to give me a bound of $\inf_{t>0} e^{tkn} (\mathbb{E}e^{-tX_1})^n$, and I don't see where to proceed from here.


1 Answer 1


Let $t>0$ be such that $Ee^{-tX_1} <1$ .

$$P(X_1+X_2+...+X_n \leq kn)$$ $$=P(e^{-(tX_1+tX_2+...+tX_n)}\geq e^{-ktn})\leq e^{tkn}Ee^{-(tX_1+tX_2+...+tX_n)}$$ $$=e^{tkn} (Ee^{-tX_1})^{n}\leq e^{-kn}$$ if $$k <-\frac 1 {1+t} \ln Ee^{-tX_1}.$$

Existence of $t$: Let $f(t)=Ee^{-tX_1}$ for $t >0$. Since $X_1$ has finite exponential moments we can justify the following: $f'(0+)=E(-X_1) <0$. This implies that $f(t) <1$ for sufficiently small values of $t>0$

  • $\begingroup$ Thank you, this answer is instructive for me also. I don't understand what the reasoning is behind setting the variational parameter $t$ to be arbitrarily large, so that $\mathbb{E}[e^{-tX_i}] < 1$. Please may you clarify? $\endgroup$
    – microhaus
    May 10, 2021 at 23:56
  • $\begingroup$ @microhaus We want $k$ to be positive. So we need $\ln E^{-tX_1} <0$ or $E^{-tX_1} <1$ $\endgroup$ May 10, 2021 at 23:59
  • $\begingroup$ @microhaus I have edited my answer. $\endgroup$ May 11, 2021 at 5:41

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .