Suppose $P(X x) le 100 (e^{-ax}+e^{-bx})$. Is there a clever way to bound $mathbb E[X]$?

Question

Let $X$ be a nonnegative random variable. We always have $mathbb E[X] le int_0^infty P(X>x)dx$.
Suppose we also know $P(X>x)le 100e^{-ax}$. We can integrate naively to see $mathbb E[X] le frac{100}{a}$. We can also be more clever by observing $P(X > x) le 1$ for all $x$. This gives the bound
$$mathbb E[X] le int_0^infty  P(X>x)dx le int_0^infty  min{1, 100e^{-ax}} dx $$ $$ le int_0^{log(100)/a}  1 dx +  int_{log(100)/a}^infty  100e^{-ax} dx$$ $$  =frac{log 100}{a}+ frac{100}{a}e^{-ax} biggvert_{x=log(100)/a}=frac{1+log 100}{a}$$
which is much better if $a$ is small.
Now suppose instead we know $P(X > x) le 100 (e^{-ax}+e^{-bx})$ for some $a,b>0$. We can of course estimate by $P(X > x) le 200 e^{-min{a,b}x}$ and do the same as above to get $mathbb E[X] le frac{1+log(100)}{min{a,b}}$.
I wonder is there any way to be more clever than this? There is a temptation to use convexity/concavity to bound $e^{-ax}+e^{-bx}$ by something involving averages. But to my knowledge the convexity/concavity inequalities go the wrong way. Does anyone have an idea?

Varun Vejalla · Answer

You can use a very similar approach to what you have already done for $100e^{-ax}$. You have that $$mathbb{E}[X] = int_0^{infty}P(X>x) dx le int_0^{infty} minleft(1,100left(e^{-ax}+e^{-bx}right)right)$$
Let the solution of $100 left( e^{-ax}+e^{-bx} right) = 1$ be denoted as $t$. This means that $$int_0^{infty} minleft(1,100left(e^{-ax}+e^{-bx}right)right) = int_{0}^{t}1dx+int_{t}^{infty}100left(e^{-ax}+e^{-bx}right)dx$$
This integral evaluates to $$t + 100left(frac{e^{-at}}{a}+frac{e^{-bt}}{b}right)$$
Provided you know nothing more about the distribution of $X$, this is the tightest bound you could get.
Because the exponential blows up less than $t$, it is better to have an overestimate of $t$ rather than an underestimate (provided they are off by the same amount). For one approximation, we can use the solution to $2cdot 100e^{-min(a, b)x} = 1$. This would be $tapprox t_0=frac{lnleft(200right)}{minleft(a,bright)}$. To improve the estimate, you can use the Newton-Raphson method (or any number of root-finding methods).
Specifically, given an estimate $t_n$, a better estimate for $t$ would be $$t_{n+1} = t_{n}+frac{100left(e^{-at_{n}}+e^{-bt_{n}}right)-1}{100left(ae^{-at_{n}}+be^{-bt_{n}}right)}$$

Suppose $P(X > x) le 100 (e^{-ax}+e^{-bx})$. Is there a clever way to bound $mathbb E[X]$?

One Answer

Add your own answers!

Ask a Question