LARGE DEVIATION INEQUALITIES

FOR SUMS OF INDICATOR VARIABLES

Svante Janson

This draft, dated October 1994, will not be published, at least not in its present form. It lacks references to G. Bennett, Probability inequalities for the sum of independent random variables, J. Amer. Statist. Assoc. 57 (1962), 33–45, and W. Hoeffding, Probability inequalities for sums of bounded random variables, J. Amer. Statist. Assoc. 58 (1963), 13–30, where some of the results below can be found.

Abstract. Some new Chernoff type bounds are given for the tail probabilities P(X −EX ≥

a) and P(X −EX ≤ a) when X is a random variable that can be written as a sum of indicator variables that are either independent or negatively related. Several previously known bounds are included and some comparisons are made.

1. Introduction and conclusions

The purpose of this paper is to present some simple upper bounds for the probabilities P(X −EX ≤ −a) and P(X −EX ≥ a), where X is a random variable that can be written as a sum I_{1} + ⋯ + I_{n} of 0–1 (indicator) random variables. We consider both independent and dependent variables I_{i} (with strong restrictions in the dependent case).

Independent summands. The simplest case is when the indicator variables I_{i} are independent and identically distributed, I_{i} ∼ Be(p), with 0 < p < 1 (avoiding trivial cases); then X has the binomial distribution Bi(n, p). This case has been studied by many authors, giving bounds or asymptotic results (sometimes in greater generality); see for example Khintchine (1929), Cramér (1938), Feller (1943), Chernoff (1952), Bahadur and Rao (1960), Littlewood (1969), and the further references given in these papers.

We are here interested in explicit bounds for finite n rather than asymptotic results. One simple but powerful such bound was given by Chernoff (1952); since for every t ≥ 0,

P(X ≥ E X + a) ≤ e^{−t(E X+a)} E e^{tX}  (1.1)

and Ee^{tX} = (1 + p(e^{t} − 1))^{n}, we obtain by simple calculus, letting λ = E X and assuming 0 ≤ a ≤ n − λ,

P(X ≥ E X + a) ≤ inf_{t≥0} exp(−at − npt + n ln(1 + p(e^{t} − 1)))
= exp(−(λ + a) ln \frac{λ + a}{λ} − (n − λ − a) ln \frac{n − λ − a}{n − λ}). (1.2)

Typeset by AMS-TEX

Supported by the Göran Gustafsson Foundation for Research in Natural Sciences and Medicine

Similarly, for 0 ≤ a ≤ λ,

P(X ≤ E X − a) ≤ inf_{t≥0} exp(−at + npt + n ln(1 + p(e^{−t} − 1)))
= exp(−(λ − a) ln \frac{λ − a}{λ} − (n − λ + a) ln \frac{n − λ + a}{n − λ}). (1.3)

Chernoff (1952) proved also that the estimates (1.2) and (1.3) are asymptotically sharp in the sense that if n → ∞ with a/n and p fixed, then equality holds within factors 1 + o(1) in the exponent.

Simpler but (slightly) cruder bounds are easily obtained by finding suitable upper bounds for the right hand sides of (1.2) and (1.3), see for example Alon and Spencer (1992), Appendix A. We state here some, more or less well-known, such bounds. Proofs are given in Section 2.

Theorem 1. Suppose that X ∼ Bi(n, p) and let q = 1 − p. Then, for every a ≥ 0,

P(X ≥ E X + a) ≤ exp(−\frac{a^{2}}{2(npq + a(q − p)/3)}) ≤ exp(−\frac{a^{2}}{2(npq + a/3)})
≤ exp(−\frac{a^{2}}{2npq} (1 − \frac{a}{3npq} )),  (1.4)
P(X ≥ E X + a) ≤ exp(−np((1 + \frac{a}{np}) ln(1 + \frac{a}{np}) − \frac{a}{np})),  (1.5)
P(X ≥ E X + a) ≤ exp(−\frac{a^{2}}{2np(1 + a/3np)}) ≤ exp(−\frac{a^{2}}{2np}(1 − \frac{a}{3np})),  (1.6)
P(X ≤ E X − a) ≤ exp(−\frac{a^{2}}{2(npq − a(q − p)/3)}) ≤ exp(−\frac{a^{2}}{2(npq + a/3)})
≤ exp(−\frac{a^{2}}{2npq} (1 − \frac{a}{3npq} )),  (1.7)
P(X ≤ E X − a) ≤ exp(−np((1 − \frac{a}{np}) ln(1 − \frac{a}{np}) + \frac{a}{np})),  (1.8)
P(X ≤ E X − a) ≤ exp(−\frac{a^{2}}{2np}).  (1.9)

Moreover, if 0 ≤ p ≤ 1/2, then

P(X ≤ E X − a) ≤ exp(−\frac{a^{2}}{2npq} ).  (1.10)

Remark 1. The estimates (1.4) and (1.7) (as well as (1.2) and (1.3)) are obvious “mirror images” of each other, and are equivalent by the substitution X → n − X. On the other hand, the remaining estimates in Theorem 1 are asymmetric, and are useful mainly when p is small.

Remark 2. Note that (1.5), (1.6), (1.8) and (1.9) use n and p only in the combination np = λ = E X.

Remark 3. It may also be observed that if we replace np by λ, then (1.5), (1.6), (1.8) and (1.9) are (e.g. by continuity) valid also when X ∼ Po(λ); in fact, (1.5) and (1.8) then become the Chernoff bounds for the Poisson distribution. These Chernoff bounds too are asymptotically sharp in the sense, considering for example (1.5), that if c > 0 is fixed and c_{1} > (1 + c) ln(1 + c) − c, then P(X ≥ E X + cλ) > exp(−c_{1}λ) for X ∼ Po(λ) with λ large, and thus also for some X ∼ Bi(n, p) with np large and p small. In particular this implies that the simple bound (1.9) is not valid for P(X ≥ E X + a). This implies further, by considering n − X, that (1.10) cannot hold without some restriction on p.

