Suppose $X_1, X_2,\dots, X_n$ are iid random variable,$P(X_i=-\infty)$ is allowed,$P(X_i>v)< e^{-v}\forall v>0$, $X$ is distributed as $X_i$, if $c$ is a finite real number such that $E(X)<c$, then show that there is $A>0, r<1$ such that $P(X_1+\dots+X_n>nc)< Ar^n\forall n$. Can apply Chernoff or Hoefding bound here, to apply do I need to know what distribution $X_i$ is following? I am a bit confused. what is the role of $X$ here? Thanks for helping.

  • $\begingroup$ you seem to really mean $P(X_i=-\infty)>0$ , then the prob you want is bounded by the probability that you haven't seen -infinity yet, which is of the right form. . But then of course E(X) = $-\inf$. $\endgroup$
    – mike
    Sep 25, 2019 at 15:15

1 Answer 1


By the Markov--Bernstein inequality (incorrectly referred to as Chernoff's) \begin{equation} P(X_1+\dots+X_n\ge nc)\le e^{-tnc}Ee^{t(X_1+\dots+X_n)} =e^{-tnc}(Ee^{tX})^n=e^{ng(t)} \end{equation} for real $t\ge0$, where \begin{equation} g(t):=-tc+\ln Ee^{tX}. \end{equation} The condition $P(X_i>v)< e^{-v}\ \forall v>0$ implies $Ee^{tX}<\infty$ and hence $\frac d{dt}\,Ee^{tX}=EXe^{tX}\in\mathbb R$ for real $t<1$. So, $g(0)=0$ and $g'(0)=-c+EX<0$, whence $g(s)<0$ for some real $s>0$. We conclude that \begin{equation} P(X_1+\dots+X_n\ge nc)\le r^n, \end{equation} where $r:=e^{g(s)}\in(0,1)$, as was desired.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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