You are currently browsing the tag archive for the ‘Bennett's inequality’ tag.

If , a Poisson random variable with mean is a random variable taking values in the natural numbers with probability distribution

One is often interested in bounding upper tail probabilities for , or lower tail probabilities for . A standard tool for this is Bennett’s inequality:

Proposition 1 (Bennett’s inequality)One has for and for , where

From the Taylor expansion for we conclude Gaussian type tail bounds in the regime (and in particular when (in the spirit of the Chernoff, Bernstein, and Hoeffding inequalities). but in the regime where is large and positive one obtains a slight gain over these other classical bounds (of type, rather than ).

*Proof:* We use the exponential moment method. For any , we have from Markov’s inequality that

Remark 2Bennett’s inequality also applies for (suitably normalized) sums of bounded independent random variables. In some cases there are direct comparison inequalities available to relate those variables to the Poisson case. For instance, suppose is the sum of independent Boolean variables of total mean and with for some . Then for any natural number , we have As such, for small, one can efficiently control the tail probabilities of in terms of the tail probability of a Poisson random variable of mean close to ; this is of course very closely related to the well known fact that the Poisson distribution emerges as the limit of sums of many independent boolean variables, each of which is non-zero with small probability. See this paper of Bentkus and this paper of Pinelis for some further useful (and less obvious) comparison inequalities of this type.

In this note I wanted to record the observation that one can improve the Bennett bound by a small polynomial factor once one leaves the Gaussian regime , in particular gaining a factor of when . This observation is not difficult and is implicitly in the literature (one can extract it for instance from the much more general results of this paper of Talagrand, and the basic idea already appears in this paper of Glynn), but I was not able to find a clean version of this statement in the literature, so I am placing it here on my blog. (But if a reader knows of a reference that basically contains the bound below, I would be happy to know of it.)

Proposition 3 (Improved Bennett’s inequality)One has for and for .

*Proof:* We begin with the first inequality. We may assume that , since otherwise the claim follows from the usual Bennett inequality. We expand out the left-hand side as

Now we turn to the second inequality. As before we may assume that . We first dispose of a degenerate case in which . Here the left-hand side is just

and the right-hand side is comparable to Since is negative and , we see that the right-hand side is , and the estimate holds in this case.It remains to consider the regime where and . The left-hand side expands as

The sum is dominated by the first term times a geometric series . The maximal is comparable to , so we can bound the left-hand side by Using the Stirling approximation as before we can bound this by which simplifies to after a routine calculation.The same analysis can be reversed to show that the bounds given above are basically sharp up to constants, at least when (and ) are large.

## Recent Comments