LARGE DEVIATIONS FOR SUMS OF PARTLY DEPENDENT RANDOM VARIABLES

SVANTE JANSON

Abstract. We use and extend a method by Hoeffding to obtain strong large deviation bounds for sums of dependent random variables with suitable dependency structure. The method is based on breaking up the sum into sums of independent variables. Applications are given to U-statistics, random strings and random graphs.

1. Introduction

Many random variables can be written as a sum

X = ∑_{α∈A} Y_{α}.  (1.1)

of simpler random variables Y_{α}, with α ranging over some index set. For example, each Y_{α} may be an indicator variable taking the values 0 and 1 only, i.e. Y_{α} ∼ Be(p_{α}) for some p_{α} ∈ [0, 1].

We are interested in situations where the variables Y_{α} may be dependent, but there is a large amount of independence among them. A typical situation is the sum

X = ∑_{(i_{1},...,i_{d})∈A} f_{i_{1}···i_{d}}(ξ_{i_{1}}, …, ξ_{i_{d}}),  (1.2)

for some functions f_{i_{1}···i_{d}} and independent random variables ξ_{1}, …, ξ_{n}, and some set A ⊆ [n]_{<}^{d}, where [n]_{<}^{d} is the set of all d-tuples (i_{1}, …, i_{d}) with 1 ≤ i_{1} < ⋯ < i_{d} ≤ n. Here d and n are some positive integers; typically d is small (perhaps only 2 or 3) and n is large.

One example of such sums (1.2) is the family of U-statistics [13], which is the symmetric case obtained by taking ξ_{1}, …, ξ_{n} i.i.d., all f_{i_{1}···i_{d}} equal to some symmetric function f, and A = [n]_{<}^{d}. More generally, if we in this situation sum over a subset A ⊂ [n]_{<}^{d}, we obtain an incomplete U-statistic. Also twosample U-statistics are of the general type (1.2), but now the ξ_{i} are of two different types.

Another example of (1.2), now with a non-symmetric f, is the problem on random strings described in Example 4.2; this problem was the direct motivation to write this paper. Further examples, for random graphs and hypergraphs, are also given in Section 4.

The purpose of this paper is to prove small bounds for the probability of large deviations of a variable (1.1). Such bounds have a long history. In the case of independent summands, some of the most important contributions are Bernstein [4], Cramér [9], Feller [10], Chernoff [8], Okamoto [19], Bennett [3], and Hoeffding [14]. For dependent summands, there are many results proved by many authors using different methods under various assumptions; for a few of these, see the surveys in [16] and [18].

Date: September 19, 2002; updated October 9, 2003.

The present paper is based on Hoeffding [14], which besides the independent case also studies several dependent cases, among them U-statistics. Hoeffding’s method for this case is based on breaking up the sum (1.2) into several parts, each part being a sum of independent variables. The same idea has been used in a somewhat different form (see Remark 5.2) by, among others, [21], [18], [20]. We will show how Hoeffding’s original method, with only minor modifications, extends to general sums (1.2) and (1.1).

The main results are stated in Section 2, proved in Section 3 and applied in Section 4. Section 5 contains some further remarks.

Acknowledgements. I thank Wojtek Szpankowski for stimulating discussions that led to this research. Part of the research was carried out at the Newton Institute in Cambridge. I thank Ravi Kannan, Andrzej Ruciński and Peter Winkler for helpful comments.

2. Results

Definitions. Given A and {Y_{α}}, α ∈ A, we make the following definitions. • A subset A′ of A is independent if the corresponding random variables {Y_{α}}_{α∈A′}, are independent.

• A family {A_{j}}_{j} of subsets of A is a cover of A if ⋃_{j} A_{j} = A.

• A family {(A_{j}, w_{j})}_{j} of pairs (A_{j}, w_{j}), where A_{j} ⊆ A and w_{j} ∈ [0, 1] is a fractional cover of A if ∑_{j} w_{j}1_{A_{j}} ≥ 1_{A}, i.e. ∑_{j:α∈A_{j}} w_{j} ≥ 1 for each α ∈ A.

• A (fractional) cover is proper if each set A_{j} in it is independent.

• χ(A) is the size of the smallest proper cover of A, i.e. the smallest m such that A is the union of m independent subsets.

• χ^{∗}(A) is the minimum of ∑_{j} w_{j} over all proper fractional covers {(A_{j}, w_{j})}_{j}.

Note that, in spite of our notation, χ(A) and χ^{∗}(A) depend not only on A but also on the family {Y_{α}}_{α∈A}.

A cover can be regarded as a fractional cover with every w_{j} = 1. Hence

χ^{∗}(A) ≤ χ(A).  (2.1)

We can thus replace χ^{∗}(A) by χ(A) in all results below, and the reader that prefers it may consider only covers and ignore the fractional ones.

