ON CONCENTRATION OF PROBABILITY

SVANTE JANSON

Abstract. We give a survey of several methods to obtain sharp concentration results, typically with exponentially small error probabilities, for random variables occuring in combinatorial probability.

Introduction

In probabilistic combinatorics, it is often important to show that a random variable is sharply concentrated about its mean. A well-known, simple, but rather weak result of this type is Chebyshev’s inequality

ℙ(|X − 𝔼 X| ≥ t) ≤ Var(X)/t^{2},

which holds for any random variable X with finite variance and any t > 0. This inequality is very general (and very useful), but is in many cases too weak. The purpose of this paper is to give a survey of some more or less recent stronger inequalities, which under suitable assumptions yield estimates that decrease exponentially as t → ∞.

1. Sums of independent variables

An important case is when the variable X can be written as a sum ∑_{1}^{n} X_{i} of independent random variables. We consider here only the case when each X_{i} is an indicator variable; thus X_{i} ∈ Be(p_{i}) where p_{i} = ℙ(X_{i} = 1) = 𝔼 X_{i}. (The results hold more generally, assuming only that 0 ≤ X_{i} ≤ 1.) Let λ = 𝔼 X = ∑_{1}^{n} p_{i}.

Consider first the case of a binomially distributed variable X ∈ Bi(n, p); this is of the type above with all p_{i} = p, and thus λ = np. Applying Markov’s inequality to e^{uX}, one finds

ℙ(X ≥ λ + t) ≤ e^{−u(λ+t)} 𝔼 e^{uX} = e^{−u(λ+t)}(1 − p + pe^{u})^{n},  u ≥ 0. (1)

The right hand side attains its minimum at e^{u} = (λ + t)(1 − p)/(n − λ − t)p, assuming 0 < λ + t < n, which yields

ℙ(X ≥ 𝔼 X + t) ≤ (\frac{λ}{λ + t})^{λ+t}(\frac{n − λ}{n − λ − t})^{n−λ−t},  0 ≤ t ≤ n − λ; (2)

for t > n − λ the probability is 0. This bound is implicit in Chernoff [8] and appears explicitly in Okamoto [19]. For applications, it is usually convenient to replace the right hand side of (2) by a larger but simpler bound. Our favourites are the following, which follow from (2) by some calculus.

Date: November 5, 1998; revised August 15, 2000; typo corrected May 25, 2010.

Key words and phrases. Concentration of probability, Azuma’s inequality, Chernoff bound, Janson’s inequality, Suen’s inequality, Talagrand’s inequality.

This paper is based on lectures at the workshop “Probabilistic combinatorics” at the Paul Erdős center in Budapest 1998.

Theorem 1. If X ∈ Bi(n, p) and λ = np, then

ℙ(X ≥ 𝔼 X + t) ≤ exp(−\frac{t^{2}}{2(λ + t/3)}),  t ≥ 0;  (3)
ℙ(X ≤ 𝔼 X − t) ≤ exp(−\frac{t^{2}}{2λ}),  t ≥ 0.  (4)

Remark. The inequality (3) would not hold in general without the term t/3 in the denominator.

We now return to the case when X_{i} ∈ Be(p_{i}) with different p_{i}. Using Jensen’s inequality, it is easily seen that (1) holds in this case too, with p = λ/n = ∑ p_{i}/n. Consequently, the following generalization of Theorem 1 holds.

Theorem 2. If X_{i} ∈ Be(p_{i}), i = 1, …, n, are independent and X = ∑_{1}^{n} X_{i}, then (2), (3) and (4) hold, with λ = 𝔼 X.

Many other similar bounds, often sharper than (3) and (4), have been proved under these, or more general, assumptions by the same method (which goes back at least to Bernstein [4]); see e.g. [3], [11] and [1, Appendix A].

Remark. Much more precise estimates of the tail probabilities for sums of independent, but not necessarily identically distributed, random variables were obtained by Feller [10] using different methods. Feller’s result implies, for the cases above and with σ^{2} = Var X,

ℙ(X ≥ 𝔼 X + t) = e^{θ_{1} \frac{t}{σ^{2}} x^{2}}(1 − Φ(x) + \frac{θ_{2}}{σ} e^{−x^{2}/2}), 0 < t < σ^{2}/12,

where x = t/σ, Φ is the normal distribution function, |θ_{1}| ≤ 6/7(1 − 12t/σ^{2}) and |θ_{2}| < 9.

Very precise asymptotic results for the binomial distribution are given by Littlewood [16].

Some related distributions. The Poisson distribution Po(λ) is a limit of binomial distributions, and thus Theorem 1 implies the same bounds for the Poisson case.