The Chernoff bounds given above for the binomial distribution are easily extended to the case when the 0–1 variables I_{i} are independent with different distributions, I_{i} ∼ Be(p_{i}). In fact, as is well-known (see for example Alon and Spencer (1992), Appendix A), if λ = E X = ∑_{1}^{n} p_{i}, p = λ/n (the average of p_{1}, …, p_{n}), and we let X_{0} ∼ Bi(n, p) be a binomially distributed random variable with the same n and expectation as X, then by Jensen’s inequality for the convex function − ln(1 + x(e^{t} − 1)),

E e^{tX} = ∏_{1}^{n}(1 + p_{i}(e^{t} − 1)) ≤ (1 + p(e^{t} − 1))^{n} = E e^{tX_{0}},  −∞ < t < ∞. (1.11)

Consequently,

P(X ≥ E X + a) ≤ e^{−ta−t E X} E e^{tX} ≤ e^{−ta−t E X_{0}} E e^{tX_{0}},  (1.12)

and thus every Chernoff type bound for the binomial variable X_{0} derived from (1.1), applies also to X.

Theorem 2. The bounds (1.2)–(1.10) hold also when X = ∑_{1}^{n} I_{i} where I_{i} ∼ Be(p_{i}) are independent indicator variables and p = E X/n, q = 1 − p. □

Remark 4. We do not claim that the actual tail probability P(X_{0} ≥ E X + a) is larger than P(X ≥ E X + a), and indeed this is in general false as is shown by the example n = 2, p_{1} = 1/5, p_{2} = 3/5, where P(X ≥ 1) = 17/25 while X_{0} ∼ Bi(2, 2/5) and P(X_{0} ≥ 1) = 16/25.

As mentioned above, the bounds (1.2) and (1.3) are asymptotically sharp for the binomial distribution, but that is no longer generally true when the 0–1 variables have different distributions. In fact, a Taylor expansion shows that the exponent in (1.2) or (1.3) is −\frac{a^{2}}{2np(1−p)}(1+o(1)) provided a = o(np(1−p)), cf. (1.4) and (1.7). In the binomial

case, this equals −\frac{a^{2}}{2σ^{2}} (1 + o(1)), with σ^{2} = Var X, which is what one would expect from normal approximation heuristics; in general, however, σ^{2} = Var X may be much smaller than np(1 − p), and it would be advantageous to have better bounds with exponents −\frac{a^{2}}{2σ^{2}} (1 + o(1)) for moderately large a. One of the principal results of this paper is the following theorem, giving such bounds depending on a and σ^{2} only, with an exponent of the expected order for a = o(σ^{2}). We prove this result in Section 3 using (1.1) as above, but doing a more careful estimation of E e^{tX} than (1.11).

Theorem 3. Let X be a random variable and suppose that there exist independent 0–1 variables I_{i} ∼ Be(p_{i}), i = 1, …, n, such that X =^{d} ∑_{1}^{n} I_{i}. Let λ = E X and σ^{2} = Var X. Then

(i) If a ≥ 0, then
P(X ≥ E X + a) ≤ exp(−σ^{2}((1 + \frac{a}{σ^{2}} ) ln(1 + \frac{a}{σ^{2}} ) − \frac{a}{σ^{2}} ))  (1.13)

(ii) If a ≥ 0, then

P(X ≥ E X + a) ≤ exp(−\frac{a^{2}}{2σ^{2}} /(1 + \frac{a}{3σ^{2}} )) ≤ exp(−\frac{a^{2}}{2σ^{2}} (1 − \frac{a}{3σ^{2}} )).  (1.14)

(iii) If a ≥ cσ^{2}, with c > 0, then

P(X ≥ E X + a) ≤ exp(−((1 + c^{−1}) ln(1 + c) − 1)a).  (1.15)

The same estimates hold for P(X ≤ E X −a), and thus P(|X −E X| ≥ a) may be estimated by twice the right hand sides in (1.13)–(1.15).

(iv) Moreover, if a ≥ 0 and σ^{2} ≥ λ/2, then

P(X ≤ E X − a) ≤ exp(−\frac{a^{2}}{2σ^{2}} ).  (1.16)

Remark 5. The estimates (1.13) and (1.14) are very similar to (1.5) and (1.6); the only difference is that np = λ is replaced by σ^{2} < λ. It is easily seen that this always improves the bound in (1.5) and the first bound in (1.6). On the other hand, the bounds for P(X ≤ E X − a) (except (1.16)) are somewhat different from the corresponding bounds in Theorem 1, because of the symmetry of the bounds in Theorem 3.

Remark 6. It is easily seen (by approximating a Poisson distribution) that the constant in (iii) is best possible. In particular, it follows that (1.16) cannot hold without restriction.

Much more precise estimates of the tail probabilities for sums of independent, but not necessarily identically distributed, random variables were obtained by Feller (1943) using different methods (conjugated distributions as in Cramér (1938) together with a Berry– Esseen estimate), and it is interesting to compare our result with Feller’s. Feller’s result (for our case, using λ_{n} = 1/σ in Feller (1943)) is, for 0 < a < σ^{2}/12,

P(X ≥ E X + a) = e^{− \frac{x^{2}}{2} Q(x)}(1 − Φ(x) + \frac{θ(x)}{σ}e^{−x^{2}/2}),  (1.17)

