BRICS RS-96-27 Dubhashi et al.: Negative Dependence Through the FKG Inequality

BRICS

Basic Research in Computer Science

Negative Dependence Through the FKG Inequality

Devdatt Dubhashi Volker Priebe Desh Ranjan

BRICS Report Series RS-96-27 ISSN 0909-0878 July 1996 Copyright \begin{matrix}c \\ ◯ \end{matrix} 1996, BRICS, Department of Computer Science

University of Aarhus. All rights reserved.

Reproduction of all or part of this work is permitted for educational or research use on condition that this copyright notice is included in any copy.

See back inner page for a list of recent publications in the BRICS Report Series. Copies may be obtained by contacting:

BRICS Department of Computer Science University of Aarhus Ny Munkegade, building 540 DK - 8000 Aarhus C Denmark

Telephone: +45 8942 3360
Telefax: +45 8942 3255
Internet: BRICS@brics.dk

BRICS publications are in general accessible through WWW and anonymous FTP:

http://www.brics.dk/
ftp ftp.brics.dk (cd pub/BRICS)

Negative Dependence Through the FKG Inequality^{∗}

Devdatt Dubhashi^{†}

BRICS

Department of Computer Science

University of Aarhus

Ny Munkegade DK-8000 Aarhus C, Denmark

 dubhashi@daimi.aau.dk

Volker Priebe

Max-Planck-Institut für Informatik Im Stadtwald 66123 Saarbrücken, Germany

                                   priebe@mpi-sb.mpg.de

Desh Ranjan^{†}

Department of Computer Science New Mexico State University Las Cruces, NM 88003, USA

                   dranjan@cs.nmsu.edu

Abstract

We investigate random variables arising in occupancy problems, and show the variables to be negatively associated, that is, negatively dependent in a strong sense. Our proofs are based on the FKG correlation inequality, and they suggest a useful, general technique for proving negative dependence among random variables. We also show that in the special case of two binary random variables, the notions of negative correlation and negative association coincide.

∗This work was supported by the ESPRIT II Basic Research Actions Program of the EC under contract no. 7141 (project ALCOM II) and by the Danish National Research Foundation through the Centre for Basic Research in Computer Science (BRICS).

†Work partly done when the authors were visiting Max-Planck-Institut für Informatik, Saarbrücken. Desh Ranjan also acknowledges the hospitality of BRICS.

1 Introduction

Informally speaking, random variables are said to be negatively dependent, if they have the following property: if any one subset of the variables is “high”, then other (disjoint) subsets of the variables are “low”. Such variables arise frequently in the analysis of algorithms, for which a stream of random bits influences either the input or the execution of the algorithm. To give a more specific example, we consider occupancy problems, where m balls are randomly allocated into n bins. Typical random variables of interest are the occupancy numbers B_{i}, i ∈ [n], that is, the number of balls that are contained in bin i. The B_{i}’s are dependent, since ∑_{i} B_{i} = m. The intuitive argument from above—if one of the B_{i}’s is “large”, the other variables are less likely to be “large” as well—suggests that they are negatively dependent. Occupancy problems arise in the analysis of algorithms from areas as diverse as dynamic load balancing [1], simulation of parallel computer models on realistic parallel machines [3], and distributed graph coloring [11].

Dependence among random variables makes the analysis of an algorithm more difficult, since independent random variables obey many simple laws that do not hold for dependent random variables. The well-known Chernoff– Hoeffding bounds from the theory of large deviations are an excellent example in this respect. Much effort has been made to salvage these sharp bounds in the more general situation under consideration; see, for example, [11, 13, 3, 8]. It turns out that one can apply the Chernoff–Hoeffding bounds to sums of “strongly” negatively dependent random variables just as one would apply them to independent random variables; see Section 6. Hence, it is useful to establish negative dependence among random variables. However, this can be a hard task, and it is mostly accomplished by ad-hoc techniques. In this paper, we show that the FKG correlation inequality from the theory of partial orders can be a useful, general tool. We give simple proofs based on the FKG inequality, establishing negative dependence among random variables in three different settings. The results are not new, but we give new proofs that are more elegant than those appearing in the literature.

