Sharpness of Moment bounds, exponential example
Just for fun, let’s compare the tail bounds you get from the moment method with the explicit tail bound of the exponential distribution.
First, we need the moments: if 
then 
for 
You can compute these using induction and integration by parts. By Markov’s inequality and Stirling’s approximation,
![\displaystyle
\begin{aligned}
\mathbb{P}(X \geq t) & = \mathbb{P}(X^n \geq t^n) \leq \frac{\mathbb{E}X^n}{t^n} = \frac{n!}{(\alpha t)^n} \\ &< \sqrt{2\pi n} \left(\frac{n}{\alpha t e}\right)^n = e^{[\log(2\pi) + \log(n)]/2 + n\log(n) - n\log(\alpha t e)}
\end{aligned}](/cz/latexrender/pictures/62b79c457eeba1b488e314fef2ffa638.png "\displaystyle
\begin{aligned}
\mathbb{P}(X \geq t) & = \mathbb{P}(X^n \geq t^n) \leq \frac{\mathbb{E}X^n}{t^n} = \frac{n!}{(\alpha t)^n} \\ &< \sqrt{2\pi n} \left(\frac{n}{\alpha t e}\right)^n = e^{[\log(2\pi) + \log(n)]/2 + n\log(n) - n\log(\alpha t e)}
\end{aligned}")
for 
sufficiently large.
The derivative of the final quantity is
![\displaystyle
\left(\frac{1}{2n} + \log(n) - \log(\alpha t) \right) e^{[\log(2\pi) + \log(n)]/2 + n\log(n) - n\log(\alpha t e)};](/cz/latexrender/pictures/6e3dd90cefdfc2dc014577bdc73c0159.png "\displaystyle
\left(\frac{1}{2n} + \log(n) - \log(\alpha t) \right) e^{[\log(2\pi) + \log(n)]/2 + n\log(n) - n\log(\alpha t e)};")
if we consider only 
the quantity in the parentheses is monotonic:
It follows that if 
is sufficiently large that the quantity in the parentheses is negative for some 
, then we can optimize the approximate tail bound by setting to be the root of the quantity in the parentheses.
If 
, then the root is given by the Lambert W function:
Putting it all together, the moment method gives the following tail bound for a random variable 
:
How does this compare to the actual bound 
? Just eyeballing it, it looks like asymptotically, the moment bound gives you an exponential tail bound with a worse constant. If true, that’s pretty amazing!
Semilogy plot of the analytic and moment method tail bounds for an Exp(1/2) random variable
Hmmm. On second thought, this is only amazing because I forgot I already worked this out in a more general setting.
Possibly relevant posts:
- Explicit Moment, Tail bound connection (3/12/2010)
- Moment generating function? (6/3/2010)
- Quick and easy route to concentration inequalities for order statistics (8/13/2009)