where x = a/σ, |θ(x)| < 9, Φ is the normal distribution function and

Q(x) = ∑_{ν=1}^{∞} q_{ν}x^{ν},  (1.18)

where q_{ν} depends on the first ν + 2 moments of X and

|q_{ν}| < \frac{1}{7}(\frac{12}{σ})^{ν}.  (1.19)

If, say, σ ≤ a ≤ σ^{2}/24, this yields, using 1 − Φ(x) ≤ (2π)^{−1/2}x^{−1}e^{−x^{2}/2} for x > 0,

P(X ≥ E X + a) < exp(−\frac{x^{2}}{2} (1 + Q(x))) = exp(−\frac{a^{2}}{2σ^{2}} (1 + Q(\frac{a}{σ} )))
< exp(−\frac{a^{2}}{2σ^{2}} (1 − \frac{24}{7} \frac{a}{σ^{2}} )).  (1.20)

For P(X ≤ E X − a) we have the same estimates if we replace Q(x) by Q(−x) (and θ(x) by some θ′(x)); this follows by considering n − X.

The bound (1.20) is similar to the ones given in Theorem 3, in particular (1.14). It is somewhat inferior to (1.14) since the constant in the second order term in the exponent is worse, and the range of a is restricted, but for applications they are essentially equivalent.

Note also that Feller’s result has other advantages. First, (1.17) is an equality (although the exact value of θ(x) is unspecified), and it leads also to a lower bound similar to (1.20) and to asymptotic results. In particular, simple asymptotic results follow when a/σ^{2} → 0 and thus Q(x) → 0. Secondly, Feller (1943) describes how the coefficients q_{ν} may be explicitly expressed in terms of the semi-invariants κ_{j} of X (and thus in terms of the moments); for example (the sign seems to be wrong in Feller (1943), (2.18)–(2.19)),

q_{1} = −\frac{κ_{3}}{3σ^{3}} ,  (1.21)
q_{2} = −\frac{κ_{4}}{12σ^{4}} + \frac{1}{4σ^{6}} κ_{3}^{2}.  (1.22)

(Thus, q_{1} = −\frac{1}{3}γ_{1} and q_{2} = −\frac{1}{12}γ_{2} + \frac{1}{4}γ_{1}^{2}, where γ_{1} and γ_{2} are the skewness and excess of X, respectively.) For example, using (1.21) for q_{1} and (1.19) for q_{ν}, ν ≥ 2, we obtain for σ ≤ a ≤ σ^{2}/24, instead of (1.20),

P(X ≥ E X + a) ≤ exp(−\frac{a^{2}}{2σ^{2}} (1 − \frac{288}{7} \frac{a^{2}}{σ^{4}} − \frac{aκ_{3}}{3σ^{4}} )),  (1.23)

which yields an improvement in cases when κ_{3} = E(X−E X)^{3} is known and either negative or not to large positive.

Dependent summands.

Let us now consider the case of dependent 0–1 variables I_{i}. Of course any bounded non-negative integer valued random variable X can be written as a sum of dependent 0–1 variables, so nothing can be said in general. We will here consider only 0–1 variables that are negatively related in the following sense, cf. Barbour, Holst and Janson (1992).

(Note that large deviation bounds for a class of sums of positively related indicators are given in Janson (1990) and Barbour, Holst and Janson (1992), Theorem 2.S. In this case only the lower tail probabilities P(X ≤ E X − a) have nice upper bounds.)

Definition. The indicator random variables (I_{i})_{i=1}^{n} (defined on the same probability space) are negatively related if for each j ≤ n there exist further random variables (J_{ij})_{i=1}^{n}, defined on the same probability space (or an extension of it), such that the distribution of the random vector (J_{ij})_{i=1}^{n} equals the conditional distribution of (I_{i})_{i=1}^{n} given I_{j} = 1, and, moreover, for every i with i ≠ j, J_{ij}^{i} ≤ I_{i}.

Example 1. (Hypergeometric distribution.) Let m, n and N be given positive integers with max(m, n) ≤ N. Given N urns, labelled 1, …, N, and m balls, put the balls at random into m different urns (drawing without replacement), and let X be the total number of balls in urns 1, …, n. Clearly X = ∑_{1}^{n} I_{i}, where I_{i} equals 1 if urn i contains a ball. In this case it is easy to show that the indicators I_{i} are negatively related by explicitly construction J_{i}, as follows. After randomly distributing the balls as above, and recording I_{i}, we ensure that there is a ball in urn j by “cheating”: if urn j is empty we select one of the balls at random and move it to urn j. Let J_{ij} = 1 if urn i now contains a ball. It is clear that (J_{ij}) has the right distribution, and that J_{ij} ≤ I_{i} for i ≠ j.

Example 2. Distribute m balls into n urns, but this time put the balls one by one at random, independently of the other choices of urn (drawing with replacement). Let X be the number of empty urns. Clearly X = ∑_{1}^{n} I_{i}, where I_{i} = 1 if urn i is empty. These indicators are negativlely related; this follow by a construction very similar to the one in Example 1, removing all balls (if any) in urn i and redistributing them (repeating if necessary).

Further examples of negatively related variables are given in Barbour, Holst and Janson (1992), where also some general results are established. In particular, it is proven (a special case of Corollary 2.D.1) that the variables I_{i}, i = 1, …, n, are negatively related if and only if I_{j} and ϕ(I_{1}, …, I_{j−1}, I_{j+1}, …, I_{n}) are negatively correlated for every j and every indicator function ϕ that is increasing in each variable. (Pairwise negative correlation of the I_{i} is not enough.) It follows immediately that the variables (1 − I_{i})_{i=1}^{n} are negatively related if (I_{i})_{i=1}^{n} are. It follows also that variables are negatively related if they are negatively associated in the sense of Joag-Dev and Proschan (1983).