Theorem 3. If X ∈ Po(λ), then (3) and (4) hold.

Furthermore, as a special case of a result in [22], a hypergeometric distribution is the distribution of a certain sum of independent indicator variables. (The proof is algebraic; there is no known probabilistic interpretation of these indicators, which in general have irrational expectations.) Consequently we can apply Theorem 2.

Theorem 4. Let X have a hypergeometric distribution with parameters N, n and m. Then (3) and (4) hold, with λ = 𝔼 X = mn/N.

(This was proved more directly by Hoeffding [11].)

2. Sums of dependent variables

In this section we discuss random variables of the type X = ∑_{α∈A} I_{α}, where I_{α} ∈ Be(p_{α}) are indicator variables as above, but now they may be dependent. (However, the inequalities below are useful only in cases when “most” variables are independent.) In order to quantify the dependence, we say that a graph Γ is a dependency graph for the family {I_{α}}_{α∈A} if the vertex set V (Γ) = A and two subfamilies {I_{α}}_{α∈A} and {I_{α}}_{α∈B} are independent whenever A and B are two disjoint subsets of A such that there is no edge in Γ connecting A and B.

Remark. A slightly weaker definition of dependency graph is commonly used for the Lovasz local lemma [1].

We concentrate for simplicity on bounds for ℙ(X = 0), i.e., on the probability that I_{α} = 0 for every α ∈ A. Similar bounds exist for the lower tail probabilities ℙ(X ≤ 𝔼 X − t), t ≥ 0, but not for the upper tail [12, 13].

A special case, which has had many applications in the last decade, is when there is an underlying family {J_{j}}_{j∈J} of independent random indicator variables, each index α is a (nonempty) subset of J and I_{α} = ∏_{j∈α} J_{j}. In other words, if W denotes the random set {j ∈ J : J_{j} = 1}, then I_{α} is the indicator of the event α ⊆ W, where α ∈ A, an arbitrary family of nonempty subsets of J. In this case, we define a dependency graph Γ by taking V (Γ) = A and letting the edge set consist of the edges αβ for all pairs α, β ∈ A with α ≠ β and α ∩ β ≠ ∅.

We fix a dependency graph Γ for {I_{α}} and write α ∼ β if α, β ∈ A and there is an edge in Γ between α and β. (In particular, then α ≠ β.) We further write α ∼ {β, γ} if α ∼ β or α ∼ γ, and define

• λ = 𝔼 X = ∑_{α∈A} p_{α}

• Δ = ∑_{{α,β}:α∼β} 𝔼(I_{α}I_{β}), summing over unordered pairs {α, β}, i.e. over the edges in Γ. As a sum over ordered pairs, Δ = \frac{1}{2} ∑_{α∈A} ∑_{β∼α} 𝔼(I_{α}I_{β}).

• δ_{α} = ∑_{β∼α} p_{β}.

• δ = max_{α∈A} δ_{α}.

• ε = max_{α∈A} p_{α}. In the special case we thus have Δ = \frac{1}{2} ∑ ∑_{α≠β, α∩β≠∅} 𝔼(I_{α}I_{β}). Then, the

following bounds hold [14].

Theorem 5. In the special case, with X = ∑ I_{A}, λ = 𝔼 X and Δ as above,

ℙ(X = 0) ≤ exp(−λ + Δ);  (5)
ℙ(X = 0) ≤ exp(−\frac{λ^{2}}{λ + 2Δ}) = exp (−\frac{λ^{2}}{∑ ∑_{α∩β≠∅} 𝔼(I_{α}I_{β})}) .  (6)

The first bound is best for Δ ≤ λ/2, while the second is better for larger Δ.

Remark. Boppana and Spencer [6] proved a slightly different version of (5), viz.

ℙ(X = 0) ≤ e^{Δ/(1−ε)} ∏_{α∈A}(1 − p_{α}),  (7)

which has the advantage of being exact when Δ = 0 (i.e. when the variables I_{α} are independent), but otherwise seems slightly less convenient for applications. Although the upper bounds (5) and (7) are quite close when ε = max p_{α} is small, neither of them dominates the other. It is intriguing to note that the conceivable common improvement e^{Δ} ∏_{α}(1 − p_{α}) fails to be an upper bound to ℙ(X = 0); this is seen by the simple example where X = I_{1} + I_{2} with I_{1} = I_{2} ∈ Be(p), for which Δ = p and ℙ(X = 0) = 1 − p > e^{p}(1 − p)^{2}, cf. [13].

Note also that in the special case, by the FKG inequality, we have the lower bound