Our results involve a strong notion of negative dependence called negative association, which, in general, is much stronger than the better known negative correlation. In Section 5.1, we give a short proof that for the special case of two binary random variables, the two notions coincide. (This result can also be obtained by combining results in [5, 7].)

We further deal with two different types of occupancy experiments. In the first one, balls are thrown independently into bins—this gives rise to a (generalized) multinomial distribution for (B_{1}, …, B_{n}). The B_{i}’s are known to be negatively associated, [4]. In Section 5.3, we give a more direct proof of negative association for sums of the B_{i}’s. In the second experiment, we assume that m < n, that bins contain at most one ball, and that each distribution of balls among the bins is equally likely to occur. This is the so-called Fermi–Dirac model, which can be viewed as a special case of the more general permutation distribution. We prove in Section 5.2 that random variables with a permutation distribution satisfy the negative association condition, a result already mentioned in [7]. In particular, it follows that the occupancy numbers in the Fermi–Dirac model are negatively associated.

The paper is organized as follows. A detailed description of the probabilistic experiments is given in Section 2. We review the notion of negative association and the FKG inequality in Sections 3 and 4, respectively. Our results are proved in Section 5, and we give an application of our results to a probabilistic analysis in Section 6.

2 Experiments

For a positive integer n, let [n] := {1, …, n}; for I ⊆ [n], let Ī:= [n]−I. We investigate probabilistic experiments where m balls are randomly distributed among n bins. Let B_{i}, i ∈ [n], denote the occupancy number of bin i, that is, the number of balls that are contained in bin i at the end of the experiment.

We consider two types of experiments. In the first one, balls are thrown independently into bins with Pr(ball j goes into bin i) = p_{i,j}, i ∈ [n], j ∈ [m], and for each ball j, ∑_{i} p_{i,j} = 1. In the uniform case where p_{i,j} = p_{i} for each j ∈ [m], (B_{1}, …, B_{n}) have the usual multinomial distribution with

Pr(B_{1} = m_{1}, …, B_{n} = m_{n}) = \frac{n!}{m_{1}! ⋯ m_{n}!} · p_{1}^{m_{1}} ⋯ p_{n}^{m_{n}} ,

when ∑_{i} m_{i} = m. This is sometimes called the Maxwell–Boltzmann model.

In the second experiment, the so-called Fermi–Dirac model, bins contain at most one ball, and each distribution of balls among the bins is equally likely to occur. (This requires m < n.) The B_{i}’s are indicator variables in this case, and for m_{i} ∈ {0, 1}, i ∈ [n], with ∑_{i} m_{i} = m,

Pr(B_{1} = m_{1}, …, B_{n} = m_{n}) = \binom{n}{m}^{−1} .

The joint distribution of (B_{1}, …, B_{n}) in the Fermi–Dirac model is a special case of a permutation distribution for n random variables.

Definition 1 Let n be a positive integer.

1. The random variables J_{1}, …, J_{n} have the permutation distribution on [n], if they take values in [n] and, for every permutation σ : [n] → [n],

Pr(J_{1} = σ(1), …, J_{n} = σ(n)) = \frac{1}{n!} .

2. Let x_{1}, …, x_{n} be arbitrary real numbers. The random variables X_{1}, …, X_{n} are said to have a permutation distribution on (x_{1}, …, x_{n}), if there is a set of random variables J_{1}, …, J_{n} with the permutation distribution on [n] and X_{i} = x_{J_{i}} for each i ∈ [n].

We shall refer to either situation as a permutation distribution.

Remark 2 If x_{1}, …, x_{n} are all distinct, then this definition is equivalent to stating that

Pr(X_{1} = x_{σ(1)}, …, X_{n} = x_{σ(n)}) = \frac{1}{n!}

for every permutation σ : [n] → [n]. This is apparently the definition of Joag-Dev and Proschan [7].^{1} However, this is not equivalent if the x_{i}’s are not all distinct, which is the case needed in our application to the Fermi– Dirac model.

3 Negative Dependence of Random Variables

We consider only discrete random variables. X = (X_{1}, …, X_{n}) denotes a tuple of random variables X_{1}, …, X_{n}; we will assume that all expectations E[h(X)] exist.