Theorem 4. Suppose that X =^{d} ∑_{1}^{n} I_{i}, where I_{i} ∼ Be(p_{i}) are negatively related indicator variables. Let Ĩ_{i}, i = 1, …, n, be independent indicator variables with Ĩ_{i} ∼ Be(p_{i}), and put X̃ = ∑_{1}^{n} Ĩ_{i}. Then, for every real t,

E e^{tX} ≤ E e^{tX̃}.

Consequently, any Chernoff type bound for X̃ applies also to X. In particular, (1.2)–(1.10) hold with p = E X/n and q = 1 − p; for example, with λ = E X,

P(X ≥ E X + a) ≤ exp(−\frac{a^{2}}{2λ(1 + a/3λ)}) ≤ exp(−\frac{a^{2}}{2λ}(1 − \frac{a}{3λ})),
P(X ≤ E X − a) ≤ exp(−\frac{a^{2}}{2λ}).

Of course, also the bounds in Theorem 3 (applied to X̃) apply to X. The problem is that we have to use σ^{2} = Var(X̃) instead of Var(X), which may be much smaller. In fact, the bounds in Theorem 3 are in general false with σ^{2} = Var X in the dependent case; the following theorem implies that it is impossible to have a general bound that is, say, exp(−a^{2}/3σ^{2}) for some a ≥ 4σ.

Theorem 5. Let α > 0, 0 < c < 1/e and A < ∞. There exists a random variable X which is a finite sum of negatively related indicators such that σ^{2} = Var X > A and, with a = ασ,

P(X > E X + a) > ce^{−a/σ}.  (1.24)

Nevertheless, there are cases where it is possible to do better. A striking example is based on the result by Vatutin and Mikhailov (1982) that certain random variables that occur in some occupancy problems, and have natural representations as sums of negatively related indicators (with the same expectation), also can be represented as sums of independent indicators with different expectations. (The proof is algebraic, and based on showing that the probability generating function has only real roots; there is no (known) probabilistic interpretation of these indicators, which in general have irrational expectations.) Their result includes the variables in Examples 1 and 2 (using in their notation s_{1} = N − n, s_{2} = N − m for Example 1 and s_{1} = ⋯ = s_{m} = 1 for Example 2).

Consequently, the variables in Examples 1 and 2 actually satisfy the hypothesis of Theorem 3 (although we do not know the p_{i} explicitly). Hence we can apply Theorem 3; note that the bounds in Theorem 3 involve only σ^{2} and possibly λ, and not the unknown p_{i}. (In fact, this application was one of the motivations for finding bounds of the form given in Theorem 3.)

Theorem 6. Let X be either hypergeometric as in Example 1, or as in Example 2. Then the conclusions of Theorem 3 hold, with λ = E X and σ^{2} = Var X. □

Example 2, cont. For the occupancy problem described above,

λ = E X = n(1 − \frac{1}{n})^{m},

σ^{2} = Var X = n(1 − \frac{1}{n})^{m} + n(n − 1)(1 − \frac{2}{n})^{m} − n^{2}(1 − \frac{1}{n})^{2m};

estimates of the tail probabilities are obtained by using these values in any of the formulas (1.2)–(1.16), letting p = E X/n and q = 1 − n.

For asymptotical results in the case m/n → r > 0, we easily find

λ = E X ∼ ne^{−r},
σ^{2} = Var X ∼ n(e^{−r} − (1 + r)e^{−2r}) = ne^{−2r}(e^{r} − 1 − r).

The asymptotics for the tail probabilites in this case have been studied in detail by Kamath, Motwani, Palem and Spirakis (1994).

Remark 7. A comparison of Theorems 3 and 5 shows that not every random variable that is a sum of negatively related indicators can be represented as a sum of independent indicators; the Vatutin–Mikhailov result depends on some further structure. The first example of such a variable was found by Andrew Barbour (personal communication): Let P(X = 3) = 4/13, P(X = 4) = 5/13, P(X = 5) = 4/13. Then X = ∑_{1}^{5} I_{i}, with I_{i} indicators and the distribution of (I_{1}, …, I_{5}) uniform given X; and these I_{i} are easily verified to be negatively related. On the other hand, it is easily seen that X is not the sum of any number of independent indicators.

Acknowledgements. This research has been inspired by discussions with Andrew Barbour, Carl-Gustav Esseen, Rajeev Motwani, Joel Spencer, Andrew Thomason, and possibly others.

2. Proof of Theorem 1

The first inequality in (1.4) is trivial for a > nq. For 0 ≤ a ≤ nq, let x = a/n ∈ [0, q]. Then the bound (1.2) may be written

P(X ≥ E X + a) ≤ exp(−np(1 + \frac{x}{p}) ln(1 + \frac{x}{p}) − nq(1 − \frac{x}{q}) ln(1 − \frac{x}{q})).  (2.1)

Let, for 0 ≤ x ≤ q,

f(x) = p(1 + \frac{x}{p}) ln(1 + \frac{x}{p}) + q(1 − \frac{x}{q}) ln(1 − \frac{x}{q}) − \frac{x^{2}}{2(pq + x(q − p)/3)}.

Then f(0) = f′(0) = 0, and an elementary calculation yields

f′′(x) = \frac{1}{x + p} + \frac{1}{q − x} − \frac{p^{2}q^{2}}{(pq + x(q − p)/3)^{3}}

= \frac{\frac{1}{3}pq(q − p)^{2}x^{2} + \frac{1}{27}(q − p)^{3}x^{3} + p^{2}q^{2}x^{2}}{(x + p)(q − x)(pq + x(q − p)/3)^{3}} ≥ 0