Note further that χ^{∗}(A) ≥ 1 (unless A = ∅) and that χ^{∗}(A) = 1 if and only if the variables Y_{α}, α ∈ A, are independent. It is often convenient to consider a dependency graph for {Y_{α}}. This is a graph Γ with vertex set A such that if B ⊂ A and α ∈ A is not connected by an edge to any vertex in B, then Y_{α} is independent of {Y_{β}}_{β∈B}. A typical example is for sums of type (1.2), where A ⊆ [n]_{<}^{d}; we define Γ to have an edge between every pair of d-tuples α, β ∈ [n]_{<}^{d} such that α and β have an index in common. (See further Remark 5.3 and the examples in Section 4.) It follows that a subset of A that is independent in Γ in the graph theory sense (no edges inside the subset) is independent in the sense above. (The converse is not necessarily true, see Remark 5.3.) Hence, χ(A) ≤ χ(Γ) and χ^{∗}(A) ≤ χ^{∗}(Γ), where χ(Γ) and χ^{∗}(Γ) are the usual chromatic and fractional chromatic numbers of Γ.

We further let Δ(Γ) denote the maximum degree of Γ and let (for convenience) Δ_{1}(Γ) := Δ(Γ) + 1. It is well-known (and easily seen by a greedy colouring) that χ(Γ) ≤ Δ_{1}(Γ), see e.g. [6]. When Γ is a dependency graph for {Y_{α}}, we thus have

χ^{∗}(A) ≤ χ^{∗}(Γ) ≤ χ(Γ) ≤ Δ_{1}(Γ),  (2.2)

so χ^{∗}(A) can be replaced by any of χ^{∗}(Γ), χ(Γ), Δ_{1}(Γ) in our results; in many applications this causes no significant loss.

We now can state our main results. The first extends [14, Theorem 2], which is the case χ^{∗}(A) = 1 (i.e. independent variables).

Theorem 2.1. Suppose that X is as in (1.1) with a_{α} ≤ Y_{α} ≤ b_{α} for every α ∈ A and some real numbers a_{α} and b_{α}. Then, for t > 0,

ℙ(X ≥ 𝔼 X + t) ≤ exp(−2\frac{t^{2}}{χ^{∗}(A) ∑_{α∈A}(b_{α} − a_{α})^{2}} ).

The same estimate holds for ℙ(X ≤ 𝔼 X − t).

Corollary 2.2. Suppose that X is as in (1.1) with Y_{α} ∼ Be(p_{α}) for some p_{α} ∈ (0, 1) and all α ∈ A. Then, for t ≥ 0,

ℙ(X ≥ 𝔼 X + t) ≤ exp(−2\frac{t^{2}}{χ^{∗}(A)|A|}).

The same estimate holds for ℙ(X ≤ 𝔼 X − t). □

These results, while useful in many situations, can be improved (again by Hoeffding’s methods) when the summands have variances that are substantially smaller than the upper bound (b_{α} − a_{α})^{2}/4. Note that we assume a one-sided bound on Y_{α} in Theorem 2.3 (and Theorem 2.5) below; as in Theorem 2.3 the obtained estimate holds for ℙ(X ≤ 𝔼 X − t) too (by considering −X), but only if the boundedness assumption is reversed to Y_{α} − 𝔼 Y_{α} ≥ −b. We define

φ(x) := (1 + x) ln(1 + x) − x.  (2.3)

Theorem 2.3. Suppose that X is as in (1.1) with Y_{α} − 𝔼 Y_{α} ≤ b for some b > 0 and all α ∈ A. Then, with φ(x) as in (2.3) and S := ∑_{α∈A} Var Y_{α}, for t ≥ 0,

ℙ(X ≥ 𝔼 X + t) ≤ exp(−\frac{S}{b^{2}χ^{∗}(A)}φ(\frac{4bt}{5S})) ≤ exp(−\frac{8t^{2}}{25χ^{∗}(A)(S + bt/3)}).

Corollary 2.4. Suppose that X is as in (1.1) with Y_{α} ∼ Be(p) for some p ∈ (0, 1) and all α ∈ A. Let N := |A|. Then, for t ≥ 0,

ℙ(X ≥ 𝔼 X + t) ≤ exp(−\frac{Np}{(1 − p)χ^{∗}(A)}φ(\frac{4t}{5Np}))  (2.4)
≤ exp(−\frac{8t^{2}}{25χ^{∗}(A)(Np + t/3)});  (2.5)
ℙ(X ≤ 𝔼 X − t) ≤ exp(−\frac{N(1 − p)}{pχ^{∗}(A)}φ(\frac{4t}{5N(1 − p)}));  (2.6)
ℙ(X ≤ 𝔼 X − t) ≤ exp(−\frac{8t^{2}}{25χ^{∗}(A)Np}).  (2.7)

If we are given a dependency graph Γ, we may by (2.2) replace χ^{∗}(A) by Δ_{1}(Γ). Actually, with Δ_{1}, which is often convenient for applications, we may improve the bounds a little as follows in the important case when all Y_{α} have the same distribution. (The improvement amounts typically to a factor ≈ 25/16 in the exponent. For many applications this is irrelevant.)

Theorem 2.5. Suppose that X is as in (1.1) and that all Y_{α} have the same distribution with Y_{α} − 𝔼 Y_{α} ≤ b for some b > 0. Suppose further that Γ is a dependency graph for {Y_{α}}_{α∈A}. Let N := |A|, S := N Var Y_{α} and Δ_{1} := Δ_{1}(Γ). Then, with φ(x) as in (2.3), for t ≥ 0,