1They use the term “expermutation” which we were not able to locate in the literature.

Two random variables X, Y are called negatively correlated, if cov(X, Y) := E[XY]−E[X]E[Y] ≤ 0. The following definition from [7] is a natural generalization of negative correlation (and other notions of negative dependence) to the case of n random variables.

Definition 3 (–A) The random variables X = (X_{1}, …, X_{n}) are negatively associated if for every index set I ⊆ [n], cov(f(X_{i}, i ∈ I), g(X_{i}, i ∈ Ī)) ≤ 0, that is,

E[f(X_{i}, i ∈ I)g(X_{i}, i ∈ Ī)] ≤ E[f(X_{i}, i ∈ I)]E[g(X_{i}, i ∈ Ī)] ,

for all non-decreasing functions f : ℝ^{|I|} → ℝ and g : ℝ^{n−|I|} → ℝ. (A function h : ℝ^{k} → ℝ is said to be non-decreasing, if h(x) ≤ h(y) whenever x ≤ y in the component-wise ordering on ℝ^{k}.)

Note that the same inequality will hold if f and g are both non-increasing functions.

Negative association of random variables is preserved under taking subsets, forming unions of independent sets, and forming sets of non-decreasing functions that are defined on disjoint subsets of the random variables. The following proposition makes some of these very useful properties more precise, see [7].

Proposition 4 1. If X = (X_{1}, …, X_{n}) and Y = (Y_{1}, …, Y_{m}) both satisfy (−A) and are mutually independent, then the augmented vector (X, Y) = (X_{1}, …, X_{n}, Y_{1}, …, Y_{m}) satisfies (−A).

2. Let X := (X_{1}, …, X_{n}) satisfy (−A). Let I_{1}, …, I_{k} ⊆ [n] be disjoint index sets, for some positive integer k. For j ∈ [k], let h_{j} : ℝ^{|I_{k}|} → ℝ be non-decreasing functions, and define Y_{j} := h_{j}(X_{i}, i ∈ I_{j}). Then the vector Y := (Y_{1}, …, Y_{k}) also satisfies (−A). That is, non-decreasing functions of disjoint subsets of negatively associated variables are also negatively associated. The same is true if each h_{j} is a non-increasing function.

Remark 5 It is obvious from the definition that two negatively associated random variables are negatively correlated. In general, the notion of negative association is much stronger than the notion of negative correlation; however, see Theorem 9.

4 The FKG Inequality

We recall some concepts from the theory of partial orders. A (finite) lattice (L, ≤_{L}) is a (finite) set L, partially ordered by ≤_{L}, in which every two elements x, y have a least upper bound, denoted x ∨ y and called the join of x and y, and a greatest lower bound, denoted x ∧ y and called the meet of x and y. A lattice L is called distributive, if, for all x, y, z ∈ L, we have the following two distributive laws:

x∧(y ∨z) = (x∧y)∨(x∧z) or, equivalently, x∨(y ∧z) = (x∨y)∧(x∨z) .

A function f : L → ℝ on a lattice (L, ≤_{L}) is said to be non-decreasing (non-increasing) with respect to ≤_{L}, if x ≤_{L} y implies f(x) ≤ f(y) (respectively, x ≤_{L} y implies f(x) ≥ f(y)). A function μ : L → ℝ^{+} is called log-supermodular, if, for all x, y ∈ L,

μ(x)μ(y) ≤ μ(x ∨ y)μ(x ∧ y) .  (4.1)

We give two examples of lattices that we will use in later sections.

Example 6 For positive integers n, m, define L := [n]^{m} and ≤_{L} to be the component-wise order, that is, for a = (a_{1}, …, a_{m}), b = (b_{1}, …, b_{m}) ∈ L,

a ≤_{L} b ⟺ a_{k} ≤ b_{k} for each k ∈ [m] .

Join and meet are given by the following equations on the components,

(a ∨ b)_{k} := max{a_{k}, b_{k}} and (a ∧ b)_{k} := min{a_{k}, b_{k}} ;

and it turns out that (L, ≤_{L}) is a distributive lattice because of the following property of integers,

min{u, max{v, w}} = max{min{u, v}, min{u, w}} ,
max{u, min{v, w}} = min{max{u, v}, max{u, w}} .

