NEW VERSIONS OF SUEN’S CORRELATION INEQUALITY

SVANTE JANSON

1. Introduction

Suen [8] found a remarkable correlation inequality, giving estimates for the probability that a collection of dependent random indicator variables vanish simultaneously, or in other words, for the probability that none of a collection of dependent events occurs.

The present author [4, 3] has found similar inequalities for a much more restricted situation; when applicable, these inequalities are somewhat better than Suen’s, although the difference is negligible in many cases. (See Section 8 below.) Those inequalities have been used by several different authors for a variety of problems; there are, however, many situations where they are not applicable (see [8, 5] for two examples) and then Suen’s inequality is a very attractive choice.

The purpose of the present note is to present some improvements and modifications of Suen’s original inequality which (we hope) will be easy to apply in different situations.

The estimates considered here are exponential (unlike for example Chebyshev’s inequality), in the sense that they typically are similar to the estimate exp(−μ) for the independent case, where μ is the expected number of events. They are thus aimed at the case when the studied probability is very small, and has to be shown to be very small. In many applications, constants occuring in the estimates, even in the exponents, are immaterial; on the other hand, there are applications where very precise estimates are desired. For this reason, and because different versions of the inequality turn out to be useful in different situations, we will give several different versions of our estimates.

We give several upper bounds to the probability of simultaneous vanishing of a collection of indicator variables in Section 3; these are perhaps the main results of the paper. We give some corresponding lower bounds in Section 4, and in Section 5 an upper bound for the probability that only a few of the variables are non-zero. Section 6 contains the proofs of the results, while Section 7 contains three examples related to the sharpness of the results. Finally, Section 8 contains a short discussion of the results and some open problems. Acknowledgement. This paper has benefitted from discussions with participants of the Eighth International Conference on Random Structures and Algorithms in Poznań in August 1997. In particular, I am grateful to Joel Spencer, both for his pertinent questions that inspired parts of this work, and for him generously allowing me to include his proof of Theorem 7.

Date: September 23, 1997.

2. Notation

We will throughout the paper use the following assumptions and notation. Recall that an indicator (or Bernoulli) random variable is a random variable taking only the values 0 and 1.

• {I_{i}}_{i∈I} is a finite family of indicator random variables (defined on a common probability space).

• Γ is a dependency graph for {I_{i}}_{i∈I}, i.e. a graph with vertex set I such that if A and B are two disjoint subsets of I, and Γ contains no edge between A and B, then the families {I_{i}}_{i∈A} and {I_{i}}_{i∈B} are independent.

• S = ∑_{i} I_{i}. In particular S = 0 if and only if all I_{i} = 0. The expression ℙ(S = 0) in the theorems below may thus be regarded as shorthand for ℙ(every I_{i} = 0).

• i ∼ j, where i, j ∈ I, if there is an edge in Γ between i and j. (In particular, i ≁ i.)

• i ∼ A, where i ∈ I and A ⊆ I, if i ∼ j for some j ∈ A. (i ∈ A is not excluded.)

• p_{i} = ℙ(I_{i} = 1) = 𝔼 I_{i}. Thus ℙ(I_{i} = 0) = 1 − p_{i}.

• μ = 𝔼 S = ∑_{i} p_{i}.

• δ_{i} = ∑_{j∼i} p_{j}.

• δ = max_{i∈I} δ_{i}.

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

• Δ_{0} = ∑_{\{i,j\}:i∼j} p_{i}p_{j} = \frac{1}{2} ∑_{i∈I} p_{i}δ_{i}. Note that Δ_{0} ≤ Δ if the variables are positively correlated, while Δ_{0} ≥ Δ if the variables are negatively correlated.

• ε = max_{i∈I} p_{i}. Remark 1. In typical applications, there exists a natural dependency graph, but it should be observed that in general there is no unique choice, even if it is required to be minimal. Remark 2. In the Lovász local lemma, see e.g. [1], a weaker notion of dependency graph is used, where the independence condition above is required only when A is a singleton {I_{i}} (but B still is an arbitrary subset). These strong and weak versions are not equivalent, but we do not know any application where the difference matters.

We do not know whether the results below hold if Γ only is assumed to be a dependency graph in the weaker sense. Remark 3. In particular, two variables I_{i} and I_{j} are independent unless there is an edge in Γ between i and j. Note, however, that this weaker condition (i.e. the condition above when both A and B are restricted to singletons) does not imply that Γ is a dependency graph, and that it is not sufficient for our results.

For a simple counter example to many of the results below under this weaker condition, colour the vertices of the complete graph K_{n} at random (independently and with equal probabilities) with two colours, and let, for each edge ij, I_{ij} be the indicator that i and j have different colours. These \binom{n}{2} indicator variables are pairwise independent, so we could take Γ to be the empty graph with no edges, and then the upper bounds below are all less than 2^{−cn^{2}}, for some c > 0; on the other hand, clearly S = 0 if and only if all vertices have the same colour, and thus ℙ(S = 0) = 2^{1−n}.

Remark 4. In several related papers, Δ is instead defined as a sum over ordered pairs, yielding twice our value. This should be kept in mind when comparing results.

3. Upper bounds

As explained in the introduction, we will in this section give several different upper bounds for ℙ(S = 0), suitable for different (present or future) applications.

We begin with a slight improvement of Suen’s original inequality [8], essentially following (but sharpening) the original proof. (Suen [8] has 2(𝔼(I_{i}I_{j}) + p_{i}p_{j}) instead of 𝔼(I_{i}I_{j}) below; the p_{i}p_{j} is really needed only for his lower bound, see Section 4, while the factor 2 is removed by a more careful estimate in the proof.) For convenience, all proofs are given in Section 6.

Theorem 1. Let {I_{i}}_{i∈I} be a finite family of indicator random variables having a dependency graph Γ. Then, with notations as above,

ℙ(S = 0) ≤ exp( ∑_{{i,j}:i∼j} 𝔼(I_{i}I_{j}) ∏_{k∼{i,j}}(1 − p_{k})^{−1}) ∏_{l∈I}(1 − p_{l}).