ℙ(X ≥ 𝔼 X + t) ≤ exp(−\frac{S}{b^{2}Δ_{1}} φ(\frac{bt}{S(1 + Δ_{1}/8N)}))

≤ exp(−\frac{t^{2}(1 − Δ_{1}/4N)}{2Δ_{1}(S + bt/3)}).

Corollary 2.6. Under the assumptions of Corollary 2.4, and with Δ_{1} = Δ_{1}(Γ), where Γ is a dependency graph for {Y_{α}}, for t ≥ 0,

ℙ(X ≥ 𝔼 X + t) ≤ exp(−\frac{Np}{(1 − p)Δ_{1}} φ(\frac{t}{(N + Δ_{1}/8)p}))  (2.8)
≤ exp(−\frac{t^{2}(1 − Δ_{1}/4N)}{2Δ_{1}(Np + t/3)(1 − p)});  (2.9)
ℙ(X ≤ 𝔼 X − t) ≤ exp(−\frac{N(1 − p)}{Δ_{1}p}φ(\frac{t}{(N + Δ_{1}/8)(1 − p)}));  (2.10)
ℙ(X ≤ 𝔼 X − t) ≤ exp(−\frac{t^{2}(1 − Δ_{1}/4N)}{2Δ_{1}Np}).  (2.11)

3. Proofs

The reader is advised to first consider the case of covers only (every w_{i} = 1) for simplicity.

We say that a fractional cover {(A_{j}, w_{j})}_{j} is exact if ∑_{j} w_{j}1_{A_{j}} = 1_{A}.

Lemma 3.1. If {(A_{j}, w_{j})}_{j} is an exact fractional cover of A, and x_{α}, α ∈ A, are any numbers, then

∑_{α∈A} x_{α} = ∑_{j} w_{j}s_{j},

where s_{j} := ∑_{α∈A_{j}} x_{α}. In particular, |A| = ∑_{j} w_{j}|A_{j}|.

Proof.

∑_{j} w_{j}s_{j} = ∑_{j} w_{j} ∑_{α∈A} 1_{A_{j}}(α)x_{α} = ∑_{α∈A} ∑_{j} w_{j}1_{A_{j}}(α)x_{α} = ∑_{α∈A} x_{α}.

The final claim follows by taking each x_{α} = 1. □

The following simple lemma will enable us to consider only exact (fractional) covers, which will simplify proofs. In particular, it implies that χ^{∗} is the minimum of ∑_{j} w_{j} over all exact proper fractional covers.

Lemma 3.2. If {(A_{j}, w_{j})}_{j} is a fractional cover, we can replace each (A_{j}, w_{j}) by one or several (A_{jk}, w_{jk}) with A_{jk} ⊆ A_{j} and ∑_{k} w_{jk} = w_{j} such that {(A_{jk}, w_{jk})}_{jk} is an exact fractional cover.

Proof. Take an element α ∈ A. It is easily seen that {(A_{j}, w_{j})}_{j} can be replaced by a family {(A_{jk}, w_{jk})}_{jk} with each A_{jk} = A_{j} or A_{j} \ {α}, ∑_{k} w_{jk} = w_{j}, and ∑ w_{jk}1_{A_{jk}}(α) = 1. Repeat the same procedure for each α ∈ A. □

Proof of Theorem 2.1. We follow the method of Hoeffding [14]. Subtracting the means, we may assume that 𝔼 Y_{α} = 0 for all α, and thus 𝔼 X = 0. Then, by [14, (4.16)], for every real h,

𝔼 exp(hY_{α}) ≤ exp(\frac{1}{8}h^{2}(b_{α} − a_{α})^{2}).  (3.1)

Let {(A_{j}, w_{j})}_{j} be an exact proper fractional cover of A, and let X_{j} := ∑_{A_{j}} Y_{α}. Then X = ∑_{j} w_{j}X_{j} by Lemma 3.1. Let p_{j} be any positive numbers with ∑_{j} p_{j} = 1. By Jensen’s inequality, for any real u,

exp(uX) = exp(∑_{j} p_{j} \frac{uw_{j}}{p_{j}} X_{j}) ≤ ∑_{j} p_{j} exp(\frac{uw_{j}}{p_{j}} X_{j}).

Taking the expectations we find using (3.1), since X_{j} is a sum of independent variables Y_{α}, α ∈ A_{j},

𝔼 exp(uX) ≤ ∑_{j} p_{j} 𝔼 exp(\frac{uw_{j}}{p_{j}} X_{j}) = ∑_{j} p_{j} ∏_{α∈A_{j}} 𝔼 exp(\frac{w_{j}u}{p_{j}}Y_{α})

≤ ∑_{j} p_{j} ∏_{α∈A_{j}} exp(\frac{w_{j}^{2}u^{2}}{8p_{j}^{2}} (b_{α} − a_{α})^{2}) = ∑_{j} p_{j} exp(\frac{w_{j}^{2}u^{2}c_{j}}{8p_{j}^{2}} ), (3.2)

where c_{j} := ∑_{α∈A_{j}}(b_{α} − a_{α})^{2}. We choose p_{j} = w_{j}c_{j}^{1/2}/T with T := ∑_{j} w_{j}c_{j}^{1/2}, and find