Example 7 For m < n, let L_{m} be the set of (ordered) m-element subsets S = {s_{1}, …, s_{m}} of [n], that is, s_{1} < ⋯ < s_{m}. For S, S′ ∈ L_{m}, we define S ⪯ S′ if s_{k} ≤ s′_{k} for all k ∈ [m]. If we identify S with (s_{1}, …, s_{m}) ∈ [n]^{m}, we can view (L_{m}, ⪯) as a sublattice of the lattice (L, ≤_{L}) from the previous example.

(Note that L_{m} is closed under ∨ and ∧. For m-element subsets S, S′ of [n] and any k ∈ [m − 1], (S ∨ S′)_{[k+1]} := max{s_{[k+1]}, s′_{[k+1]}} > max{s_{[k]}, s′_{[k]}} = (S ∨ S′)_{[k]}, since s_{[k+1]} > s_{[k]} and s′_{[k+1]} > s′_{[k]}. Therefore, (S ∨ S′) ∈ L_{m}, and (S ∧ S′) ∈ L_{m} is proved similarly.) (L_{m}, ⪯) is distributive, since it is a sublattice of the distributive lattice (L, ≤_{L}). (The lattice (L_{m}, ⪯) has also been considered in [14]. Figure 4.1 shows (L_{2}, ⪯) for n = 5.)

{1, 2} {1, 3} {1, 4} {1, 5} {2, 3} {2, 4} {2, 5} {3, 4} {3, 5} {4, 5}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}  ^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}  ^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}  ^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}  ^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}  ^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}  ^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}

Figure 4.1: The lattice (L_{2}, ⪯) of ordered 2-element subsets of {1, …, 5}.

There is an interesting relationship between (L_{m}, ⪯) and (L_{n−m}, ⪯). For m-element subsets S, S′ of [n], S ⪯ S′ if and only if \overline{S′} ⪯ \overline{S}. For i ∈ [m], let \overline{S′}_{i} =: ℓ + i, ℓ ≥ 0. This means ℓ + i − 1 ≥ S′_{ℓ} ≥ S_{ℓ}, since S ⪯ S′, and, in turn, ℓ + i − 1 ≤ \overline{S}_{i−1}. This implies \overline{S}_{i} ≥ ℓ + i = \overline{S′}_{i}, that is, \overline{S′} ⪯ \overline{S}.

The FKG inequality extends the correlation of monotone functions on the real line to the situation in which functions are defined on a lattice.

Theorem 8 (FKG Inequality [6, 12, 2]) Let L be a finite, distributive lattice and let μ : L → ℝ^{+} be a log-supermodular function. Then, if f, g : L → ℝ are both non-decreasing or both non-increasing with respect to ≤_{L}, we have

∑_{x∈L} f(x)μ(x) · ∑_{x∈L} g(x)μ(x) ≤ ∑_{x∈L} f(x)g(x)μ(x) · ∑_{x∈L} μ(x) .

If one of the functions is non-decreasing and the other is non-increasing, then the reverse inequality holds.

It is helpful to view μ as a measure on L. Assuming that μ is not identically zero, we can define, for any f : L → ℝ, its expectation E[f] := (∑_{x∈L} f(x)μ(x))/(∑_{x∈L} μ(x)). In this notation, the FKG inequality asserts, for example, that for any log-supermodular μ and functions f, g : L → ℝ,

E[f] · E[g] ≥ E[f · g] ,

if one of the functions is non-decreasing and the other one is non-increasing. This should be taken not only as a formal similarity with Definition 3 but as an indication why the FKG inequality is at the core of many proofs of negative association among random variables.

5 Results on Negative Dependence

5.1 Negatively Correlated Coins Satisfy (−A)

As already mentioned in Remark 5, two random variables are negatively correlated if they are negatively associated. We now show that the converse is true if both variables are binary (that is, are “coins”); cf. [5, Theorem 2] and [7, p. 287].

Theorem 9 Binary random variables are negatively associated if and only if they are negatively correlated.