ℙ(X = 0) ≥ ∏_{A∈A}(1 − p_{A}) ≥ exp(−\frac{λ}{1 − ε}),

which shows that the bounds above are quite sharp when Δ and ε are small.

The inequalities (5)–(7) have been widely used, although they apply only to the sum of indicator variables with a very special structure. For example, they apply to the number of copies of a given graph in 𝔾(n, p), but they do not apply to the number of induced copies.

In a paper which has too long been neglected, Suen [20] proved, at about the same time as [14, 6] and independently of them, a similar inequality for the general case. The Suen inequality and later versions of it [13] yield almost as good bounds as (5)–(7), but are thus much more widely applicable.

We do not give Suen’s original inequality [20] here, but rather a slight improvement of it (8) followed by two consequences of it [13], which are more convenient for applications and closely resemble (5) and (6) for the special case above.

Theorem 6. Let X = ∑_{α} I_{α}, where {I_{α}}_{α∈A} is a finite family of Bernoulli random variables having a dependency graph Γ. Then, with the notation above,

ℙ(X = 0) ≤ exp( ∑_{{α,β}:α∼β} 𝔼(I_{α}I_{β}) ∏_{γ∼{α,β}}(1 − p_{γ})^{−1}) ∏_{ν∈A}(1 − p_{ν}); (8)
ℙ(X = 0) ≤ exp(−λ + Δe^{2δ});  (9)
ℙ(X = 0) ≤ exp (− min(\frac{λ^{2}}{8Δ}, \frac{λ}{2}, \frac{λ}{6δ} )) = e^{−λ^{2}/ max(8Δ,2λ,6δλ)}.  (10)

The bounds (9) and (10) are similar to the ones in (5) and (6), but with extra terms involving δ and somewhat worse constants in (10). In applications, δ is usually small and the bounds (9) and (10) are often as useful as (5) and (6). Nevertheless, in at least one application (a recent bound for the 3-SAT problem by Kirousis, Kranakis, Krizanc and Stamatiou [15], where δ ≈ 0.089), the extra factor e^{2δ} in (9) affects the final result significantly, and it is desirable to reduce it as much as possible. It is shown in [13], using a proof by Spencer (personal communication), that if 0 ≤ δ + ε, this factor e^{2δ} can be replaced by the smallest root φ of φ = e^{(δ+ε)φ}; this is the version used in [15].

It is an open problem whether the factor e^{2δ} in (9) can be eliminated completely, i.e. whether (5) (or (6), (7)) holds in the general case too.

3. Azuma’s inequality

The final inequalitites that we consider apply to random variables of the form X = f(Z_{1}, …, Z_{N}), where Z_{1}, …, Z_{N} are independent random variables; here the underlying random variables Z_{k} can take values in arbitrary (and possibly different) spaces Λ_{k}. Our basic assumption is the following Lipschitz condition, for some numbers c_{1}, …, c_{N}. (In most applications, c_{k} = 1.)

(L) If the vectors z, z′ ∈ ∏_{1}^{N} Λ_{i} differ only in the kth coordinate, then |f(z) − f(z′)| ≤ c_{k}, k = 1, …, N.

In combinatorial applications, one often considers a random subset W of a set A = {a_{1}, …, a_{N}}, and sets Z_{k} = 1[a_{k} ∈ W], the indicator variable of the event {a_{k} ∈ W }.

More generally, we may partition the ground set A into blocks B_{k} and let Z_{k} be the vector of the indicator variables (1[a_{i} ∈ W])_{i∈B_{k}} (thus Z_{k} takes values in the product space {0, 1}^{B_{k}}). A common instance of this construction is “vertex exposure” for a random graph 𝔾(n, p), where A = {{i, j} : 1 ≤ i < j ≤ n} and B_{k} = {{i, k} : 1 ≤ i < k}, k = 1, …, n.

The first result for this situation is based on the following martingale inequality, known as Azuma’s inequality [2], although it was earlier proved by Hoeffding [11].

Theorem 7. If (X_{k})_{0}^{N} is a martingale, and there exist constants c_{k} ≥ 0 such that |X_{k} − X_{k−1}| ≤ c_{k}, k = 1, …, N, then

ℙ(X_{N} ≥ X_{0} + t) ≤ exp(−t^{2}/2 ∑_{1}^{N} c_{k}^{2}), t ≥ 0.

For applications to our situation, let X_{k} = 𝔼(X | Z_{1}, …, Z_{k}); then the assumptions of Theorem 7 are satisfied, and thus