𝔼 exp(uX) ≤ exp(\frac{1}{8}T^{2}u^{2}), u ∈ ℝ.

Hence, for u ≥ 0,

ℙ(X ≥ t) ≤ e^{−ut} 𝔼 e^{uX} ≤ exp(\frac{1}{8}T^{2}u^{2} − ut),

and the optimal choice u := 4t/T^{2} yields

ℙ(X ≥ t) ≤ exp(−2t^{2}/T^{2}).  (3.3)

By the Cauchy–Schwarz inequality and Lemma 3.1,

T^{2} = (∑_{j} w_{j}c_{j}^{1/2})^{2} ≤ ∑_{j} w_{j} · ∑_{j} w_{j}c_{j} = ∑_{j} w_{j} · ∑_{α∈A}(b_{α} − a_{α})^{2}

and the result follows from (3.3) by choosing {(A_{j}, w_{j})}_{j} with ∑_{j} w_{j} = χ^{∗}(A). The result for ℙ(X ≤ 𝔼 X − t) follows by considering −X. □

Remark 3.3. In some cases (when the Cauchy–Schwarz inequality above is far from sharp), (3.3) may be substantially better than the theorem.

We will derive Theorems 2.3 and 2.5 from the following more technical estimate.

Theorem 3.4. Suppose that X is as in (1.1) with Y_{α} − 𝔼 Y_{α} ≤ b for some b > 0 and all α ∈ A. Suppose further that {(A_{j}, w_{j})}_{j} is a proper fractional cover of A. Let S := ∑_{α∈A} Var Y_{α} and σ_{j}^{2} := ∑_{α∈A_{j}} Var Y_{α}. Then, with φ(x) as in (2.3),

ℙ(X ≥ 𝔼 X + t) ≤ exp(−\frac{S}{b^{2}W} φ(\frac{btW}{US} )),  t ≥ 0,  (3.4)

where W := ∑_{j} w_{j} and

U := ∑_{j} w_{j} max(1, \frac{σ_{j}W^{1/2}}{S^{1/2}} ).  (3.5)

Proof. This is similar to the proof of Theorem 2.1, but we use a (usually) sharper estimate than (3.1).

We may by Lemma 3.2 assume that the fractional cover {(A_{j}, w_{j})}_{j} is exact; note that the modification in Lemma 3.2 preserves W and preserves or decreases U. We may further assume that b = 1 and, for each α, 𝔼 Y_{α} = 0; the general case follows by replacing Y_{α} by (Y_{α} − 𝔼 Y_{α})/b. We thus have 𝔼 Y_{α} = 0 and Y_{α} ≤ 1 for all α. Hence, with σ_{α}^{2} := Var Y_{α}, by [3, p. 42], see also [14, Lemma 2],

𝔼 exp(hY_{α}) ≤ \frac{1}{1 + σ_{α}^{2}} e^{−hσ_{α}^{2}} + \frac{σ_{α}^{2}}{1 + σ_{α}^{2}} e^{h},  h ≥ 0.  (3.6)

We rewrite this as

𝔼 exp(hY_{α}) ≤ exp(f(σ_{α}^{2}; h)), h ≥ 0,

where

f(s; h) := ln(\frac{1}{1 + s}e^{−hs} + \frac{s}{1 + s}e^{h}).

It is proved in [14, Lemma 3 and p. 24] that f is a concave function of s ≥ 0 with f(0) = 0, and thus

f(s; h) ≤ sg(h), s ≥ 0,

where

g(h) := \frac{∂}{∂s}f(0; h) = e^{h} − 1 − h.

Consequently,

𝔼 exp(hY_{α}) ≤ exp(σ_{α}^{2}g(h)), h ≥ 0. (3.7)

As in (3.2), for any u ≥ 0 and positive numbers p_{j} with ∑_{j} p_{j} = 1, now using (3.7),

𝔼 exp(uX) ≤ ∑_{j} p_{j} ∏_{α∈A_{j}} 𝔼 exp(\frac{w_{j}u}{p_{j}}Y_{α})

≤ ∑_{j} p_{j} ∏_{α∈A_{j}} exp(σ_{α}^{2}g(\frac{w_{j}u}{p_{j}})) = ∑_{j} p_{j} exp(σ_{j}^{2}g(\frac{w_{j}u}{p_{j}})). (3.8)

Choose this time p_{j} := w_{j} max(1, \frac{σ_{j}W^{1/2}}{S^{1/2}} )/U, cf. (3.5). If σ_{j}^{2} ≤ S/W, then p_{j} = w_{j}/U and

σ_{j}^{2}g(\frac{uw_{j}}{p_{j}} ) ≤ \frac{S}{W} g(uU).  (3.9)

If σ_{j}^{2} ≥ S/W, then p_{j} = w_{j}σ_{j}W^{1/2}/(S^{1/2}U) and

σ_{j}^{2}g(\frac{uw_{j}}{p_{j}} ) = σ_{j}^{2}g(\frac{uS^{1/2}U}{σ_{j}W^{1/2}} ) ≤ σ_{j}^{2} \frac{S}{σ_{j}^{2}W} g(uU),

because g(0) = g′(0) = 0 and g′′ is increasing, and thus x ↦ g(x)/x^{2} is increasing. Hence, (3.9) holds in this case too, and (3.8) yields

