5
$\begingroup$

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?

$\endgroup$

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

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