# Right tail from exponential-generating function — better than exponential Chebyshev?

For any random variable $X$, and any real number $\theta \geq 0$, you have the inequality $$P(X \geq x) \leq E[e^{\theta X}]/e^{\theta x} = e^{-\theta x} M(\theta)$$

Here $M(\theta)$ is the exponential-generating function for $X$.

Consequently you have Chebyshev's exponential inequality $$P(X \geq x) \leq \inf_\theta e^{-\theta x} M(\theta)$$

How tight is this formula? While it gives the right asymptotic bounds on $P(X \geq x)$, what if one wants more exact (non-asymptotic) information? Are there any other functions of $M$ that give tighter bounds on $P(X \geq x)$?

-

One such alternative bound is the moment bound:

$$P(X \geq x) \leq \inf_{n} \frac{E[X_*^n]}{x^n},$$ where $X_*=\max\{X,0\}$. This is in general tighter than the exponential inequality (see T. Phillips and R. Nelson's The Moment Bound Is Tighter Than Chernoff's Bound for Positive Tail Probabilities (The American Statistician, 1995, 175-178); in Problem 5.1 of Motvani/Raghavan's Randomized Algorithms textbook a similar observation for two-sided tail bounds is credited to J. Naor without a reference given), though it can be more difficult to compute (e.g. if $X$ is the sum of a number of independent variables $E[e^{\theta X}]$ factors nicely, but $E[X^n]$ does not).

-

From saddlepoint approximations you can get the approximation $$P(X\ge x)\approx G_N(r_x)$$ where $G_N$ is the upper tail probability of the standard normal distribution and $$r_x^2=D_x=2\cdot[x\theta_x-m(\theta_x)]$$ for $m(s)=\ln M(s)$ and $\theta_x$ the solution to $m'(\theta_x)=x$ (and the sign of $r_x$ determined by the $x$ being above or below the mean). The $D_x$ denotes the deviance, and the $r_x$ are (depending on context) sometimes referred to as deviance or likelihood residuals.

An alternative formulation of the same result for the case when $r_x\gg0$ (positive and not too close to zero) is $$P(X\ge x) \approx \frac{1}{\sqrt{2\pi D_x}}e^{-D_x/2} =\frac{1}{\sqrt{2\pi}\cdot r_x}e^{m(\theta_x)-x\theta_x}.$$

Note that this is an approximation, not a strict inequality as is Chebyshev's. The result can also be expected to behave better on continuous distributions than discrete, although it may work well on discrete distributions up to the neccessary errors due to the cumulative distribution having jumps which the approximation cannot capture.

In fact, the approximation produced by the reconstruction is log-concave (or close to being log-concave, not sure I remember correctly), so you can imagine that the actual distrubution is being approximated by a continuous log-concave distribution, and then the tail probability of this is estimated.

However, if the distribution is log-concave (continuous or discrete), I've seen this approximation work remarkably well, particularly at the extreme tails: not so quite so good very close to the centre.

Oh, a quick warning. My memory is a bit rusty, and I haven't had this morning's first cup of coffee yet, so I may have snuck in a typo here and there.

Here's one classic reference to this method: Barndorff-Nielsen, O., & Cox, D. (1979). Edgeworth and saddle-point approximations with statistical applications. Journal of the Royal Statistical Society. Series B (Methodological), 41(3), 279–312. http://www.jstor.org/stable/10.2307/2985061

There's also some (perhaps more readable) in this book if I remember correctly: McCullagh, Peter; Nelder, John (1989). Generalized Linear Models. Chapman & Hall/CRC.

-