𝔼 exp(uX) ≤ exp(\frac{S}{W} g(uU)),  u ≥ 0.  (3.10)

Hence,

ℙ(X ≥ 𝔼 X + t) ≤ exp(\frac{S}{W} g(uU) − ut),  u ≥ 0.  (3.11)

We optimize by choosing u = U^{−1} ln(1 + tW/SU), which yields (3.4). □

To prove Theorems 2.3 and 2.5, it remains to estimate W and U for suitable proper fractional covers.

Proof of Theorem 2.3. By the inequality y ≤ 1 + y^{2}/4 and Lemma 3.1, we always have

U ≤ ∑_{j} w_{j}(1 + \frac{σ_{j}^{2}W}{4S} ) = ∑_{j} w_{j} + ∑_{j} w_{j}σ_{j}^{2} \frac{W}{4S} = W + S \frac{W}{4S} = \frac{5}{4}W.

The first inequality in Theorem 2.3 now follows from Theorem 3.4 if we choose an optimal proper fractional cover {(A_{j}, w_{j})}_{j} such that W = χ^{∗}(A).

The second inequality follows by the elementary inequality

φ(x) ≥ \frac{x^{2}}{2(1 + x/3)},  x ≥ 0,  (3.12)

see e.g. [3] or [16, proof of Theorem 2.1]. □

Proof of Corollary 2.4. For (2.4)–(2.5), apply Theorem 2.3 with b = 1 − p and S = Np(1 − p).

For (2.6), replace Y_{α} by 1 − Y_{α} and apply (2.4).

Finally, (2.7) is trivial for t > 𝔼 X = Np, and for t ≤ Np it follows from (2.6) and (3.12), using (1 − p)(1 + 4t/15N(1 − p)) ≤ 1 − p + t/N ≤ 1. □

Proof of Theorem 2.5. For Theorem 2.5, we use instead the Hajnal–Szemerédi Theorem [12], [5], which says that A can be partitioned into Δ_{1} independent sets, each of size equal to either ⌈|A|/Δ_{1}⌉ or ⌊|A|/Δ_{1}⌋. We use these sets as our A_{j}, with all weights w_{j} = 1. If N = kΔ_{1} + l, with k and l integers and 0 ≤ l < Δ_{1}, there are necessarily Δ_{1} − l sets of size k and l of size k + 1, and thus W = Δ_{1} and, by (3.5),

U = Δ_{1} − l + l(\frac{(k + 1)Δ_{1}}{N} )^{1/2} = Δ_{1} + l(\sqrt{1 + \frac{Δ_{1} − l}{N}} − 1)

≤ Δ_{1} + \frac{l(Δ_{1} − l)}{2N} ≤ Δ_{1}(1 + \frac{Δ_{1}}{8N} ).

The result follows from Theorem 3.4 and (3.12). □

Proof of Corollary 2.6. This follows from Theorem 2.5 by the arguments for Corollary 2.4. □

Remark 3.5. The idea to use the Hajnal–Szemerédi Theorem in this context is due to Ruciński [16, 18] and Pemmaraju [20] (independently). Pemmaraju [20] further explores the possibility of improving the bound by finding by other means, for specific Γ, a partition of Γ into fewer than Δ_{1} independent sets of (almost) the same size. Note that such arguments can beat our general bound in Theorem 2.3 by at most a factor 25/16 in the exponent. Indeed, the proof of Theorem 2.3 uses the general estimate U/W ≤ 5/4 proved above, while Theorem 2.5 and [20] exploits better estimates of U/W in special situations; however, U/W ≥ 1 by (3.5), so the room for improvement is limited.

4. Examples

Example 4.1 (U-statistics). Consider a sum

X = ∑_{1≤i_{1}<···<i_{d}≤n} f_{i_{1}···i_{d}}(ξ_{i_{1}}, …, ξ_{i_{d}})  (4.1)

where ξ_{1}, …, ξ_{n} are independent random variables. This is the special case of (1.2) with A = [n]_{<}^{d}, and includes U-statistics.

We define, as in Section 2, a dependency graph Γ with vertex set [n]_{<}^{d} by declaring that α and β are joined by an edge if α ∩ β ≠ ∅ (regarding the d-tuples α and β as sets).

Let k := ⌊n/d⌋. Let A_{1}, …, A_{M} be a listing of all families of k disjoint d-tuples in A = [n]_{<}^{d}. By symmetry, ∑_{j=1}^{M} 1_{A_{j}} = Mk|A|^{−1}1_{A}, and thus we have ∑_{j} w_{j}1_{A_{j}} = 1_{A} with w_{j} = |A|/(Mk) for all j. Hence,

χ^{∗}(A) ≤ χ^{∗}(Γ) ≤ \frac{|A|}{k} = \frac{\binom{n}{d}}{⌊n/d⌋}.  (4.2)

Consequently, Theorem 2.1 shows that if a ≤ f_{i_{1}···i_{d}}(ξ_{i_{1}}, …, ξ_{i_{d}}) ≤ b for every i_{1}, …, i_{d} and two real numbers a and b, then, for t > 0,

ℙ(X ≥ 𝔼 X + t\binom{n}{d}) ≤ exp(−2 ⌊\frac{n}{d}⌋ t^{2}/(b − a)^{2}).  (4.3)