Large products are often less convenient than large sums. For example, it is often convenient to use the standard estimate ∏(1−p_{i}) ≤ exp(− ∑ p_{i}) = e^{−μ}. In a similar spirit, the estimate in Theorem 1 can be modified as follows, often without significant loss.

Theorem 2. With assumptions as in Theorem 1,

ℙ(S = 0) ≤ exp(−μ + ∑_{{i,j}:i∼j} 𝔼(I_{i}I_{j}) exp( ∑_{k∼{i,j}} p_{k})) ≤ e^{−μ+Δe^{2δ}}.

Theorems 1 and 2 are useful, and often quite sharp, when Δ < μ and δ is small. If Δ ≥ μ, Theorem 2 (and typically Theorem 1 too) is worthless, since the right hand side becomes greater than 1. In this case, the following version becomes useful.

Theorem 3. With assumptions as in Theorem 1,

ℙ(S = 0) ≤ exp(− min(\frac{μ^{2}}{8Δ}, \frac{μ}{6δ} , \frac{μ}{2})) = e^{−μ^{2}/ max(8Δ,2μ,6δμ)}.

The numerical constants in the exponents can be improved, but there is (with our proof, at least) a trade off between the different constants, and the optimal choice depends on the relations between μ, Δ and δ. The version given here is a compromise trying to be both simple and reasonably sharp. In an application where constant factors in the exponent are important, it is probably better to use the proof below, in particular (8), and choose q there according to the situation at hand.

Of the three quantities in the exponents in Theorem 3, the one involving δ is typically the least important. If we do not care about the constants, we can always replace it by a term involving Δ_{0}, which in many applications is dominated by Δ. (Again, the constants given here are not optimal.)

Theorem 4. With assumptions as in Theorem 1,

ℙ(S = 0) ≤ e^{−μ^{2}/ max(32Δ,48Δ_{0},4μ)}.

Theorem 5. With assumptions as in Theorem 1, if furthermore the variables {I_{i}} are positively correlated,

ℙ(S = 0) ≤ e^{−μ^{2}/ max(48Δ,4μ)}.

We do not know whether the terms involving δ really are needed in the estimates above, cf. Section 8. In most applications they are harmless, but in at least one [5] they affect the final result significantly. For that reason, we give two slightly stronger versions of Theorems 1 and 2, where this term is reduced as much as we have been able to achieve.

Define

φ_{1}(x) = 2 ∫_{0}^{1} te^{tx} dt = 2\frac{xe^{x} − e^{x} + 1}{x^{2}} = e^{x} \frac{e^{−x} − 1 + x}{x^{2}/2}

and observe that 1 ≤ φ_{1}(x) ≤ e^{x} for x ≥ 0. For small x, φ_{1}(x) = 1+\frac{2}{3}x+O(x^{2}).

Theorem 6. With assumptions as in Theorem 1,

ℙ(S = 0) ≤ exp(\frac{1}{2} ∑_{i} ∑_{j∼i} 𝔼(I_{i}I_{j})(1 − p_{j})^{−1}φ_{1}( ∑_{k∼\{i,j\}, k≠i,j} p_{k}/(1 − p_{k})))

× ∏_{l∈I}(1 − p_{l})

≤ exp(Δ(1 − ε)^{−1}φ_{1}(2δ/(1 − ε))) ∏_{l∈I}(1 − p_{l})

and

ℙ(S = 0) ≤ exp(−μ + e^{ε}φ_{1}(2e^{ε}δ)Δ).

Joel Spencer [6] has found a different proof of this type of inequalities, using only elementary probability calculations. This proof yields the following result, which sometimes is better than Theorem 6; when ε is negligible, Theorem 7 is better when 0 < δ < 0.225 … while Theorem 6 is better for larger δ. (This strongly suggests that neither is the best possible, and that there is room for future improvements of these results.)

Define φ_{2}(x), 0 ≤ x ≤ e^{−1}, to be the smallest root of

φ_{2}(x) = e^{xφ_{2}(x)}.  (1)

It is well known that φ_{2} is well defined in [0, e^{−1}], with the Taylor series

φ_{2}(x) = ∑_{0}^{∞} \frac{(n + 1)^{n−1}}{n!} x^{n}, 0 ≤ x ≤ e^{−1};

in particular, φ_{2}(x) = 1 + x + O(x^{2}).

Theorem 7 (Spencer [6]). With assumptions as in Theorem 1, if furthermore δ + ε ≤ e^{−1},

ℙ(S = 0) ≤ e^{Δφ_{2}(δ+ε)} ∏_{k∈I}(1 − p_{k}) ≤ e^{−μ+Δφ_{2}(δ+ε)}.

Remark 5. As is seen from the proof of Theorem 7, further improvements are possible if the dependency graph is such that the neigbourhoods of two adjacent vertices overlap significantly; cf. Theorem 6, where such an effect can be seen in the first upper bound.

4. Lower bounds

Suen [8] gave also a lower bound to ℙ(S = 0) corresponding to his upper bound. Although the lower bound seems to have less applications, we for completeness give an improvement of it too corresponding to Theorem 1. (We ignore further improvements corresponding to Theorem 6.)

Theorem 8. With assumptions as in Theorem 1, let

Δ^{∗} = ∑_{{i,j}:i∼j} 𝔼(I_{i}I_{j}) ∏_{k∼{i,j}}(1 − p_{k})^{−1},
Δ_{0}^{∗} = ∑_{{i,j}:i∼j} p_{i}p_{j} ∏_{k∼{i,j}}(1 − p_{k})^{−1}.

Then

ℙ(S = 0) ≥ (1 − Δ_{0}^{∗} exp(Δ^{∗})) ∏_{k∈I}(1 − p_{k})

≥ (1 − Δ_{0}e^{2δ/(1−ε)} exp(Δe^{2δ/(1−ε)})) ∏_{k∈I}(1 − p_{k}).

Remark 6. The careful reader may observe from the proof that the factor exp(Δ^{∗}) can be replaced by the somewhat smaller φ_{3}(Δ^{∗}), where φ_{3}(x) = (e^{x} − 1)/x. (We do not know whether this factor depending on Δ^{∗} really is needed at all, or whether it is an artefact of our proof.)