for 0 ≤ x ≤ q. Hence f(x) ≥ 0 in this interval, and thus

P(X ≥ E X + a) ≤ exp(−n\frac{x^{2}}{2(pq + x(q − p)/3)}).

This proves the first inequality in (1.4). The second follows from q − p ≤ 1 and the third from

\frac{1}{1 + a/3npq} ≥ 1 − \frac{a}{3npq} .

Inequality (1.5) follows directly from (2.1) and

−nq(1 − \frac{x}{q}) ln(1 − \frac{x}{q}) = n(q − x) ln(1 + \frac{x}{q − x}) ≤ nx.  (2.2)

The inequalities (1.6) follow from (1.4) and

−\frac{1}{npq + a/3} ≤ −\frac{1}{np(1 + a/3np)} ≤ −\frac{1}{np}(1 − \frac{a}{3np});

alternatively, they follow easily from (1.5), cf. (3.10).

The inequalities (1.7) follow from (1.3) by an argument similar to the one given above for (1.4), or (simpler) by applying (1.4) to n−X ∼ Bi(n, q); (1.8) follows from (1.3), using (2.2) with x = −a/n ≤ 0; (1.9) follows from (1.7) and, assuming (as we may) a ≤ np, npq − a(q − p)/3 ≤ npq + ap/3 ≤ npq + np^{2}/3 ≤ np. Finally, also (1.10) follows from (1.7) since we now assume a(q − p)/3 ≥ 0. □

3. Proof of Theorem 3

We may assume that X = ∑_{1}^{n} I_{i} where I_{i} ∼ Be(p_{i}) are independent. Note that

λ = E X = ∑_{1}^{n} p_{i}

σ^{2} = Var X = ∑_{1}^{n} p_{i}(1 − p_{i}) = λ − ∑_{1}^{n} p_{i}^{2}

and thus

∑_{1}^{n} p_{i}^{2} = λ − σ^{2}.

We assume, to avoid trivialities, that at least one p_{i} ≠ 0, 1. Thus 0 < λ < n and 0 < σ^{2} < λ.

We begin with a real analysis lemma. It is an analogue of Jensen’s inequality but with a condition on the sign of the third derivative instead of the second.

Lemma 1. Suppose that μ is a finite positive measure on [0, 1], and define

m = μ([0, 1]),
x_{0} = ∫_{0}^{1} x^{2}dμ/ ∫_{0}^{1} x dμ,

α_{0} = (∫_{0}^{1} x dμ)^{2}/ ∫_{0}^{1} x^{2}dμ,
x_{1} = 1 − ∫_{0}^{1}(1 − x)^{2}dμ/ ∫_{0}^{1}(1 − x)dμ,

α_{1} = (∫_{0}^{1}(1 − x)dμ)^{2}/ ∫_{0}^{1}(1 − x)^{2}dμ.

(We here let 0/0 = 0; this occurs in the degenerate cases where μ is a point mass at 0 or 1.) If f is a three times continuously differentiable real function on [0, 1] with f′′′ ≥ 0, then

(m − α_{0})f(0) + α_{0}f(x_{0}) ≤ ∫_{0}^{1} f dμ ≤ (m − α_{1})f(1) + α_{1}f(x_{1}).  (3.1)

If instead f′′′ ≤ 0 on [0, 1], then these inequalities are reversed.

Proof. We will show the left inequality of (3.1); the right inequality then follows by symmetry, considering the function f̃(x) = −f(1 − x), which satisfies f̃′′′(x) = f′′′(1 − x) ≥ 0, and the similarly reflected measure μ̃(A) = μ({1 − x : x ∈ A}). Similarly, the statement for f′′′ ≤ 0 follows by considering −f.

Let ν be the measure (m − α_{0})δ_{0} + α_{0}δ_{x_{0}}; thus the sought inequality is ∫ f dν ≤ ∫ f dμ, while the choice of α_{0} and x_{0} yields ∫ 1 dν = m = ∫ 1 dμ, ∫ x dν = α_{0}x_{0} = ∫ x dμ, and ∫ x^{2}dμ = α_{0}x_{0}^{2} = ∫ x^{2}dμ. (In fact, it is easily seen that ν is the unique measure concentrated on a two-point set {0, x} for some x ∈ [0, 1], such that ∫ x^{k}dν = ∫ x^{k}dμ for k = 0, 1, 2.)

We now use Taylor’s formula

f(x) = f(0) + f′(0)x + \frac{1}{2}f′′(0)x^{2} + \frac{1}{2} ∫_{0}^{x}(x − t)^{2}f′′′(t) dt  (3.2)

and integrate against the signed measure μ − ν. Since as we just have shown,

∫_{0}^{1} x^{k}d(μ − ν) = 0,  k = 0, 1, 2,  (3.3)

we obtain from (3.2) and Fubini’s theorem,

∫_{0}^{1} f(x) d(μ − ν) = ∫_{0}^{1} ∫_{0}^{x} \frac{1}{2}(x − t)^{2}f′′′(t) dt d(μ − ν)(x)
= ∫_{0}^{1} ∫_{t}^{1} \frac{1}{2}(x − t)^{2}d(μ − ν)(x)f′′′(t) dt
= ∫_{0}^{1} φ(t)f′′′(t)dt,  (3.4)

where

φ(t) = \frac{1}{2} ∫_{t}^{1}(x − t)^{2}d(μ − ν)(x).