ℙ(X ≥ 𝔼 X + t) ≤ exp(−t^{2}/2 ∑_{1}^{N} c_{k}^{2}).

In fact, the exponent here (but not in Theorem 7) may be improved by a factor 4 [17].

Theorem 8. Let Z_{1}, …, Z_{N} be independent random variables, with Z_{k} taking values in a set Λ_{k}. Assume that a (measurable) function f : Λ_{1} × Λ_{2} × ⋯ × Λ_{N} → ℝ satisfies the Lipschitz condition (L). Then, the random variable X = f(Z_{1}, …, Z_{N}) satisfies, for any t ≥ 0,

ℙ(X ≥ 𝔼 X + t) ≤ exp(−2t^{2} / ∑_{1}^{N} c_{k}^{2}),  (11)

ℙ(X ≤ 𝔼 X − t) ≤ exp(−2t^{2} / ∑_{1}^{N} c_{k}^{2}).  (12)

For further related results, including an extension to unbounded martingale differences, see the survey by Bollobás [5]. For another extension (weakening (L) by a truncation), see [7].

4. Talagrand’s inequality

Talagrand [21] has given several inequalities on concentration of measure, with various applications. We will here treat one of his inequalities only; it yields results similar to those obtained by Azuma’s inequality, although often much stronger, and it has already had important combinatorial applications.

Remark. The interested reader should study also the other inequalities by Talagrand in [21] and subsequent papers; it seems reasonable to guess that some of them too will be useful in combinatorial applications. Moreover, there are other proofs of the results below, with extensions in different directions, by Marton [18] and Dembo [9].

We continue with the assumptions of the preceding section, in particular condition (L), and assume furthermore the following, for some function ψ and the same c_{k} as in (L).

(C) If z = (z_{k})_{1}^{N} ∈ ∏_{1}^{N} Λ_{k} and r ∈ ℝ with f(z) ≥ r, then there exists a set J ⊆ {1, …, N} with ∑_{k∈J} c_{k}^{2} ≤ ψ(r), such that for all y = (y_{k})_{1}^{N} ∈

∏_{1}^{N} Λ_{k} with y_{k} = z_{k} when k ∈ J, we have f(y) ≥ r.

In other words, there exists a vector (z_{k})_{k∈J} (called a certificate), which forces f ≥ r, such that the index set J is not too large. (The set J generally depends on z and r.)

Every function f trivially satisfies (C) with ψ(r) = ∑_{1}^{N} c_{k}^{2} for all r; just take J = {1, …, N}. This choice of ψ in the theorem below yields an inequality similar to the one in Theorem 8, but generally somewhat weaker. In many interesting applications, however, (C) holds with a much smaller ψ; this leads to stronger estimates that significantly surpass Azuma’s inequality. (It is immaterial that we obtain inequalities for the deviation from the median instead of the mean.)

Example. Let X be the order of the largest independent set in the random graph 𝔾(n, p). Then, using vertex exposure as described above, (L) holds with c_{k} = 1, and (C) holds with ψ(r) = ⌈r⌉ for r ≥ 0; the certificate is just any independent set of order ⌈r⌉.

Talagrand’s inequality may then be stated as follows.

Theorem 9. Suppose that Z_{1}, …, Z_{N} are independent random variables taking their values in some sets Λ_{1}, …, Λ_{N}, respectively. Suppose further that X = f(Z_{1}, …, Z_{N}), where f : Λ_{1} × ⋯ × Λ_{N} → ℝ is a (measurable) function such that (L) and (C) hold for some constants c_{k}, k = 1, …, N, and some function ψ. Then, for every r ∈ ℝ and t ≥ 0,

ℙ(X ≤ r − t) ℙ(X ≥ r) ≤ e^{−t^{2}/4ψ(r)}.  (13)

In particular, if m is a median of X, then for every t ≥ 0,

ℙ(X ≤ m − t) ≤ 2e^{−t^{2}/4ψ(m)}  (14)

and

ℙ(X ≥ m + t) ≤ 2e^{−t^{2}/4ψ(m+t)}.  (15)

Actually, the theorem above is a simple corollary of the following more general inequality due to Talagrand [21].

Theorem 10. Suppose that A and B are two (measurable) subsets of ∏_{1}^{N} Λ_{k} such that for some t ≥ 0 the following separation condition holds: for every z ∈ B, there exists a non-zero vector α = (α_{i})_{1}^{N} ∈ ℝ^{N} such that for every y ∈ A,

∑_{i:y_{i}≠z_{i}} α_{i} ≥ t(∑_{1}^{N} α_{i}^{2})^{1/2}.

Then