This estimate is due to Hoeffding [14, (5.7)]. (Hoeffding treated U-statistics only; his proof extends to the more general non-symmetric version here.) We have the same estimate for ℙ(X ≤ 𝔼 X − t\binom{n}{d}).

Since d⌊n/d⌋ ≥ n − d + 1, we obtain from (4.2) also

χ^{∗}(A) ≤ \binom{n}{d − 1}  (4.4)

which leads to a slight weakening of (4.3) that may look simpler:

ℙ(X ≥ 𝔼 X + tn^{d−1/2}) ≤ exp(−2\frac{d! (d − 1)!}{(b − a)^{2}}t^{2}).  (4.5)

In many cases, Theorem 2.3 or Corollary 2.4 yields better results. For example, if ξ_{1}, …, ξ_{n} are identically distributed and f_{i_{1}···i_{d}} = f does not depend on i_{1}, …, i_{d} and take the values 0 and 1 only, then Corollary 2.4 yields, with p := ℙ(f(ξ_{1}, …, ξ_{d}) = 1),

ℙ(X ≥ 𝔼 X + t) ≤ exp(−\frac{8t^{2}}{25\binom{n}{d−1}(\binom{n}{d}p + t/3)});  (4.6)

ℙ(X ≤ 𝔼 X − t) ≤ exp(−\frac{8t^{2}}{25\binom{n}{d−1}\binom{n}{d}p}).  (4.7)

These are better than (4.3) and (4.5) when p < 0.16 and (for (4.6)) t is not too large.

In this case, Theorem 2.5 and its corollary are somewhat weaker. We have

Δ(Γ) ≤ d\binom{n − 1}{d − 1},

and this estimate is asymptotically sharp. Together with (4.4), we thus see that we lose about a factor d in the exponent by using Δ_{1} instead of χ^{∗}(A), which outweighs the gain of a factor 25/16 in Theorem 2.5 compared to Theorem 2.3.

If we have a sparse sum as in (1.2), for example an incomplete U-statistic, we can get better estimates provided we have a reasonable estimate of χ^{∗}(A) or Δ(A).

Some other large deviation bounds for U-statistics are given in [1], [2], [7].

Example 4.2 (Patterns in a random string). Let ξ_{1}, …, ξ_{n} be i.i.d. random letters from a finite alphabet A, and let w be a given word of length d. Flajolet et al. [11] studied the number of subsequences ξ_{i_{1}} ⋯ ξ_{i_{d}} that equal w. This is a random variable of the form (4.1), with f(x_{1}, …, x_{d}) = 1 if x_{1} ⋯ x_{d} = w and 0 otherwise. Hence all bounds in Example 4.1 apply, with b − a = 1 and p = ℙ(ξ_{1} ⋯ ξ_{d} = w) = ∏_{i=1}^{d} p_{w_{i}}, where w_{i} is the i:th letter of w and p_{x} := ℙ(ξ_{1} = x). In particular, (4.5) (Theorem 2.1) yields the bound

ℙ(|X − 𝔼 X| ≥ tn^{d−1/2}) < 2 exp(−2d!(d − 1)! t^{2}).

For p small, better results are given by (4.6) and (4.7) (Corollary 2.4).

Flajolet et al. [11] further studied the number of such subsequences with the constraints i_{j+1} − i_{j} ≤ ℓ_{j} on the gaps of the sequence, where ℓ_{1}, …, ℓ_{d−1} are given numbers (possibly ∞). This is a random variable of the type (1.2), so the results above apply. We now have

A = {(i_{1}, …, i_{d}) ∈ [n]_{<}^{d} : 0 < i_{j+1} − i_{j} ≤ ℓ_{j} for j = 1, …, d − 1}.

Let F := {i : ℓ_{i} < ∞} and set b := d − |F| = 1 + |{i : ℓ_{i} = ∞}| and D := ∏_{i∈F} ℓ_{i}. Consider ℓ_{j} as fixed and let n → ∞. Then |A| = \binom{n}{b}D(1 + O(1/n)), see [11]. Moreover, given any i_{k}, the gaps i_{j+1} − i_{j} may be chosen in at most D ways for j ∈ F and in at most \binom{n}{b−1} ways for j ∉ F. Since any given d-tuple α ∈ A has d indices, and any of these may be in (at most) d positions in another d-tuple, it follows that, with the dependency graph Γ defined as in Example 4.1,

Δ_{1}(Γ) ≤ d^{2}D\binom{n}{b − 1} ≤ \frac{d^{2}D}{(b − 1)!}n^{b−1}.  (4.8)

We thus obtain from Corollary 2.6, for all t > 0,

ℙ(X ≥ 𝔼 X + t) ≤ exp(−\frac{(b − 1)! b!}{2d^{2}D^{2}p} · \frac{t^{2}}{n^{2b−1}} (1 + O(\frac{1}{n} + \frac{t}{n^{b}p})))
ℙ(X ≤ 𝔼 X − t) ≤ exp(−\frac{(b − 1)! b!}{2d^{2}D^{2}p} · \frac{t^{2}}{n^{2b−1}} (1 + O(\frac{1}{n}))).