We claim that φ(t) ≥ 0 on [0,1]; this implies ∫_{0}^{1} f(x)d(μ − ν) ≥ 0 by (3.4) which is the required result. Note that φ(1) = 0 and φ(0) = \frac{1}{2} ∫_{0}^{1} x^{2}d(μ − ν) = 0. Moreover, again by (3.3), ∫_{0}^{1}(x − t)^{2}d(μ − ν)(x) = 0 and thus

φ(t) = −\frac{1}{2} ∫_{0}^{t}(x − t)^{2}d(μ − ν)(x).

Using Fubini again, and letting F (x) = μ([0, x]) − ν([0, x]),

φ(t) = − ∫∫∫_{0≤x≤y≤z≤t} dy dz d(μ − ν)(x) = − ∫_{0}^{t} ∫_{0}^{z} F (y) dy dz,

and thus φ is continuously differentiable with

φ′(z) = − ∫_{0}^{z} F (y) dy.  (3.5)

In particular φ′(0) = 0 and, using Fubini a last time,

φ′(1) = − ∫_{0}^{1} F (y) dy = − ∫_{0}^{1} ∫_{0}^{y} d(μ − ν)(x) dy = − ∫_{0}^{1}(1 − x) d(μ − ν)(x) = 0.

On the interval [0, x_{0}), ν([0, x]) is constant m − α_{0}, and thus F (x) is increasing; hence there exists x_{2} ∈ [0, x_{0}] such that F (x) ≤ 0 on (0, x_{2}) and F (x) ≥ 0 on (x_{2}, x_{0}). It follows by (3.5) that φ′ is increasing and thus φ is convex on [0, x_{2}], while φ is concave on [x_{2}, x_{0}]. Since φ(0) = φ′(0) = 0, this implies that φ ≥ 0 on [0, x_{2}]. Similarly, on the interval [x_{0}, 1], we have ν([0, x]) = m and thus

F (x) = μ([0, x]) − ν([0, x]) = μ([0, x]) − m ≤ 0,

which implies that φ is convex on [x_{0}, 1]. Moreover, φ(1) = φ′(1) = 0 and thus φ ≥ 0 on [x_{0}, 1]. Finally, on the interval [x_{2}, x_{0}], φ is concave so it attains it minimum at one of the endpoints, but we have already shown φ(x_{2}), φ(x_{0}) ≥ 0 and thus φ ≥ 0 also on [x_{2}, x_{0}], which completes the proof. □

We apply this lemma to estimate the moment generating function of X.

Lemma 2. Let X be as above. If 0 ≤ t ≤ 1, then

E(1 − t)^{X} ≤ (1 − t(1 − \frac{σ^{2}}{λ} ))^{λ^{2}/(λ−σ^{2})}

or

ln E(1 − t)^{X} ≤ \frac{λ^{2}}{λ − σ^{2}} ln(1 − t(1 − \frac{σ^{2}}{λ} )).  (3.6)

Proof. Since the I_{i} are independent, and E(1 − t)^{I_{i}} = 1 − p_{i} + p_{i}(1 − t) = 1 − p_{i}t,

E(1 − t)^{X} = E ∏_{i=1}^{n}(1 − t)^{I_{i}} = ∏_{i=1}^{n} E(1 − t)^{I_{i}} = ∏_{i=1}^{n}(1 − p_{i}t),

and thus

ln E(1 − t)^{X} = ∑_{i=1}^{n} ln(1 − p_{i}t) = ∫_{0}^{1} ln(1 − tx) dμ(x),

where μ is the measure ∑_{1}^{n} δ_{p_{i}} consisting of n point masses at the (possibly coinciding) points p_{i}. Note that

∫_{0}^{1} x dμ = ∑_{i=1}^{n} p_{i} = λ

and

∫_{0}^{1} x^{2}dμ = ∑_{i=1}^{n} p_{i}^{2} = λ − σ^{2}.

We may assume that t < 1 (the case t = 1 follows then by continuity); then the function f(x) = ln(1 − tx) is infinitely differentiable on [0, 1] with f′′′(x) = −2t^{3}/(1 − tx)^{3} ≤ 0. Hence Lemma 1 yields

ln E(1 − t)^{X} = ∫_{0}^{1} ln(1 − tx) dμ(x) ≤ (m − α_{0})f(0) + α_{0}f(x_{0}) = α_{0} ln(1 − tx_{0}),

where m = n, α_{0} = λ^{2}/(λ − σ^{2}) and x_{0} = (λ − σ^{2})/λ, which is the required estimate. □

Remark 8. For t ≥ 0, a similar argument yields

ln E(1 + t)^{X} ≤ (n − α_{1}) ln(1 + t) + α_{1} ln(1 + tx_{1})
= \frac{nλ − λ^{2} − nσ^{2}}{n − λ − σ^{2}} ln(1 + t) + \frac{(n − λ)^{2}}{n − λ − σ^{2}} ln(1 + t\frac{σ^{2}}{n − λ}).  (3.7)

This inequality could be used instead of (3.6) below, giving the same results. We prefer to use (3.6), which does not involve n explicitly.

Remark 9. Estimates of E e^{sX} are, of course, obtained by substituting t = 1−e^{s} in (3.6) for s ≤ 0 and t = e^{s} − 1 in (3.7) for s ≥ 0.

We can now obtain our basic estimate.

Lemma 3. Let X be as above. If 0 ≤ a ≤ λ, then

ln P(X ≤ λ − a) ≤ −\frac{λ}{λ − σ^{2}} (a + σ^{2} − aσ^{2}/λ) ln(1 + \frac{a}{σ^{2}} − \frac{a}{λ}) − (λ − a) ln(1 − \frac{a}{λ}). (3.8)

(When a = λ, we define (λ − a) ln(1 − a/λ) = 0.)