Proof. In view of Remark 5, it remains to be proved that two binary random variables satisfy the negative association condition (−A) if they are negatively correlated. Let X, Y be negatively correlated binary random variables, that is, cov(X, Y) = E[XY] − E[X]E[Y] ≤ 0. For i, j ∈ {0, 1}, define μ_{i,j} := Pr(X = i, Y = j). We have E[X] = Pr(X = 1) = μ_{1,0} + μ_{1,1}, and cov(X, Y) ≤ 0 reads μ_{1,1} ≤ (μ_{1,0} + μ_{1,1}) · (μ_{0,1} + μ_{1,1}). Since μ_{0,0} + μ_{0,1} + μ_{1,0} + μ_{1,1} = 1, this is equivalent to

μ_{1,1} · μ_{0,0} = μ_{1,1} · (1 − μ_{0,1} − μ_{1,0} − μ_{1,1}) ≤ μ_{1,0} · μ_{0,1} .  (5.1)

Let L := {0, 1}^{2} and for x = (x_{1}, x_{2}), y = (y_{1}, y_{2}) ∈ L, x ≤_{L} y if and only if x_{1} ≤ y_{1} and x_{2} ≥ y_{2}; see Figure 5.1. It is easily seen that (L, ≤_{L}) defines a distributive lattice.

(0,1) (0,0) (1,0) (1,1)^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}  ^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}

Figure 5.1: The lattice (L = {0, 1}^{2}, ≤_{L}) defined in the proof of Theorem 9.

To establish the negative association condition for (X, Y), we have to prove that E[f(X)g(Y)] ≤ E[f(X)]E[g(Y)] for non-decreasing functions f, g : ℝ → ℝ. (All other cases are trivial.) Define real-valued functions f′, g′ on (L, ≤_{L}) by setting

f′(x_{1}, x_{2}) := f(x_{1}) , g′(x_{1}, x_{2}) := g(x_{2}) .

By definition of (L, ≤_{L}), f′ is non-decreasing and g′ is non-increasing on the lattice. For x = (x_{1}, x_{2}) ∈ L, define μ(x) := μ_{x_{1},x_{2}}. Note that

∑_{x∈L} f′(x)μ(x) = E[f(X)] , ∑_{x∈L} g′(x)μ(x) = E[g(Y)] , and

∑_{x∈L} f′(x)g′(x)μ(x) = E[f(X)g(Y)] .

Therefore, the desired result follows from the FKG inequality as soon as we have established log-supermodularity of μ. Again, there is only one nontrivial case to check, namely, x = (1, 1) and y = (0, 0) with x ∨ y = (1, 0) and x ∧ y = (0, 1). However, for these elements, the log-supermodularity condition (4.1) is nothing else but (5.1), that is, log-supermodularity of μ is implied by the assumption that X, Y are negatively correlated. □

5.2 Permutation Distribution Satisfies (−A)

In this paragraph, we prove that the indicator variables B_{1}, …, B_{n} in the Fermi–Dirac model are negatively associated. We will prove the stronger result that random variables having the permutation distribution are negatively associated. Basically, this result already appears in [7, Theorem 2.11]. Here we give a new short proof of this result via the FKG inequality.

Theorem 10 Random variables having the permutation distribution are negatively associated.

Proof. We shall first show that for any positive integer n, the permutation distribution on [n] is negatively associated. Let J_{1}, …, J_{n} have the permutation distribution on [n]. Let I ⊆ [n] be an arbitrary index set with |I| = k ≤ n. For a k-element subset S = {S_{1}, …, S_{k}} ⊆ [n] and a permutation τ on S, we shall write τ(S) for the vector (τ(S_{1}), …, τ(S_{k})).

Let (L_{k}, ⪯) be the lattice on the k-element subsets of [n] as defined in Example 7. For non-decreasing functions f : ℝ^{k} → ℝ, g : ℝ^{n−k} → ℝ , we define real-valued functions f′, g′ on (L_{k}, ⪯) by setting

f′(S) := \frac{1}{k!} ∑_{τ} f(τ(S)) , g′(S) := \frac{1}{(n − k)!} ∑_{ρ} g(ρ(\overline{S})) ,