Moreover, since Δ_{0}^{∗} exp(Δ^{∗}) ≤ exp(Δ_{0}^{∗} + Δ^{∗}) − exp(Δ^{∗}) ≤ exp(Δ_{0}^{∗} + Δ^{∗}) − 1, the factor 1 − Δ_{0}^{∗} exp(Δ^{∗}) may be replaced by the smaller 2 − exp(Δ^{∗} + Δ_{0}^{∗}); Suen [8] has 2 − exp(2Δ^{∗} + 2Δ_{0}^{∗}).

Theorem 8 is useful only when Δ_{0} < 1 and Δ is small, but even then it is often surpassed by the following quantitative version of the Lovász local lemma, cf. [1, Chapter 5].

Theorem 9. With assumptions as in Theorem 1, suppose further that δ +ε ≤ e^{−1}. Then, with φ_{2} defined by (1),

ℙ(S = 0) ≥ exp(−μφ_{2}(δ + ε)).

5. Tail estimates

It is also possible to obtain exponential upper bounds for the lower tails ℙ(S ≤ λ), λ < μ, of the distribution of S, similar to the bounds given above for ℙ(S = 0). (There are no similar general bounds for the upper tails ℙ(S ≥ λ), λ > μ, see [3, Example 2].)

Theorem 10. With assumptions as in Theorem 1, and 0 ≤ a ≤ 1,

ℙ(S ≤ aμ) ≤ exp(− min((1 − a)^{2} \frac{μ^{2}}{8Δ + 2μ}, (1 − a)\frac{μ}{6δ} )).

Note that the special case a = 0 yields the corollary

ℙ(S = 0) ≤ e^{−μ^{2}/ max(8Δ+2μ,6δμ)},

which is only slightly weaker than Theorem 3.

Remark 7. The tail bounds given in [3] for a special case are of the same type as Theorem 10 but somewhat better; there 8Δ is replaced by 4Δ and there is no term with δ.

6. Proofs

We define for each index i ∈ I a partition I = {i} ∪ N_{i} ∪ U_{i} of the index set, with N_{i} = {j ∈ I : j ∼ i} (the neighbours of i in Γ) and thus U_{i} = {j ≠ i : j ≁ i}; hence I_{i} is independent of {I_{j} : j ∈ U_{i}}.

Proof of Theorem 1. Define, for 0 ≤ t ≤ 1, the random function

F (t) = ∏_{i∈I}(1 − p_{i} − t(I_{i} − p_{i})).

Thus F (0) = ∏_{i}(1 − p_{i}) and F (1) = ∏_{i}(1 − I_{i}), so 𝔼 F (1) = ℙ(S = 0). We thus want to compare 𝔼 F (1) and 𝔼 F (0) = F (0). (Note that in the case of independent indicators I_{i}, 𝔼 F (t) is independent of t.)

We differentiate and obtain, introducing the notation F_{A}(t) = ∏_{i∈A}(1−p_{i} − t(I_{i} − p_{i})) for A ⊆ I,

\begin{aligned}F′(t) & = − ∑_{i}(I_{i} − p_{i}) ∏_{j≠i}(1 − p_{j} − t(I_{j} − p_{j})) = − ∑_{i}(I_{i} − p_{i})F_{I\\{i\}}(t) \\ & = − ∑_{i}(I_{i} − p_{i})F_{N_{i}}(t)F_{U_{i}}(t). \end{aligned} (2)

Note that, for 0 ≤ t ≤ 1 and each j,

0 ≤ 1 − p_{j} − t(I_{j} − p_{j}) ≤ 1 − p_{j} + tp_{j} ≤ 1.  (3)

Hence, for any set A ⊆ I,

0 ≤ ∏_{j∈A}(1 − p_{j} + tp_{j}) − F_{A}(t) ≤ ∑_{j∈A} tI_{j},  (4)

and thus, considering the cases I_{i} = 0 and I_{i} = 1 separately,

(I_{i} − p_{i})(∏_{j∈A}(1 − p_{j} + tp_{j}) − F_{A}(t)) ≤ I_{i} ∑_{j∈A} tI_{j}.  (5)

Choosing A = N_{i}, this and (2) yield

F′(t) ≤ − ∑_{i} F_{U_{i}}(t)(I_{i} − p_{i}) ∏_{j∈N_{i}}(1 − p_{j} + tp_{j}) + ∑_{i} F_{U_{i}}(t)I_{i} ∑_{j∈N_{i}} tI_{j}.

Since, by the definition of a dependency graph, I_{i} and F_{U_{i}}(t) are independent, 𝔼(F_{U_{i}}(t)(I_{i} − p_{i})) = 0. Moreover, using (3), F_{U_{i}}(t) ≤ F_{U_{i}∩U_{j}}(t), which is independent of I_{i}I_{j}. Hence, for 0 ≤ t ≤ 1,

\begin{aligned}𝔼 F′(t) & ≤ ∑_{i} ∑_{j∼i} t 𝔼(I_{i}I_{j}F_{U_{i}}(t)) ≤ ∑_{i} ∑_{j∼i} t 𝔼(I_{i}I_{j}F_{U_{i}∩U_{j}}(t)) \\ & = t ∑_{i} ∑_{j∼i} 𝔼(I_{i}I_{j}) 𝔼 F_{U_{i}∩U_{j}}(t). \end{aligned}  (6)

Now, let y_{ij} = 𝔼(I_{i}I_{j}) ∏_{k∼{i,j}}(1 − p_{k})^{−1} and Δ^{∗} = ∑_{{i,j}:i∼j} y_{ij}. We claim that

𝔼 F (t) ≤ e^{t^{2}Δ^{∗}} ∏_{k∈I}(1 − p_{k}),  0 ≤ t ≤ 1.  (7)