Proof. For any t with 0 ≤ t ≤ 1,

E(1 − t)^{X} ≥ (1 − t)^{λ−a} P(X ≤ λ − a),

and thus, using Lemma 2,

ln P(X ≤ λ − a) ≤ ln E(1 − t)^{X} − (λ − a) ln(1 − t)

≤ \frac{λ^{2}}{λ − σ^{2}} ln(1 − t(1 − \frac{σ^{2}}{λ} )) − (λ − a) ln(1 − t).

Choosing

t = \frac{a}{a + σ^{2} − aσ^{2}/λ}

(which minimizes the right hand side), this yields

ln P(X ≤ λ − a) ≤ \frac{λ^{2}}{λ − σ^{2}} ln \frac{σ^{2}}{a + σ^{2} − aσ^{2}/λ} − (λ − a) ln \frac{σ^{2}(1 − a/λ)}{a + σ^{2} − aσ^{2}/λ}

= (\frac{λ^{2}}{λ − σ^{2}} − λ + a) ln \frac{σ^{2}}{a + σ^{2} − aσ^{2}/λ} − (λ − a) ln(1 − \frac{a}{λ})

= −\frac{λσ^{2} + λa − aσ^{2}}{λ − σ^{2}} ln \frac{σ^{2} + a − aσ^{2}/λ}{σ^{2}} − (λ − a) ln(1 − \frac{a}{λ}),

which yields the sought result. □

While the estimate in Lemma 3 may be useful for numerical evaluation in applications, it is too complicated to be of much other direct use. Hence we will use it to derive the simpler (but slightly weaker) estimates in Theorem 3.

For notational convenience, let σ^{2} = xλ and a = yσ^{2} = xyλ, where 0 < x < 1 and 0 ≤ y ≤ 1/x. Then (3.8) may be written

ln P(X ≤ λ − a) ≤ −σ^{2}g(x, y),  (3.9)

where

g(x, y) = \frac{1}{1 − x}(1 + y − xy) ln(1 + y − xy) + \frac{1}{x}(1 − xy) ln(1 − xy).

Lemma 4. g(x, y) is an increasing function of x in the region

U = {(x, y) : 0 < x < 1, 0 ≤ y ≤ 1/x}.

Proof. We want to show that ∂g/∂x ≥ 0 in the region {(x, y) : 0 < x < 1, 0 ≤ y < 1/x}; note that g is well-defined and infinitely differentiable in the larger region V = {(x, y) : 0 < x < 1, −1/(1 − x) < y < 1/x}, and continuous on V̄ ∩ {(x, y) : 0 < x < 1} ⊃ U.

Instead of estimating ∂g/∂x directly, we first compute

\frac{∂g}{∂y} = ln(1 + y − xy) − ln(1 − xy)

and

\frac{∂^{2}g}{∂x∂y} = \frac{∂^{2}g}{∂y∂x} = \frac{−y}{1 + y − xy} − \frac{−y}{1 − xy} = \frac{y^{2}}{(1 + y − xy)(1 − xy)} ≥ 0.

Hence ∂g/∂x is an increasing function of y. Moreover, taking y = 0, we find g(x, 0) = 0 and thus

\frac{∂g}{∂x}(x, 0) = 0, 0 < x < 1.

Hence \frac{∂g}{∂x}(x, y) ≥ 0 for all (x, y) ∈ V with y ≥ 0. □

Proof of Theorem 3. If x ↘ 0 and y ≥ 0 is fixed, then, as is easily seen,

g(x, y) → (1 + y) ln(1 + y) − y.

Lemma 4 thus yields, for 0 < x < 1 and 0 ≤ y ≤ 1/x,

g(x, y) ≥ (1 + y) ln(1 + y) − y,

and thus by (3.9), for 0 ≤ a ≤ λ,

ln P(X ≤ λ − a) ≤ −σ^{2}((1 + y) ln(1 + y) − y),

with y = a/σ^{2}, which is the analogue of (1.13) for P(X ≤ E X − a); note that this estimate trivially holds for a > λ. In order to obtain (1.13), we consider the variable X^{∗} = n − X =^{d} ∑_{1}^{n}(1 − I_{i}), and observe that P(X ≥ E X + a) = P(X^{∗} ≤ E X^{∗} − a) and Var(X^{∗}) = Var X. The estimates (1.14) and (1.15) and their analogues for P(X ≤ E X−a) now follow from the elementary estimates, defining h(y) = (1 + y) ln(1 + y) − y,

h(y) ≥ \frac{y^{2}}{2(1 + y/3)} ≥ \frac{y^{2}}{2} (1 − y/3),  y ≥ 0,  (3.10)

and

h(y) ≥ yh(c)/c,  y ≥ c.  (3.11)

The estimate (3.10) may be verified by observing that h(y)−y^{2}/2(1+y/3) vanishes together with its first derivative at 0, while the second derivative equals (9y^{2}+y^{3})/(1+y)(3+y)^{3} ≥ 0. Similarly, (3.11) follows by the convexity of h. We omit the details.

Finally, if σ^{2} ≥ λ/2, then x ≥ 1/2 and thus by Lemma 4 (assuming as we may that a ≤ λ),

g(x, y) ≥ g(\frac{1}{2}, y) = (2 + y) ln(1 + \frac{y}{2} ) + (2 − y) ln(1 − \frac{y}{2} ) ≥ \frac{1}{2}y^{2},

which together with (3.9) yields (1.16). □

4. Proof of Theorem 4.

Let Y = ∑_{2}^{n} I_{i} and Z = ∑_{2}^{n} J_{i1}, where (J_{i1})_{i=1}^{n} are as in the definition of negatively related variables. Then X = I_{1} + Y and E(Y | I_{1} = 1) =^{d} Z. Moreover, since J_{i1} ≤ I_{i} for i ≥ 2, we have Z ≤ Y. Consequently, for any real t,

