# Tail Lower Bounds using Moment Generating Functions

Given a random variable $$X>0$$ with Moment Generating Function $$m(s)=E[e^{sX}]$$ I'm interested in finding a lower bound $$\Pr[X \ge t] \ge 1-\varepsilon(t),$$ where $$t>E[X]$$.

A classic technique for finding upper bounds for $$\Pr[X \ge t]$$ is using Markov's inequality with the Moment Generating Function: $$\Pr[X \ge t] \le E[e^{sX}]e^{-st},$$ for $$s\ge 0$$. Since $$E[e^{s X}]\ge e^{s E[X]}$$ (Jensen's inequality), this bound is useful whenever $$t>E[X]$$. (I'm assuming $$X$$ is a positive random variable, so $$E[X]>0$$.)

Standard techniques for lower bounds include the second-moment method, such as Cantelli's inequality and Paley-Zygmund. However, they only cover the case $$t\in[0,E[X]]$$ and say nothing about the case $$t>E[X]$$.

My best bet so far has been Lévy's and Gil-Pelaez's inversion formulas for the Characteristic Function $$m(i s)$$:

\begin{align}\Pr[X \ge t] &= 1-\frac{1} {2\pi} \lim_{S \to \infty} \int_{-S}^{S} \frac{1 - e^{-ist}} {is}\, m(is)\, ds. \\\text{and}\quad \Pr[X \ge t] &= \frac{1}{2} + \frac{1}{\pi}\int_0^\infty \frac{\operatorname{Im}[e^{-ist}m(i s)]}{s}\,ds.\end{align}

However, I don't have any good ideas for bounding those in a useful way. It certainly seems a lot harder than the Markov method for the upper bound.

Am I missing a useful approach here?

Actually this is not so hard to do with Paley-Zygmund. Not sure why I didn't see this before. We just substitute $$X$$ by $$e^{s X}$$ like in Chernoff's bound:
$$\Pr[e^{sX} > \theta E[e^{sX}]] = \Pr[X > \log(\theta E[e^{sX}])/s] \ge (1-\theta)^2\frac{E[e^{s X}]}{E[e^{2 s X}]}.$$
For an example with the normal distribution, where $$E[e^{s X}]=e^{s^2/2}$$ we get $$\Pr[X > \log(\theta)/s + s/2] \ge (1-\theta)^2 e^{-\tfrac{3}{2}s^2},$$ so taking $$\log(\theta)/s+s/2=t$$ and $$\theta=1/2$$ we get $$\Pr[X > t] \ge \frac{1}{4} e^{-\left(\sqrt{t^2+\log (4)}+t\right)^2} \sim e^{-6t^2}.$$ Indeed, the value of $$\theta$$ matters very little. We can compare this result to the true asymptotics for the normal distribution $$\Pr[X > t] \sim e^{-t^2/2}$$ to see that we lose roughly a factor 12 in the exponent. Alternatively for $$t\to0$$ we get $$\Pr[X>0]\ge1/16$$.
We can improve the lower bound a bit to $$\sim t^{O(1)} e^{-2t^2}$$ using the $$L^p$$ version of Paley-Zygmund, but there's still a gap. This differs from the situation of the upper bound (Markov/Chernoff) which is tight in the exponent. If there's a way to get a tight exponent using moment generating functions, I'm still very interested.