In fact, we may by induction over |I|, the number of variables, assume that the corresponding inequality holds for 𝔼 F_{A}(t) for every proper subset A of I. Since the corresponding values y_{ij}^{(A)} for a subset A (and i, j ∈ A) satisfy y_{ij}^{(A)} ≤ y_{ij}, it then follows from (6) that, using also that when i ∼ j, I \ (U_{i} ∩ U_{j}) = N_{i} ∪ N_{j} = {k : k ∼ {i, j}},

\begin{aligned}𝔼 F′(t) & ≤ t ∑_{i} ∑_{j∼i} 𝔼(I_{i}I_{j})e^{t^{2}Δ^{∗}} ∏_{k∈U_{i}∩U_{j}}(1 − p_{k}) = t ∑_{i} ∑_{j∼i} y_{ij}e^{t^{2}Δ^{∗}} ∏_{k∈I}(1 − p_{k}) \\ & = 2tΔ^{∗}e^{t^{2}Δ^{∗}} ∏_{k∈I}(1 − p_{k}) = \frac{d}{dt}e^{t^{2}Δ^{∗}} ∏_{k∈I}(1 − p_{k}). \end{aligned}

The estimate (7) now follows by integration, since it holds (with equality) for t = 0.

The theorem follows by choosing t = 1 in (7).

Remark 8. If all p_{i} are equal, p_{i} = p say, then F (t) = (1 − p + pt)^{|I|}e^{−uS}, with u = ln((1 − p + tp)/(1 − p)(1 − t)); hence estimating 𝔼 F (t), 0 ≤ t ≤ 1, is equivalent to estimating the Laplace transform 𝔼 e^{−uS}, u ≥ 0. In general, with unequal p_{i}, 𝔼 F (t) is not equivalent to the Laplace transform; nevertheless, 𝔼 e^{−uS} may be estimated by arguments similar to the ones above, which leads to results similar to the ones given here. It seems, however, that estimates of F (as in Suen’s paper [8]) lead to slightly stronger results. For applications of the Laplace transform, see the proof of Theorem 10 below, and also [4, 3] where it is used advantageously in a special case.

We derive Theorems 2–5 as corollaries to Theorem 1 by performing a random thinning of the family {I_{i}}. (This idea is used by Alon and Spencer [1] for a related inequality.) Let q_{i} ∈ [0, 1] and let J_{i} ∼ Be(q_{i}) be Bernoulli variables that are independent of each other and of {I_{i}}. Define I′_{i} = I_{i}J_{i} and S′ = ∑_{i∈I} I′_{i}. Clearly, S′ ≤ S and thus ℙ(S = 0) ≤ ℙ(S′ = 0). Moreover, Γ is a dependency graph for {I′_{i}} too. Consequently, we may apply our estimates to the family {I′_{i}} and obtain new estimates for ℙ(S = 0); with suitable choices of q_{i}, this may improve the original estimate.

Let p′_{i} = 𝔼 I′_{i} = p_{i}q_{i}, thus 0 ≤ p′_{i} ≤ p_{i}.

Proof of Theorem 2. If we choose q_{i} = (1 − e^{−p_{i}})/p_{i}, and thus p′_{i} = 1 − e^{−p_{i}}, then Theorem 1 applied to {I′_{i}} yields

ℙ(S = 0) ≤ ℙ(S′ = 0) ≤ exp( ∑_{{i,j}:i∼j} q_{i}q_{j} 𝔼(I_{i}I_{j}) ∏_{k∼{i,j}} e^{p_{k}}) ∏_{l∈I} e^{−p_{l}},

which implies the first inequality.

The final estimate follows because ∑_{k∼{i,j}} p_{k} ≤ δ_{i} + δ_{j} ≤ 2δ.

Proof of Theorem 3. Using a new thinning {I′_{i}}, this time choosing all q_{i} = q for some q ∈ [0, 1], we obtain from Theorem 2 applied to {I′_{i}}

ℙ(S = 0) ≤ ℙ(S′ = 0) ≤ e^{−qμ+q^{2}Δe^{2qδ}}.  (8)

We choose q = min(μ/4Δ, 1/3δ, 1); then qΔ ≤ μ/4 and e^{2qδ} ≤ e^{2/3} < 2, and consequently (8) yields

ℙ(S = 0) ≤ e^{−qμ+ \frac{1}{2} qμ} = e^{− \frac{1}{2} qμ},

which is the desired result.

Proof of Theorem 4. This time we use a deterministic thinning {I_{i}}_{i∈J}, where

J = {i ∈ I : δ_{i} ≤ 4Δ_{0}/μ}.

We let μ′, Δ′ and δ′ denote the quantities for our subfamily {I_{i}}_{i∈J} corresponding to μ, Δ and δ. By our choice of J,

∑_{i∉J} p_{i} ≤ \frac{μ}{4Δ_{0}} ∑_{i∈I} p_{i}δ_{i} = \frac{μ}{4Δ_{0}} 2Δ_{0} = \frac{μ}{2}

and thus

μ′ = ∑_{i∈J} p_{i} = ∑_{i∈I} p_{i} − ∑_{i∉J} p_{i} ≥ μ − \frac{μ}{2} = \frac{μ}{2}.

Moreover, clearly δ′ ≤ 4Δ_{0}/μ and Δ′ ≤ Δ.

Consequently, Theorem 3 applied to S′ = ∑_{i∈J} I_{i} yields

ℙ(S = 0) ≤ ℙ(S′ = 0) ≤ e^{− min(\frac{μ′^{2}}{8Δ′} , \frac{μ′}{6δ′} , \frac{μ′}{2} )} ≤ e^{− min(\frac{μ^{2}}{32Δ} , \frac{μ}{48Δ_{0}/μ} , \frac{μ}{4})}.

Proof of Theorem 5. When the variables are positively correlated, 𝔼(I_{i}I_{j}) ≥ p_{i}p_{j} and thus Δ ≥ Δ_{0}.

Proof of Theorem 6. We follow the proof of Theorem 1, improving some estimates. We define, for A ⊆ I, β_{A}(t) = ∏_{i∈A}(1 − p_{i} + tp_{i}). Using (3), we can improve (4) to