ℙ(A) ℙ(B) ≤ e^{−t^{2}/4}.

Remark. Talagrand [21, Corollary 4.2.5] further showed that the conclusion of Theorem 10 can be improved to

\sqrt{log(1/ ℙ(A))} + \sqrt{log(1/ ℙ(B))} ≥ t/\sqrt{2},

which implies for example that (14) can be improved to the smaller, but more complicated, bound

ℙ(X ≤ m − t) ≤ exp(−\frac{1}{2ψ(m)}(t − \sqrt{2 log 2 ψ(m)})^{2}), t ≥ \sqrt{2 log 2 ψ(m)}.

Acknowledgement

This survey is based on a chapter in a forthcoming book on random graphs that I am writing together with Tomasz Łuczak and Andrzej Ruciński. I thank these my coauthors for helpful discussions, which have contributed to this paper too.

References

[1] N. Alon & J. Spencer, The Probabilistic Method. Wiley, New York 1992.

[2] K. Azuma, Weighted sums of certain dependent variables. Tôhoku Math. J. 3 (1967), 357–367.

[3] G. Bennett, Probability inequalities for the sum of independent random variables. J. Amer. Statist. Assoc. 57 (1962), 33–45.

[4] S. Bernstein, On a modification of Chebyshev’s inequality and of the error formula of Laplace. Ann. Sci. Inst. Savantes Ukraine, Sect. Math. 1 (1924), 38–49. (Russian)

[5] B. Bollobás, Martingales, isoperimetric inequalities and random graphs. In Combinatorics (Eger 1987), Colloq. Math. Soc. János Bolyai, 52, North-Holland, Amsterdam 1988, 113–139.

[6] R. Boppana & J. Spencer, A useful elementary correlation inequality. J. Combin. Th. Ser. A 50 (1989), 305–307.

[7] T.K. Chalker, A.P. Godbole, P. Hitczenko, J. Radcliff & O.G. Ruehr, On the size of a random sphere of influence graph. Adv. Appl. Probab. 31 (1999), 596–609.

[8] H. Chernoff, A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations. Ann. Math. Statist. 23 (1952), 493–507.

[9] A. Dembo, Information inequalities and concentration of measure. Ann. Probab. 25 (1997), 927–939.

[10] W. Feller, Generalization of a probability limit theorem of Cramér. Trans. Amer. Math. Soc. 54 (1943), 361–372.

[11] W. Hoeffding, Probability inequalities for sums of bounded random variables. J. Amer. Statist. Assoc. 58 (1963), 13–30.

[12] S. Janson, Poisson approximation for large deviations. Random Struct. Alg. 1 (1990), 221–229.

[13] S. Janson, New versions of Suen’s correlation inequality. Random Struct. Alg. 13 (1998), 467–483.

[14] S. Janson, T. Łuczak & A. Ruciński, An exponential bound for the probability of nonexistence of a specified subgraph in a random graph. In Random Graphs ’87 (Poznań 1987), Wiley, Chichester 1990, 73–87.

[15] L.M. Kirousis, E. Kranakis, D. Krizanc & Y.C. Stamatiou, Approximating the unsatisfiability threshold of random formulas. Random Struct. Alg. 12 (1998), 253–269.

[16] J. E. Littlewood, On the probability in the tail of a binomial distribution. Adv. Appl. Probab. 1 (1969), 43–72.

[17] C. McDiarmid, On the method of bounded differences. In Surveys in Combinatorics (Norwich 1989), London Math. Soc. Lect. Not. 141, Cambridge Univ. Press, Cambridge 1989, 148–188.

[18] K. Marton, A measure concentration inequality for contracting Markov chains. Geom. Funct. Anal. 6 (1996), 556–571. Erratum, Geom. Funct. Anal. 7 (1997), 609–613.

[19] M. Okamoto, Some inequalities relating to the partial sum of binomial probabilities. Ann. Inst. Statist. Math. 10 (1958), 29–35.

[20] W.C.S. Suen, A correlation inequality and a Poisson limit theorem for nonoverlapping balanced subgraphs of a random graph. Random Struct. Alg. 1 (1990), 231–242.

[21] M. Talagrand, Concentration of measure and isoperimetric inequalities in product spaces. Inst. Hautes Études Sci. Publ. Math. 81 (1995), 73–205.

[22] V.A. Vatutin & V.G. Mikhaĭlov, Limit theorems for the number of empty cells in an equiprobable scheme for group allocation of particles. Teor. Veroyatnost. i Primenen. 27 (1982), 684–692 (Russian); English transl. Theor. Probab. Appl. 27 (1982), 734–743.

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

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