Since Var(X) is of the order n^{2b−1} [11], these estimates are of the subgaussian type exp(−ct^{2}/ Var(X)), at least for t not too large.

Example 4.3 (Random graphs). The random graph G(n, p) consists of n (labelled) vertices and edges drawn randomly, with each possible edge appearing with probability p, independently of all other edges.

Let X be the number of triangles in G(n, p). This can be written in the form (1.1), where A = [n]_{<}^{3} and Y_{α} is the indicator that the three edges between the three vertices in α all are present in G(n, p). (Note that this is not of the form (1.2), since the underlying independent variables are indexed by pairs ij of vertices rather than vertices. X can be regarded as an incomplete U-statistic based on the \binom{n}{2} edge indicators; this will lead to the same results.)

In this case, two variables Y_{α} and Y_{β} are independent even if α and β have one vertex (but not two) in common, and we can define an independence graph Γ with vertex set A such that α and β are joined by an edge if |α ∩ β| = 2. This means fewer edges that in the independence graph in Example 4.1 (for d = 3), and thus smaller Δ_{1} and χ^{∗}, and better estimates.

We have 𝔼 Y_{α} = ℙ(Y_{α} = 1) = p^{3}, |A| = \binom{n}{3} and Δ(Γ) = 3(n − 3), whence Δ_{1}(Γ) = 3n − 8 < 3n. It follows from Corollary 2.6 that, for ε > 0,

ℙ(X ≥ (1 + ε) 𝔼 X) ≤ exp(−\frac{ε^{2}}{36 + 12ε}n^{2}p^{3}(1 + O(1/n)))  (4.9)
ℙ(X ≤ (1 − ε) 𝔼 X) ≤ exp(−\frac{ε^{2}}{36}n^{2}p^{3}(1 + O(1/n))).  (4.10)

If p is not too small, these exponential bounds are rather good. However, for p < n^{−2/3}, they are pretty useless. Also for larger p, they are not sharp (unless p is bounded away from 0). Indeed, for this problem the following is known by other methods, assuming for simplicity that n → ∞ and that p → 0 and np ≥ 1.

As is shown in [15], [16, Chapter 3], the sharp exponent in the lower tail estimate (4.10) is, for any fixed ε ≤ 1, really of the order min(n^{3}p^{3}, n^{2}p).

For the upper tail (4.9), the sharp exponent is of the order n^{2}p^{2} (possibly up to a factor log n) for any fixed ε ≥ 0, see [17]. See also partial results and discussions in [22] and [18]; the present method is essential the same as “Break-up” in the latter. (It is a slight improvement, see Remark 5.2.)

We have here for simplicity discussed the number of triangles. Similar results hold for the number of copies of any fixed graph in G(n, p). Again, Corollary 2.6 gives estimates that are exponentially small for certain ranges of p, but we do not obtain optimal results (except in some extreme cases). Cf. [15], [16], [22], [18], [17].

Example 4.4 (Random hypergraphs). Another problem that was used in [18] to compare several different methods was the following: Consider a fixed hypergraph H, for simplicity assumed to be uniform (all hyperedges have the same number of vertices). Delete vertices of H at random, keeping each vertex with probability p, independently of the other vertex, and let X be the number of surviving hyperedges.

As shown in [18] (“Break-up” in Section 3.2), we typically obtain reasonable estimates by the methods of this paper. In some cases, these are the best that we can prove, but in others they are surpassed by other methods.

5. Further remarks

Remark 5.1. The method presented here uses independence of suitable (large) subsets of {Y_{α}}, but it does not use any other information on the dependencies. Hence it can be expected to be wasteful and not give optimal results when the dependencies that exist are weak.

Remark 5.2. Several authors, e.g. [21], [16], [18], [20], have used a splitting of (1.1) into sums with independent summands in a slightly different way. In the notation above, the argument runs as follows.

Consider for simplicity Theorem 2.1. Let {(A_{j}, w_{j})}_{j} be an exact proper fractional cover of A (usually, only covers are considered), and let again X_{j} := ∑_{A_{j}} Y_{α}. For any positive p_{j} with ∑_{j} p_{j} = 1,

ℙ(X ≥ 𝔼 X +t) = ℙ(∑_{j} w_{j}(X_{j} −𝔼 X_{j}) ≥ ∑_{j} p_{j}t) ≤ ∑_{j} ℙ(X_{j} −𝔼 X_{j} ≥ \frac{p_{j}t}{w_{j}}).

Since each X_{j} is a sum of independent variables, the latter probabilities can be estimated by [14, Theorem 2], i.e. our Theorem 2.1 with χ^{∗}(A) = 1, yielding

ℙ(X ≥ 𝔼 X + t) ≤ ∑_{j} exp(−2\frac{p_{j}^{2}}{w_{j}^{2}c_{j}} t^{2}),

where, as in our proof of Theorem 2.1, c_{j} := ∑_{α∈A_{j}}(b_{α} − a_{α})^{2}. Taking again

p_{j} = w_{j}c_{j}^{1/2}/T with T := ∑_{j} w_{j}c_{j}^{1/2}, we obtain

ℙ(X ≥ 𝔼 X + t) ≤ N_{1} exp(−2t^{2}/T^{2}),