∏_{j∈A}(1 − p_{j} + tp_{j}) − F_{A}(t) ≤ ∑_{j∈A} tI_{j}β_{A\{j}}(t),

and then (5) to

(I_{i} − p_{i})(∏_{j∈A}(1 − p_{j} + tp_{j}) − F_{A}(t)) ≤ I_{i}(1 − p_{i}) ∑_{j∈A} tI_{j}β_{A\{j}}(t). (9)

Moreover, F_{U_{i}}(t) ≤ F_{U_{i}∩U_{j}}(t)β_{U_{i}\U_{j}}(t), which together with (9) yields as an improved version of (6), for 0 ≤ t ≤ 1,

𝔼 F′(t) ≤ t ∑_{i} ∑_{j∼i} 𝔼(I_{i}I_{j}) 𝔼 F_{U_{i}∩U_{j}}(t)(1 − p_{i})β_{N_{i}\{j}}(t)β_{U_{i}\U_{j}}(t).  (10)

We now define, when i ∼ j, N_{ij} = (N_{i} \ {j}) ∪ (U_{i} \ U_{j}) = N_{i} ∪ N_{j} \ {i, j},

ψ(t) = t ∑_{i} ∑_{j∼i} 𝔼(I_{i}I_{j})(1 − p_{j})^{−1} ∏_{k∈N_{ij}}(1 + tp_{k}/(1 − p_{k}))

and

Ψ(t) = ∫_{0}^{t} ψ(s) ds.

It then follows from (10) by induction as in the proof of Theorem 1 that

𝔼 F (t) ≤ e^{Ψ(t)} ∏_{k∈I}(1 − p_{k}),  0 ≤ t ≤ 1.  (11)

The first claim in the theorem now follows by choosing t = 1 in (11), observing that

ψ(t) ≤ t ∑_{i} ∑_{j∼i} 𝔼(I_{i}I_{j})(1 − p_{j})^{−1} exp( ∑_{k∈N_{ij}} tp_{k}/(1 − p_{k}))

and thus

Ψ(1) = ∫_{0}^{1} ψ(t) dt ≤ ∑_{i} ∑_{j∼i} 𝔼(I_{i}I_{j})(1 − p_{j})^{−1} \frac{1}{2}φ_{1}( ∑_{k∈N_{ij}} p_{k}/(1 − p_{k})).

The second inequality in the theorem is immediate.

For the final estimate, we perform a random thinning with p′_{i} = 1 − e^{−p_{i}} as in the proof of Theorem 2; we leave the details to the reader.

For Theorem 7 we use the following form of the Lovász local lemma, which is easily proved by induction, see [1, Lemma 5.1.1 and its proof]. Let, for A ⊆ I, S_{A} = ∑_{i∈A} I_{i}.

Lemma 1. With assumptions as in Theorem 1, suppose further that x_{i}, i ∈ I, are real numbers such that 0 ≤ x_{i} < 1 and

p_{i} ≤ x_{i} ∏_{j∼i}(1 − x_{j}),  i ∈ I.  (12)

Then, for any two subsets A, B ⊆ I, ℙ(S_{A} = 0 | S_{B} = 0) ≥ ∏_{i∈A}(1 − x_{i}).

We will employ Lemma 1 with the following choice of x_{i}.

Lemma 2. With assumptions as in Theorem 1, suppose further that δ + ε ≤ e^{−1}. Let φ = φ_{2}(δ + ε), where φ_{2} is defined by (1), and let x_{i} = 1 − e^{−φp_{i}}, i ∈ I. Then (12) holds and, for any two subsets A, B ⊆ I,

ℙ(S_{A} = 0 | S_{B} = 0) ≥ ∏_{i∈A}(1 − x_{i}) = e^{−φ ∑_{i∈A} p_{i}}.

Proof of Lemma 2. By (1), e^{(δ+ε)φ} = φ, and thus

x_{i} ∏_{j∼i}(1 − x_{j}) = (1 − e^{−φp_{i}})e^{−φδ_{i}} = (e^{φp_{i}} − 1)e^{−(δ_{i}+p_{i})φ} ≥ φp_{i}e^{−(δ+ε)φ} = p_{i}.

Consequently (12) holds, and the final inequality follows by Lemma 1.

Proof of Theorem 7 (after Spencer [6]). The main idea is to estimate the conditional probability ℙ(I_{i} = 0 | S_{I\{i}} = 0). Recall that S_{I\{i}} = S_{N_{i}} + S_{U_{i}}, and that I_{i} and S_{U_{i}} are independent; furthermore, note the elementary identity ℙ(E_{1} | E_{2} and E_{3}) = ℙ(E_{1} and E_{2} | E_{3})/ ℙ(E_{2} | E_{3}) for any three events E_{1}, E_{2}, E_{3}. Consequently, we have the estimate

\begin{aligned}ℙ(I_{i} = 1 | S_{I\\{i\}} = 0) & = \frac{ℙ(I_{i} = 1 and S_{N_{i}} = 0 | S_{U_{i}} = 0)}{ℙ(S_{N_{i}} = 0 | S_{U_{i}} = 0)} \\ & ≥ ℙ(I_{i} = 1 and S_{N_{i}} = 0 | S_{U_{i}} = 0) \\ & = ℙ(I_{i} = 1 | S_{U_{i}} = 0) − ℙ(⋃_{j∼i}\{I_{i} = I_{j} = 1\} | S_{U_{i}} = 0) \\ & ≥ ℙ(I_{i} = 1) − ∑_{j∼i} ℙ(I_{i} = I_{j} = 1 | S_{U_{i}} = 0). \end{aligned} (13)

Similarly, when j ∼ i ∈ I, since {I_{i}, I_{j}} and S_{U_{i}∩U_{j}} are independent,

ℙ(I_{i} = I_{j} = 1 | S_{U_{i}} = 0) = \frac{ℙ(I_{i} = I_{j} = 1 and S_{U_{i}∩N_{j}} = 0 | S_{U_{i}∩U_{j}} = 0)}{ℙ(S_{U_{i}∩N_{j}} = 0 | S_{U_{i}∩U_{j}} = 0)}