where τ ranges over all permutations of S and ρ ranges over all permutations of \overline{S}. Then f′ is non-decreasing and g′ is non-increasing on the lattice. To see that f′ is non-decreasing, that is, f(S) ≤ f(S′) if S ⪯ S′, merely do a termwise comparison of the two summations. To see that g′ is non-increasing, observe in addition that S ⪯ S′ if and only if \overline{S} ⪰ \overline{S′}, see Example 7. Set μ(S) := \binom{n}{k}^{−1} to get a trivially log-supermodular measure. Observe now that (with σ varying over all permutations of [n])

∑_{S} f′(S)μ(S) = ∑_{S} ∑_{τ} f(τ(S))(n−k)!/n! = ∑_{σ} f(σ(i), i ∈ I)/n! = E[f(J_{i}, i ∈ I)] .

Similarly,

∑_{S} g′(S)μ(S) = E[g(J_{i}, i ∈ Ī)]

and

∑_{S} f′(S)g′(S)μ(S) = ∑_{S} ∑_{τ} f(τ(S)) ∑_{ρ} g(ρ(\overline{S}))/n!
= ∑_{σ} f(σ(i), i ∈ I)g(σ(i), i ∈ Ī)/n!
= E[f(J_{i}, i ∈ I)g(J_{i}, i ∈ Ī)] .

Applying the FKG inequality, we conclude that J_{1}, …, J_{n} are negatively associated.

We deduce that for any reals x_{1}, …, x_{n}, random variables X_{1}, …, X_{n} having the permutation distribution on (x_{1}, …, x_{n}) are negatively associated. Indeed, X_{i} = h_{i}(J_{i}) := x_{J_{i}} are non-decreasing functions of distinct variables; hence, by Proposition 4(2), we conclude that any permutation distribution is negatively associated. □

The desired result is now an immediate corollary.

Corollary 11 The indicator variables in the Fermi–Dirac model satisfy the negative association condition (−A).

5.3 Correlation Inequalitites for Sums of Occupancy Numbers

Correlations of the occupancy numbers B_{1}, …, B_{n} in our first experiment are extensively studied in [4]; it turns out that (B_{1}, …, B_{n}) satisfy a number of negative dependence conditions, including negative association. By Proposition 4, this implies general correlation inequalities for non-decreasing functions of disjoint subsets of the occupancy numbers. We now show that correlation inequalities involving sums of these occupancy numbers can be obtained in a more direct way via the FKG inequality.

A possible configuration of the experiment can be represented by a vector a := (a_{1}, …, a_{m}), with a_{k} ∈ [n] for each k ∈ [m]. This is the configuration where ball k goes into bin a_{k} for each k ∈ [m]. Define the lattice (L, ≤_{L} ) on all such configurations as in Example 6 and define μ : L → ℝ^{+} by μ(a) := ∏_{k} p_{a_{k},k} for each a ∈ L. For any a, b ∈ L, we have μ(a)μ(b) = μ(a ∨ b)μ(a ∧ b), and so μ is log-supermodular.

Let I, J ⊆ [n] be two index sets such that either I ∩ J = ∅ or I ∪ J = [n]; without loss of generality, we can arrange it by renumbering that J = {1, …, |J|} and I = {n − |I| + 1, …, n}. Let t_{I}, t_{J} be arbitrary nonnegative integers and define f, g : L → {0, 1} to be the indicator functions of the events (∑_{i∈I} B_{i} ≥ t_{I}) and (∑_{j∈J} B_{j} ≥ t_{J}), respectively, where B_{i}, i ∈ [n], are the (random) occupancy numbers. (The occupancy number of bin i on configuration a is given by B_{i}(a) := |{j | a_{j} = i}|.) The definition of the lattice order ≤_{L} ensures that f is non-decreasing, while g is non-increasing on L for any fixed integers t_{I}, t_{J}. Applying the FKG inequality, we get the following correlation inequality on the random variables B_{i}, i ∈ [n].

Theorem 12 Let I, J ⊆ [n] be index sets such that either I ∩ J = ∅ or I ∪ J = [n], and let t_{I}, t_{J} be arbitrary non-negative integers. Then