where N_{1} is the number of sets A_{j} in the fractional cover. (For an optimal cover, thus N_{1} = χ(A).) This is the same as (3.3) except for the factor N_{1}; hence it leads to the estimate in Theorem 2.1 multiplied by N_{1} (for an optimal fractional cover).

Hence Hoeffding’s method above, using Jensen’s inequality, is better, although the difference usually is negligible in applications.

This version of the splitting argument also applies to the other theorems above. Again, the results above are typically better by an insignificant factor, but exact comparison seems more difficult than for Theorem 2.1.

Remark 5.3. The definition in Section 2 of dependency graphs is not the only one in the literature. In some cases one needs a stronger version, requiring {Y_{α}}_{α∈A_{1}} and {Y_{α}}_{α∈A_{2}} to be independent of each other whenever A_{1} and A_{2} are two disjoint subsets of A with no edges between them. (See e.g. [16].)

In the opposite direction, an even weaker version, still sufficient for our purposes, would be to require only that {Y_{α}}_{α∈A_{1}} is a family of independent variables when A_{1} is an independent set in the graph. To see that this is strictly weaker than the definition used above, consider the three variables ξ_{1}ξ_{2}, ξ_{1}ξ_{3} and ξ_{2}ξ_{3}, where ξ_{1}, ξ_{2} and ξ_{3} are i.i.d. with ℙ(ξ_{i} = 1) = ℙ(ξ_{i} = −1) = 1/2. Then Γ is an independence graph in our sense if and only if Γ has at least two edges, while one edge suffices for the weaker definition.

Note further that |A| = 3 and that every proper subset of A is independent; hence no independence graph describes all independent sets. It is easily checked that χ^{∗}(A) = 3/2, but χ^{∗}(Γ) ≥ 2 for every independence graph (for any of the definitions above).

References

[1] A.K. Aleshkyavichene, Probabilities of large deviations for U-statistics and von Mises functionals. (Russian) Teor. Veroyatnost. i Primenen. 35 (1990), no. 1, 3–14; English transl. Theory Probab. Appl. 35 (1990), no. 1, 1–14 (1991).

[2] M.A. Arcones & E. Giné, Limit theorems for U-processes. Ann. Probab. 21 (1993), no. 3, 1494–1542.

[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. (Russian) Ann. Sci. Inst. Sav. Ukraine, Sect. Math. 1 (1924), 38–49.

[5] B. Bollobás, Extremal Graph Theory. Academic Press, London, 1978.

[6] B. Bollobás, Modern Graph Theory. Springer-Verlag, New York, 1998.

[7] J. Bretagnolle, A new large deviation inequality for U-statistics of order 2. ESAIM Probab. Statist. 3 (1999), 151–162.

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

[9] H. Cramér, Sur un noveau théorème-limite de la théorie des probabilités. Les sommes et les fonctions de variables aléatoires, Actualités Sci. Indust. 736, Hermann et Cie., Paris, 1938, pp. 5–23.

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

[11] P. Flajolet, Y. Guivarc’h, W. Szpankowski & B. Vallée, Hidden pattern statistics, Automata, Languages, and Programming (ICALP’2001), eds. F. Orejas et al., Lecture Notes Comp. Sci. 2076, Springer, 2001, pp. 152–165.

[12] A. Hajnal & E. Szemerédi, Proof of a conjecture of Erdős. Combinatorial Theory and its Applications, Vol. II, eds. P. Erdős, A. Rényi & V.T. Sós, Colloq. Math. Soc. János Bolyai 4, North-Holland, Amsterdam, 1970, pp. 601–623.

[13] W. Hoeffding, A class of statistics with asymptotically normal distribution. Ann. Math. Statist. 19 (1948), 293–325.

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

[15] S. Janson, T. Łuczak & A. Ruciński, An exponential bound for the probability of nonexistence of a specified subgraph in a random graph. Random Graphs ’87 (Proceedings, Poznań 1987), eds. M. Karoński, J. Jaworski & A. Ruciński, John Wiley & Sons, Chichester, 1990, pp. 73–87.

[16] S. Janson, T. Łuczak & A. Ruciński, Random Graphs, John Wiley & Sons, New York, 2000.

[17] S. Janson, K. Oleszkiewicz & A. Ruciński, Upper tails for subgraph counts in random graphs. Israel J. Math., to appear.

[18] S. Janson & A. Ruciński, The infamous upper tail. Random Struct. Alg. 20 (2002), no. 3, 317-342.

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

[20] S.V. Pemmaraju, Equitable coloring extends Chernoff–Hoeffding bounds. Approximation, Randomization and Combinatorial Optimization: Algorithms and Techniques (APPROX 2001 and RANDOM 2001), eds. M.X. Goemans et al, Lecture Notes Comp. Sci. 2129, Springer, 2001, pp. 285–296.

[21] V. Rödl & A. Ruciński, Random graphs with monochromatic triangles in every edge coloring. Random Struct. Alg. 5 (1994), no. 2, 253–270.

[22] V.H. Vu, A large deviation result on the number of small subgraphs of a random graph. Combin. Probab. Comput. 10 (2001), no. 1, 79–94.

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

E-mail address: svante.janson@math.uu.se
URL: http://www.math.uu.se/~svante/