≤ \frac{ℙ(I_{i} = I_{j} = 1 | S_{U_{i}∩U_{j}} = 0)}{ℙ(S_{U_{i}∩N_{j}} = 0 | S_{U_{i}∩U_{j}} = 0)} = \frac{ℙ(I_{i} = I_{j} = 1)}{ℙ(S_{U_{i}∩N_{j}} = 0 | S_{U_{i}∩U_{j}} = 0)}.

Applying Lemma 2, we thus obtain

ℙ(I_{i} = I_{j} = 1 | S_{U_{i}} = 0) ≤ ℙ(I_{i} = I_{j} = 1)e^{φ ∑_{k∈U_{i}∩N_{j}} p_{k}}.  (14)

Note that p_{i} ≤ x_{i} by (12), and thus 1 = (1 − x_{i})e^{φp_{i}} ≤ (1 − p_{i})e^{φp_{i}}; moreover (N_{j} ∩ U_{i}) ∪ {i} = N_{j} \ N_{i} provided i ∼ j. By combining (13) and (14) we thus obtain the sought estimate

\begin{aligned}ℙ(I_{i} = 0 | S_{I\\{i\}} = 0) & ≤ 1 − p_{i} + ∑_{j∼i} ℙ(I_{i} = I_{j} = 1 | S_{U_{i}} = 0) \\ & ≤ 1 − p_{i} + (1 − p_{i})e^{φp_{i}} ∑_{j∼i} ℙ(I_{i} = I_{j} = 1)e^{φ ∑_{k∈U_{i}∩N_{j}} p_{k}} \\ & = (1 − p_{i})(1 + ∑_{j∼i} 𝔼(I_{i}I_{j})e^{φ ∑_{k∈N_{j} \N_{i}} p_{k}}) \\ & ≤ (1 − p_{i}) exp(∑_{j∼i} 𝔼(I_{i}I_{j})e^{φ ∑_{k∈N_{j} \N_{i}} p_{k}}). \end{aligned} (15)

For the final step, we may assume that the index set I = {1, …, n}. We apply (15) to the subset {1, …, i} of I and obtain, for i = 1, …, n,

\begin{aligned}ℙ(I_{i} = 0 | I_{1} = ⋯ = I_{i−1} = 0) & ≤ (1 − p_{i}) exp( ∑_{j∼i, j<i} 𝔼(I_{i}I_{j})e^{φ ∑_{k∈N_{j} \N_{i}} p_{k}}) \\ & ≤ (1 − p_{i}) exp( ∑_{j∼i, j<i} 𝔼(I_{i}I_{j})e^{φδ_{j}}). \end{aligned}

The result follows by multiplying these inequalities for i = 1, …, n, and using e^{φδ_{j}} ≤ e^{(δ+ε)φ} = φ.

Proof of Theorem 8. We follow the proof of Theorem 1. The main idea is that there is a lower bound corresponding to (5), viz.

(I_{i} − p_{i})(∏_{j∈A}(1 − p_{j} + tp_{j}) − F_{A}(t)) ≥ −p_{i} ∑_{j∈A} tI_{j}.

The same arguments that led to (6) then yield (we leave the details to the reader), for 0 ≤ t ≤ 1,

𝔼 F′(t) ≥ −t ∑_{i} ∑_{j∼i} p_{i}p_{j} 𝔼 F_{U_{i}∩U_{j}}(t).

We now use the upper bound to 𝔼 F_{U_{i}∩U_{j}}(t) proved in (7) and obtain

\begin{aligned}𝔼 F′(t) & ≥ −t ∑_{i} ∑_{j∼i} p_{i}p_{j}e^{t^{2}Δ^{∗}} ∏_{k∈U_{i}∩U_{j}}(1 − p_{k}) \\ & = −2tΔ_{0}^{∗}e^{t^{2}Δ^{∗}} ∏_{k∈I}(1 − p_{k}) ≥ −2tΔ_{0}^{∗}e^{Δ^{∗}} ∏_{k∈I}(1 − p_{k}). \end{aligned}

Integrating this for 0 ≤ t ≤ 1, we obtain

F (1) − F (0) ≥ −Δ_{0}^{∗}e^{Δ^{∗}} ∏_{k∈I}(1 − p_{k}).

Since ℙ(S = 0) = F (1) and F (0) = ∏_{k∈I}(1−p_{k}), this yields the first inequality in the statement. The second follows by the estimate (1−p_{k})^{−1} ≤ exp(p_{k}/(1− p_{k})) ≤ exp(p_{k}/(1 − ε)).

Proof of Theorem 9. This is just the special case A = I and B = ∅ of Lemma 2.

Proof of Theorem 10. We use the standard method of first estimating the Laplace transform 𝔼 e^{−tS} and then applying Markov’s inequality. As remarked above, it is possible to estimate the Laplace transform directly by the method of the proof of Theorem 1. For simplicity, and to avoid repetitions, we will, however, instead use the results above together with another thinning.

Define thinned variables I′_{i} = J_{i}I_{i} as above with q_{i} = 1 − e^{−t} for every i ∈ I. Since the thinned sum S′ equals 0 if and only if J_{i}I_{i} equals 0 for all i, i.e., if and only if J_{i} = 0 for the S indices i with I_{i} = 1, the conditional probability ℙ(S′ = 0 | S) = e^{−tS} and thus

ℙ(S′ = 0) = 𝔼 e^{−tS}.

Now, for the thinned family \{I′_{i}\}, μ′ = (1 − e^{−t})μ ≥ (t − \frac{t^{2}}{2} )μ, Δ′ = (1 − e^{−t})^{2}Δ ≤ t^{2}Δ and δ′ = (1 − e^{−t})δ ≤ tδ. Consequently, Theorem 2 yields

𝔼 e^{−tS} = ℙ(S′ = 0) ≤ e^{−μ′+Δ′e^{2δ′}} ≤ e^{−tμ+t^{2}( \frac{1}{2} μ+Δe^{2tδ})},

and thus by Markov’s inequality, for any t ≥ 0,