Pr (∑_{i∈I} B_{i} ≥ t_{I}, ∑_{j∈J} B_{j} ≥ t_{J}) ≤ Pr (∑_{i∈I} B_{i} ≥ t_{I}) · Pr (∑_{j∈J} B_{j} ≥ t_{J}) . (5.2)

Remark 13 (5.2) is referred to as the negative quadrant dependence condition for X := ∑_{i∈I} B_{i} and Y := ∑_{j∈J} B_{j}. It is known to be equivalent to the negative association condition (−A) for X, Y, [7]. This can also be easily seen by replacing f, g in the proof of Theorem 12 by arbitrary non-decreasing functions. In fact, even more general correlation inequalities follow along the same lines. For example, if we define a partial order on tuples of occupancy numbers (for a fixed number of balls) by

(B_{1}, …, B_{n}) ⪯ (B′_{1}, …, B′_{n}) ⟺ ∑_{k≤i≤n} B_{i} ≤ ∑_{k≤i≤n} B′_{i} for all k ∈ [n − 1] ,

then a ≤_{L} b implies (B_{1}(a), …, B_{n}(a)) ⪯ (B_{1}(b), …, B_{n}(b)) and, hence, the FKG inequality on L can be applied to functions on (B_{1}, …, B_{n}) that are non-decreasing or non-increasing with respect to ⪯.

6 Applications

Chernoff–Hoeffding bounds are large deviation estimates for sums S = ∑_{i=1}^{n} X_{i} of independent, identically distributed random variables X_{i}, that is, they provide bounds of the form

Pr(S > an) ≤ inf_{t>0} e^{−ant}(E[exp(tX_{1})])^{n} for a > E[X_{1}] = E[S]/n ; (6.1)

see, for example, [15, 10]. The independence assumption can be replaced by the requirement that

E[exp(t ∑_{i} X_{i})] ≤ ∏_{i} E[exp(tX_{i})] .

Because of Proposition 4, this is easily seen to be fulfilled if the X_{i}’s are negatively associated.

Theorem 14 Let X_{1}, …, X_{n} be identically distributed random variables whose joint distribution satisfies the negative association condition (−A). Then the Chernoff–Hoeffding bounds (6.1) apply for S := ∑_{i} X_{i}.

Analogues of this result are true for other notions of “strong” negative dependence among random variables, but the argument gets slightly more involved; see [4] for a more detailed account.

Theorem 14 allows, for example, a simple analysis of the following probabilistic experiment from [9]. Consider a k × n matrix A that is defined as follows. Row entries Ai·, i ∈ [k], are independent random variables, and for each row i, the entries A_{ij}, j ∈ [n], are indicator variables distributed according to the Fermi–Dirac model, that is, each row of A is a random 0-1 vector of length n with exactly m ones.

Let f(A) be the number of all-zero columns in A. By Corollary 11 and Proposition 4(1), the random variables A_{ij}, i ∈ [k], j ∈ [n], are negatively associated and so are the random variables C_{j} := 1 − sgn ∑_{i∈[k]} A_{ij}, j ∈ [n], by Proposition 4(2) (sgn 0 := 0, sgn x := 1 for x > 0). Note that f(A) = ∑_{j∈[n]} C_{j}, and Theorem 14 allows to apply Chernoff–Hoeffding bounds on f(A).

In [9], Mehlhorn and Priebe consider shortest path problems on complete digraphs (with loops) with respect to simple weight functions. On a graph with n vertices, for every vertex v and every integer j ∈ [n], there is exactly one edge of length j leaving v. Among other facts, Mehlhorn and Priebe use large deviation estimates for f(A) to deduce that on random simple weight functions, any algorithm for the single source shortest path problem has complexity Ω(n log n) with high probability.

References

[1] Adler, M., Chakrabarti, S., Mitzenmacher, M. and Rasmussen, L. (1995) Parallel randomized load balancing. In Proc. 27th Annual ACM Symposium on the Theory of Computing 238–247

[2] Alon, N., Spencer, J. H. and Erdős, P. (1992) The Probabilistic Method. John Wiley & Sons, New York.

[3] Dietzfelbinger, M. and Meyer auf der Heide, F. (1993) Simple, efficient shared memory simulations. In Proc. 5th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA ’93) 110–119 [4] Dubhashi, D. and Ranjan, D. (1996) Balls and Bins: A Study in Negative