E e^{tX} − E e^{tY} = E(e^{tI_{1}} − 1)e^{tY} = E(e^{t} − 1)I_{1}e^{tY}
= (e^{t} − 1)p_{1} E(e^{tY} | I_{1} = 1)
= (e^{t} − 1)p_{1} E e^{tZ}
≤ (e^{t} − 1)p_{1} E e^{tY}
= E(e^{tI_{1}} − 1) E e^{tY}

and thus

E e^{tX} ≤ E e^{tI_{1}} E e^{tY} .

Induction yields

E e^{tX} ≤ ∏_{1}^{n} e^{tI_{i}} = E e^{tX̃}.  □

5. Proof of Theorem 5.

Given n, p, k, with 1 ≤ k ≤ n and 0 < p < 1, let U ∼ Bi(n, p) and let X_{npk} be the random variable U conditioned on U ≥ k. Since U = ∑_{1}^{n} I_{i}, with I_{i} ∼ Be(p) independent, X_{npk} = ∑_{1}^{n}(I_{i} | ∑_{1}^{n} I_{i} ≥ k), and it follows from Barbour, Holst and Janson (1992) Proposition 2.2.10 and Theorem 2.I that X_{npk} is a sum of negatively related indicators. We claim that, for any α, c, A as in Theorem 5, some variable X_{npk} satisfies (1.24).

Suppose not. Then for each n, p, k either Var(X_{npk}) ≤ A or

P(X_{npk} − E X_{npk} > ασ) ≤ ce^{−α}.  (5.1)

Fix p, let q = 1 − p, choose ε with 0 < ε < q, take k = [n(p + ε)] + 1, and let n → ∞. Then, for i ≥ 0, with r = p(q − ε)/(p + ε)q < 1,

\frac{P(X_{npk} = k + i + 1)}{P(X_{npk} = k + i)} = \frac{p}{q} · \frac{n − k − i}{k + 1} → \frac{p}{q} · \frac{q − ε}{p + ε} = r  as n → ∞,  (5.2)

and

P(X_{npk} = k + i) ≤ r^{i} P(X_{npk} = k) ≤ r^{i}.  (5.3)

It follows that X_{npk} − k converges in distribution to a random variable Y_{r} with geometric distribution Ge(1 − r): P(Y_{r} = i) = (1 − r)r^{i}, i ≥ 0. Moreover, by (5.3), every moment E(X_{npk} − k)^{m} stays bounded, which implies that the moments converge to the corresponding moments of Y_{r}.

The variance of Y_{r} equals r/(1 − r)^{2}. If Var(Y_{r}) > A, then also Var(X_{npk}) > A for large n, so by our assumption (5.1) holds and taking the limit as n → ∞ we obtain

P(Y_{r} − E Y_{r} > α\sqrt{Var Y_{r}}) ≤ ce^{−α}.  (5.4)

Now, let ε → 0 (keeping p fixed). Then r → 1 and Var(Y_{r}) = r/(1 − r)^{2} → ∞, so (5.4) holds when r is close to 1. Moreover, it is easily seen that as r → 1, (1 − r)Y_{r} converges in distribution to an exponential variable Z ∼ Exp(1), again with convergence of all moments. Consequently we may take the limit again and obtain from (5.4)

P(Z − E Z > α\sqrt{Var Z}) ≤ ce^{−α}.  (5.5)

But E Z = Var Z = 1, so the left hand side of (5.5) equals P(Z > 1 + α) = e^{−1−α} > ce^{−α}, and we have obtained a contradiction. □

References

N. Alon and J. H. Spencer (1992), The Probabilistic Method, Wiley, New York. R. Bahadur and R. Ranga Rao (1960), On deviations of the sample mean, Ann. Math. Stat. 31, 1015–1027. A. D. Barbour, L. Holst and S. Janson (1992), Poisson Approximation, Oxford Univ. Press, Oxford. H. Chernoff (1952), A measure of asymptotic efficiency for tests of a hypothesis based on the sum of

observations, Ann. Math. Stat. 23, 493–507. H. Cramér (1938), Sur un nouveau théorème-limite de la théorie des probabilités, Actualités Scientifiques

et Industrielles 736, 5–23. W. Feller (1943), Generalization of a probability limit theorem of Cramér, Trans. Amer. Math. Soc. 54,

361–372. S. Janson (1990), Poisson approximation for large deviations, Random Struct. Alg. 1, 221–230. K. Joag-Dev and F. Proschan (1983), Negative association of random variables, with applications, Ann.

Stat. 11, 286–295. A. Kamath, R. Motwani, K. Palem and P. Spirakis (1994), Tail bounds for occupancy and the satisfiability

threshold conjecture, Proceedings of the 35th Annual IEEE Symposium on Foundations of Computer Science.

A. Khintchine (1929), Über einen neuen Grenzwertsatz der Wahrscheinlichkeitsrechnung, Math. Ann. 101,

745–752. J.E. Littlewood (1969), On the probability in the tail of a binomial distribution, Adv. Appl. Probab. 1,

43–72. V.A. Vatutin and V.G. Mikhailov (1982), Limit theorems for the number of empty cells in an equiprobable

scheme for group allocation of particles, Teor. Veroyatnost. i Primenen. 27, 684–692 (Russian); English transl., Theor. Probab. Appl. 27, 734–743.

Department of Mathematics, Uppsala University, PO Box 480, S-751 06 Uppsala, Sweden

   E-mail address: svante.janson@math.uu.se