ℙ(S ≤ aμ) ≤ 𝔼 e^{taμ−tS} ≤ e^{−t(1−a)μ+t^{2}( \frac{1}{2} μ+Δe^{2tδ})}.  (16)

We choose here t = min((1 − a)μ/(4Δ + μ), 1/3δ); then e^{2tδ} ≤ e^{2/3} < 2, and thus

t^{2}(\frac{1}{2}μ + Δe^{2tδ}) ≤ \frac{1}{2}t^{2}(μ + 4Δ) ≤ \frac{1}{2}t(1 − a)μ.

Consequently, (16) yields

ℙ(S ≤ aμ) ≤ e^{−t(1−a)μ/2},

which is the claimed result.

7. Examples

We give three examples showing that the estimates above are of the right order, and that no dramatic improvements are possible in general. We begin with two simple examples.

Example 1 (positive correlations, upper bounds). Let m, n ≥ 1 and 0 < p < 1, and consider mn Be(p) variables consisting of n groups of m variables each, such that different groups are independent while the m variables in each group are identical. Let Γ be the obvious dependency graph consisting of n disjoint copies of the complete graph K_{m}. Then μ = mnp, Δ = \binom{m}{2}np, δ = (m − 1)p, ε = p, and ℙ(S = 0) = (1 − p)^{n}.

Consider first the case m = 2, and thus μ = 2np, Δ = np. Theorem 1 yields

ℙ(S = 0) ≤ exp(np(1 − p)^{−2})(1 − p)^{2n};

the ratio between the right and left hand sides is (for p ≤ 1/2, say)

exp(np(1 − p)^{−2})(1 − p)^{n} = exp(np(1 + 2p + O(p^{2})) − n(p + \frac{1}{2}p^{2} + O(p^{3})))
= exp(\frac{3}{2}np^{2} + O(np^{3})).

Note that the leading terms np in the exponent cancels, which shows that the estimate is quite sharp. Note also that the term ∏_{k∼{i,j}}(1 − p_{k})^{−1} in the exponent in Theorem 1 cannot be eliminated completely; in this example

ℙ(S = 0) > exp(Δ) ∏_{l∈I}(1 − p_{l}).  (17)

Theorem 2 yields the slightly weaker

ℙ(S = 0) ≤ exp(−2np + npe^{2p}) = exp(\frac{5}{2}np^{2} + O(np^{3})) ℙ(S = 0).

The improved bound in Theorem 6 is

exp(np(1 − p)^{−1})(1 − p)^{2n} = exp(\frac{1}{2}np^{2} + O(np^{3})) ℙ(S = 0),

while Theorem 7 in this example yields (for p ≤ 1/2e) the weaker

exp(npφ_{2}(2p))(1 − p)^{2n} = exp(\frac{3}{2}np^{2} + O(np^{3})) ℙ(S = 0).

Let us now consider m ≥ 3. Then Δ ≥ μ, and the bounds in Theorems 1 and 2 are > 1. For any m ≥ 2, and p ≤ 2/3, Theorem 3 yields

ℙ(S = 0) ≤ exp(−μ^{2}/8Δ) = exp(−\frac{m}{4(m − 1)}np),

which for small p is off by a constant factor in the exponent. Theorems 4 and 5 yield similar results with even worse constants in the exponent.

Example 2 (negative correlations, lower bounds). Let m, n ≥ 1 and 0 < p ≤ 1/m, and consider again mn Be(p) variables consisting of n independent groups of m variables each, this time assuming that the m variables in each group are such that never more than one of them equals 1. Then with Γ as in the preceding example, I_{i}I_{j} = 0 whenever i ∼ j, and thus Δ = 0; moreover, μ = mnp, Δ_{0} = \binom{m}{2}np^{2}, δ = (m − 1)p, ε = p, and ℙ(S = 0) = (1 − mp)^{n}.

Theorem 8 yields

ℙ(S = 0) ≥ (1 − \binom{m}{2}np^{2}(1 − p)^{−m})(1 − p)^{mn}

where the ratio between the right and left hand sides is (for mp ≤ 1/2 and nm^{2}p^{2} ≤ 1, say)

exp(−\binom{m}{2}np^{2}(1 + O(mp + nm^{2}p^{2})) − mn(p + \frac{1}{2}p^{2} + O(p^{3}))
+ n(mp + \frac{1}{2}m^{2}p^{2} + O(m^{3}p^{3})))
= exp(O(nm^{3}p^{3} + n^{2}m^{4}p^{4})).

This is quite sharp for small mp provided n is not too large, but fails utterly when nm(m − 1)p^{2} ≥ 2, and thus Δ_{0} ≥ 1.

Theorem 9 yields, for mp ≤ 1/2e,

ℙ(S = 0) ≥ exp(−mnpφ_{2}(mp)) = exp(−mnp − nm^{2}p^{2} + O(nm^{3}p^{3}))
= exp(−\frac{1}{2}nm^{2}p^{2} + O(nm^{3}p^{3})) ℙ(S = 0).

This too is quite sharp when mp is small. It performs better than Theorem 9 when n is large, but is not as good when both mp and nm^{2}p^{2} are small.

Example 3 (negative correlations, lower bound). This more complicated example is due to Shearer [7], to which we refer for further details; it shows that the condition δ + ε ≤ e^{−1} in Theorem 9 is best possible. (We make a minor modification since Shearer only considers the weak version of dependency graphs, cf. Remark 2.) More precisely:

Claim. If a > e^{−1}, then there exists a finite family {I_{i}}_{i∈I} having a dependency graph Γ such that δ + ε < a and ℙ(S = 0) = 0.

Shearer’s construction as is follows. Given a graph Γ and 0 ≤ p ≤ 1, let V be the vertex set of Γ, say that a subset of V is dependent if it contains both endpoints of some edge in Γ (and independent otherwise), and define a signed measure μ_{Γ,p} on 2^{V}, the space of all subsets of V, such that for each A ⊆ V

μ_{Γ,p}\{E ⊆ V : E ⊇ A\} = \begin{cases}p^{|A|} & A is independent, \\ 0 & A is dependent. \end{cases}