Dependence. Manuscript

[5] Ebrahimi, N. and Ghosh, M. (1981) Multivariate negative dependence. Comm. Statist. Theory Methods A10 307–337

[6] Fortuin, C. M., Kasteleyn, P. W. and Ginibre, J. (1971) Correlation inequalities on some partially ordered sets. Comm. Math. Phys. 22 89–103

[7] Joag-Dev, K. and Proschan, F. (1983) Negative association of random variables, with applications. Ann. Statist. 11 286–295

[8] Kamath, A., Motwani, R., Palem, K. and Spirakis, P. (1995) Tail bounds for occupancy and the satisfiability threshold conjecture. Random Structures Algorithms 7 59–80

[9] Mehlhorn, K. and Priebe, V. (1995) On the all-pairs shortest path algorithm of Moffat and Takaoka. In P. Spirakis (Ed.), Algorithms — ESA ’95 (Proc. Third Annual European Symposium on Algorithms) [Lecture Notes in Computer Science 979] 185–198. Springer-Verlag, Berlin.

[10] Motwani, R. and Raghavan, P. (1995) Randomized Algorithms. Cambridge University Press, Cambridge.

[11] Panconesi, A. and Srinivasan, A. (to appear) Randomized distributed edge coloring via an extension of the Chernoff–Hoeffding bounds. SIAM J. Comput. Extended abstract appeared as A. Panconesi and A. Srinivasan (1992) Fast randomized algorithms for distributed edge coloring. In Proc. 11th Annual ACM Symposium on Principles of Distributed Computing 251–262.

[12] Sarkar, T. K. (1969) Some Lower Bounds of Reliability. Tech. Report 124, Dept. of Operations Research and Statistics, Stanford University.

[13] Schmidt, J. P., Siegel, A. and Srinivasan, A. (1995) Chernoff–Hoeffding bounds for applications with limited independence. SIAM J. Discrete Math. 8 223–250 [14] Shepp, L. A. (1980) The FKG inequality and some monotonicity prop-

erties of partial orders. SIAM J. Algebraic Discrete Methods 1 295–299

[15] Shwartz, A. and Weiss, A. (1995) Large Deviations for Performance Analysis. Chapman & Hall, London.

Recent Publications in the BRICS Report Series

RS-96-27 Devdatt Dubhashi, Volker Priebe, and Desh Ranjan. Negative Dependence Through the FKG Inequality. July 1996. 15 pp.

RS-96-26 Nils Klarlund and Theis Rauhe. BDD Algortihms and Cache Misses. July 1996. 15 pp.

RS-96-25 Devdatt Dubhashi and Desh Ranjan. Balls and Bins: A Study in Negative Dependence. July 1996. 27 pp.

RS-96-24 Henrik Ejersbo Jensen, Kim G. Larsen, and Arne Skou. Modelling and Analysis of a Collision Avoidance Protocol using SPIN and UPPAAL. July 1996. 20 pp. Presented at DIMACS Workshop SPIN96 � 2nd International SPIN Veri�cation Workshop on Algorithms, Applications, Tool Use, Theory (Rutgers University, New Jersey, USA, August 5, 1996).

RS-96-23 Luca Aceto, Wan J. Fokkink, and Anna Ing� olfsd� ottir. A Menagerie of Non-Finitely Based Process Semantics over BPA^{∗}: From Ready Simulation Semantics to Completed Tracs. July 1996. 38 pp.

RS-96-22 Luca Aceto and Wan J. Fokkink. An Equational Axiomatization for Multi-Exit Iteration. June 1996. 30 pp.

RS-96-21 Dany Breslauer, Tao Jiang, and Zhigen Jiang. Rotation of Periodic Strings and Short Superstrings. June 1996. 14 pp.

RS-96-20 Olivier Danvy and Julia L. Lawall. Back to Direct Style II: First-Class Continuations. June 1996. 36 pp. A preliminary version of this paper appeared in the proceedings of the 1992 ACM Conference on Lisp and Functional Programming, William Clinger, editor, LISP Pointers, Vol. V, No. 1, pages 299�310, San Francisco, California, June 1992. ACM Press.