It is easily seen that this defines a unique measure μ_{Γ,p}, since μ_{Γ,p}({A}) may be expressed by inclusion-exclusion for every A ⊆ V. μ_{Γ,p} may assume negative values, but if it is a positive measure, i.e. if μ_{Γ,p}({A}) ≥ 0 for every A ⊆ V, then μ_{Γ,p} is a probability measure on 2^{V}, and it is easily seen that with this measure, the indicators I_{i} = 1(i ∈ E), i ∈ V, form a family of random indicator variables with dependency graph Γ; moreover, then p_{i} = 𝔼 I_{i} = p for each i, and 𝔼(I_{i}I_{j}) = 0 whenever i ∼ j.

Let a_{m} = (m + 2)m^{m}/(m + 1)^{m+1}. Then a_{m} → e^{−1} as m → ∞, and we may thus fix m ≥ 1 such that a_{m} < a.

Let b = a/(m + 2) > m^{m}/(m + 1)^{m+1}. Shearer [7] showed that this implies that there exists an m-ary tree G such that μ_{G,b}(∅) < 0. We fix such a G; note that the root of G has degree m, the leaves degree 1 and all other vertices degree m + 1.

On the other hand, it is easily seen that if p is small enough, then μ_{G,p} is a probability measure. (Indeed, if p ≤ m^{m}/(m + 1)^{m+1}, there is a simple probabilistic construction of μ_{G,p}: Add external edges to the root and leaves of G such that every vertex has m + 1 edges, 1 going ‘down’ and m going ‘up’; colour all edges black or white independently at random with ℙ(white) = q, where q(1 − q)^{m} = p; define I_{i} = 1 if the edge going down from vertex i is white and the m edges going up are black.)

By continuity of p ↦ min{μ_{G,p}({A}) : A ⊆ V is independent}, and the fact that μ_{G,p}({A}) = 0 whenever A is dependent, it follows that for some p with 0 < p < b we have μ_{G,p}({A}) ≥ 0 for each A, and thus μ_{G,p} is a probability measure, but μ_{G,p}({A}) = 0 for at least one independent set A.

Fix such p and A, and let Γ be the (induced) subgraph of G obtained by deleting all vertices in A together with all their neighbours. (In fact, it seems likely that A = ∅, and thus Γ = G, but we have not verified this.) By a simple calculation [7], for every B ⊆ V (Γ), μ_{Γ,p}({B}) = μ_{G,p}({A ∪ B})/p^{|A|}; thus μ_{Γ,p} is a probability measure with μ_{Γ,p}(∅) = 0.

Let the indicators I_{i} be defined as above. For this family of indicators then ℙ(S = 0) = μ_{Γ,p}(∅) = 0 and δ + ε ≤ (m + 1)p + p < (m + 2)b = a, which verifies the claim.

8. Discussion

We may compare the upper bounds given in this paper with the results previously obtained in the special case when the indicators I_{i} all are of the type ∏_{j∈Q_{i}} J_{j}, where {J_{j}}_{j∈Q} is a family of independent indicator variables and the Q_{i} are (arbitrary) subsets of the index set Q. In this case, using our notation, [4, 3] give the bounds

ℙ(S = 0) ≤ exp(−μ + Δ)  (18)

and

ℙ(S = 0) ≤ exp(−μ^{2}/(2Δ + μ));  (19)

Boppana and Spencer [2, 1] give, using a different proof and under somewhat more general conditions,

ℙ(S = 0) ≤ exp(Δ/(1 − ε)) ∏_{i∈I}(1 − p_{i}) ≤ exp(−μ + Δ/(1 − ε)).  (20)

(Alon and Spencer [1] also give, under the same conditions and provided 2Δ ≥ μ(1 − ε), the bound exp(−μ^{2}(1 − ε)/4Δ); this is similar to but larger than the bound in (19).)

The bounds given here in Section 3 (for a much more general situation) are of a similar nature, but somewhat larger. The main difference is that δ plays no role in the bounds in the special case; for example, the bound in Theorem 2 differs from (18) only by the factor e^{2δ} multiplying Δ.

Furthermore, the constants in the exponent in the bounds in Theorems 3–5 are not as good as in (19) for the special case.

Example 1 shows that the Δ in the exponent in Theorem 2 and (18) is quite sharp; for example, it cannot in general be multiplied by a constant less than 1. However, we do not know whether the factor e^{2δ} multiplying Δ in Theorem 2 really is needed. As remarked above, the incomparable estimates in Theorems 6 and 7, which represent two different attempts to reduce this factor, suggest that none of the these results is the best possible. Indeed, it seems possible that the result (18) known for the special case above holds generally. (Recall, however, from Example 1 that the corresponding factor ∏_{k∼{i,j}}(1 − p_{k})^{−1} in Theorem 1 cannot be completely eliminated, see (17). Similarly, by the same example, the factor 1/(1 − ε) cannot be removed from the first bound in (20).)

Similarly, there seems to be room for improvements of the constants in Theorems 3–5. Example 1 shows that the best one could hope for is something like (19); for example, the constants in front of Δ and μ there are the best possible.

This leads to the following open problem.

Problem 1. Do (18), (19) and (20) hold under the assumptions of this paper?

There are also other questions suggested by the results above.

Problem 2. [3] gives a tail estimate similar to Theorem 10, but also a corresponding lower bound. Is there similar lower bound under the conditions of the present paper?

As remarked in Remark 2, the Lovász local lemma (and our Theorem 9) requires only a weaker version of our condition that Γ is a dependency graph.

Problem 3. Do the results of this paper hold if Γ only is assumed to be a dependency graph in the weaker sense?

References

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

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

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

[4] 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.

[5] L.M. Kirousis, E. Kranakis, D. Krizanc & Y.C. Stamatiou, Approximating the unsatisfiability threshold of random formulas. To appear.

[6] J. Spencer, personal communication, Poznań 1997.

[7] J. Shearer, On a problem of Spencer. Combinatorica 5 (1985), 241–245.

[8] 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.

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

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