BRICS RS-95-48 D. P. Dubhashi: Simple Proofs of Occupancy Tail Bounds

BRICS

Basic Research in Computer Science

Simple Proofs of Occupancy Tail Bounds

Devdatt P. Dubhashi

BRICS Report Series RS-95-48 ISSN 0909-0878 September 1995 Copyright \begin{matrix}c \\ ◯ \end{matrix} 1995, 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@daimi.aau.dk

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

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

Simple Proofs of Occupancy Tail Bounds

Devdatt Dubhashi BRICS^{∗}, Department of Computer Science, University of Aarhus, Ny Munkegade, DK-8000 Aarhus C, Denmark

            Email: dubhashi@daimi.aau.dk

September 15, 1995

Abstract We give short proofs of some occupancy tail bounds using the method of bounded differences in expected form and the notion of negative association.

1 Introduction

The purpose of this note is to give short, simple and natural proofs of some tail bounds on occupancy problems in [5]. The proofs also serve as advertisements for some very useful, but apparently not very well–known concepts and techniques:

• The method of bounded differences in the expected form [6, Cor. 6.10].

• A concept of negative dependence called negative association from the theory of multivariate probability inequalities, [3, 4, 9, 10].

∗

Basic Research in Computer Science,

Centre of the Danish National Research Foundation.

The first of these yields the Occupancy Bound 1 of [5, Theorem 2] by a direct plug–in substitution. The second gives a short and enlightening calculation– free proof of the (Chernoff) Occupancy Bound 2 in [5, Theorem 3].

The setting is the classical probabilistic experiment of throwing m balls independently and uniformly ^{1} into n bins (for positive integers m, n). The random variables of interest are defined as follows: for i ∈ [n] ^{2}, let Z_{i} be the indicator variable which is 1 if bin i is empty and 0 otherwise. Set Z := ∑_{i} Z_{i} to be the number of empty bins. We are interested in tail bounds on the distribution of Z.

2 Bounded Differences

The “method of bounded differences” is usually stated and used in the following form [6, Lemma 1.2]

Proposition 1 (McDiarmid) Let X_{1}, …, X_{n} be independent random variables, variable X_{i} taking values in a finite set A_{i} for each i ∈ [n], and suppose the function f : ∏_{i} A_{i} → R satisfies the following “bounded difference” condition: For each i ∈ [n], there is a constant c_{i} such that

|f(x) − f(x′)| ≤ c_{i},

whenever the vectors x, x′ differ only in the kth co–ordinate. Then

Pr[|f(X) − E[f(X)]| > t] < 2 exp(−2t^{2}/ ∑_{i} c_{i}^{2}).

This lemma has an attractive packaged form, but can be too weak for some applications. In this case, we may resort to the “method of bounded differences” in the expected form [6, Cor. 6.10]:

Proposition 2 (McDiarmid) Let X_{1}, …, X_{n} be independent random variables, variable X_{i} taking values in a finite set A_{i} for each i ∈ [n], and suppose the function f satisfies the following “bounded difference” conditions: For each i ∈ [n], there is a constant c_{i} such that for any x_{k} ∈ A_{k}, k ∈ [i − 1] and for any x_{i}, x′_{i} ∈ A_{i}

1The techniques apply equally well even if the uniformity assumption is dropped, but we retain it for simplicity.

2We denote [n] := {1, …, n}

|E[f(X) | X_{1} = x_{1}, …, X_{i−1} = x_{i−1}, X_{i} = x_{i}]−
E[f(X) | X_{1} = x_{1}, …, X_{i−1} = x_{i−1}, X_{i} = x′_{i}]| ≤ c_{i} .  (1)

Then

Pr[|f(X) − E[f(X)]| > t] < 2 exp(−2t^{2}/ ∑_{i} c_{i}^{2}).

We shall illustrate the “method of bounded differences” in the above form by applying it to study the occupancy statistics in the classical balls and bins experiment. First, we have by simple calculations, E[Z_{i}] = (1− \frac{1}{n})^{m} and E[Z] = ∑_{i} E[Z_{i}] = m(1 − \frac{1}{n})^{m}.

To get a tail probability estimate, regard Z = Z(B_{1}, …, B_{m}) where the random variables B_{k} take values in the set [n] indicating which bin ball k occupies, for each k ∈ [m]. If one were to employ the “method of bounded differences” in the form of Proposition 1, it is easy to see that one must take c_{i} := 1 for each i ∈ [m]. Then one gets the tail probability bound:

Pr[|Z − E[Z]| > t] < 2 exp(−2t^{2}/ ∑_{i} c_{i}^{2}) = 2 exp(−2t^{2}/m).

This can be quite weak for large m and small t; compare the bound below.

An improved bound can be obtained by applying the expected version of Proposition 2. Fix some i ∈ [m] and let us compute

|E[Z | B_{1} = b_{1}, …, B_{i−1} = b_{i−1}, B_{i} = b_{i}]−
E[Z | B_{1} = b_{1}, …, B_{i−1} = b_{i−1}, B_{i} = b′_{i}]| ,

for fixed b_{1}, …, b_{i−1}, b_{i}, b′_{i} ∈ [n]. Set b := b_{i} ≠ b′_{i} =: b′. Let I := {b_{1}, …, b_{i−1}} ⊆ [n]. Of course for j ∈ I,

E[Z_{j} | B_{1} = b_{1}, …, B_{i−1} = b_{i−1}, B_{i} = b_{i}] = 0 =
E[Z_{j} | B_{1} = b_{1}, …, B_{i−1} = b_{i−1}, B_{i} = b′_{i}]  .  (2)

Also,

E[Z_{b} | B_{1} = b_{1}, …, B_{i−1} = b_{i−1}, B_{i} = b_{i}] = 0
E[Z_{b′} | B_{1} = b_{1}, …, B_{i−1} = b_{i−1}, B_{i} = b′_{i}] = 0.  (3)

For j ∈ [m] \ (I ∪ {b, b′}), we have

E[Z_{j} | B_{1} = b_{1}, …, B_{i−1} = b_{i−1}, B_{i} = b_{i}] = (1 − \frac{1}{n})^{m−i} =
E[Z_{j} | B_{1} = b_{1}, …, B_{i−1} = b_{i−1}, B_{i} = b′_{i}]  .  (4)

Now suppose b ∈ I but b′ ∉ I. Then with we have

E[Z_{b} | B_{1} = b_{1}, …, B_{i−1} = b_{i−1}, B_{i} = b′_{i}] = 0,  (5)

whereas

E[Z_{b′} | B_{1} = b_{1}, …, B_{i−1} = b_{i−1}, B_{i} = b_{i}] = (1 − \frac{1}{n})^{m−i}.  (6)

Finally (apart from the symmetric case of the previous one) if b, b′ ∉ I then,

E[Z_{b′} | B_{1} = b_{1}, …, B_{i−1} = b_{i−1}, B_{i} = b_{i}] = (1 − \frac{1}{n})^{m−i}.
E[Z_{b} | B_{1} = b_{1}, …, B_{i−1} = b_{i−1}, B_{i} = b′_{i}] = (1 − \frac{1}{n})^{m−i}.  (7)

Comparing (2) through (7), for i ∈ [m],

|E[Z | B_{1} = b_{1}, …, B_{i−1} = b_{i−1}, B_{i} = b_{i}]−
E[Z | B_{1} = b_{1}, …, B_{i−1} = b_{i−1}, B_{i} = b′_{i}]| ≤ c_{i},

where

c_{i} = (1 − 1/n)^{m−i},

Thus we have from Theorem 2,

Pr[|Z − E[Z]| > t] < 2 exp(−2t^{2}/ ∑_{i} c_{i}^{2}).

Since

∑_{i} c_{i}^{2} = \frac{n^{2} − μ^{2}}{2n − 1} ,

we get the occupancy bound Theorem 2 in [5]:

Pr[|Z − μ| ≥ θμ] ≤ 2 exp ( − \frac{θ^{2}μ^{2}(n − 1/2)}{n^{2} − μ^{2}}).

3 Negative Association

A very useful and robust notion of negative dependence between random variables called negative association was introduced by Joag–Dev and Proschan [4]:

Definition 3 (Negative Association) Let X := (X_{1}, …, X_{n}) be a vector of random variables.

(−A) The random variables, X are negatively associated if for every two disjoint index sets, I, J ⊆ [n],

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

for functions f : R^{|I|} → R and g : R^{|J|} → R that are both non–decreasing (or both non–increasing) with respect to the usual co–ordinatewise ordering of Euclidean spaces.

The next lemma list some properties that facilitate proofs of negative association. The properties themselves are immediate from the definition.

Lemma 4 1. If X and Y 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} : R^{|I_{k}|} → R be non–decreasing (or non–increasing) 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 (or non–increasing) functions of disjoint subsets of negatively associated variables are also negatively associated.

Proposition 5 The random variables Z_{1}, …, Z_{n} are negatively associated.

Sketch of Proof. Introduce the indicator variables for i ∈ [n], k ∈ [m],

B_{i,k} := \{ \begin{matrix}1, & if ball k goes into bin i; \\ 0, & otherwise. \end{matrix}

For each k ∈ [m], it is easy to show that the variables (B_{i,k} | i ∈ [n]) are negatively associated (observe that their joint distribution is simply a permutation distribution on 0, 0, …, 0, 1). Since each ball is thrown independently of the others, we conclude from Lemma 4(1) that the full set of variables (B_{i,k} | i ∈ [n], k ∈ [m]) are negatively associated. Finally observe that (using the Iverson symbol [P] which is 1 if the boolean property P is true and 0 otherwise) Z_{i} = [∑_{k} B_{i,k} = 0] is a non–increasing function of B_{i,k}, k ∈ [m]. Hence the result follows from Lemma 4(2).

Remark 6 In [2], a much fuller discussion of negative dependence in the balls and bins experiment can be found.

Proposition 7 ([2]) The Chernoff–Hoeffding bound applies to sums of negatively associated variables.

Sketch of Proof. From the definition of negative association, it follows by induction that if X_{1}, …, X_{n} are negatively associated, then

E[ ∏_{i∈[n]} f_{i}(X_{i})] ≤ ∏_{i∈[n]} E[f_{i}(X_{i})],

for any non–decreasing functions f_{i} : R → R. Now we apply the usual proof of the Chernoff–Hoeffding bound (see for instance [1, 7]) using the above inequality to replace the equality E[∏_{i∈[n]} e^{X_{i}}] = ∏_{i∈[n]} E[e^{X_{i}}] (which holds when the variables are independent) by the above inequality with each f_{i}(x) := e^{x}.

This yields directly, in a calculation–free manner, the (Chernoff) Occupancy Bound 2 in [5, Theorem 3].

Remark 8 It should be mentioned that [5] fail to mention [8] where this result is also obtained by arguments similar to theirs.

References

[1] N. Alon, P. Erdös, J. Spencer, The Probabilistic Method, John Wiley, 1992.

[2] D. Dubhashi, D. Ranjan, “Balls and Bins: A Study in Correlations”, Seventh Annual Conference on Random Structures and Algorithms, Atlanta 1995.

[3] M.L. Eaton, Lectures on Topics in Probability Inequalities, CWI Tracts in Mathematics, 35. 1982.

[4] K. Joag-Dev and F. Proschan, “Negative Association of Random Variables with Applications”, Annals of Statistics, 11:4, pp. 286– 295, 1983.

[5] A. Kamath, R. Motwani, K. Palem and P. Spirakis, “ Tail Bounds for Occupanvy Problems and the Satisfiability Threshold Conjecture”, Random Structures and Algorithms, 7:1, pp. 59–80, 1995.

[6] C. McDiarmid, “On the Method of Bounded Differences”, in J. Siemons (ed) Surveys in Combinatorics, London mathematical Society lecture Note Series 141, 1989.

[7] R. Motwani and P. Raghavan, Randomized Algorithms, Cambridge University Press, 1995.

[8] A. Panconesi and A. Srinivasan, “Fast Randomized Algorithms for Distributed Edge Coloring”, in Proceedings of the ACM Symposium on Principles of Distributed Computing, 1992, pp. 251– 262.

[9] R. Szekeli, Stochastic Ordering and Dependence in Applied probability, Lecture Notes in Statistics 97, Springer–Verlag 1995.

[10] Y.L. Tong, Probability Inequalities in Multivariate Distributions, Academic Press, 1980.

Recent Publications in the BRICS Report Series

RS-95-48 Devdatt P. Dubhashi. Simple Proofs of Occupancy Tail Bounds. September 1995. 7 pp.

RS-95-47 Dany Breslauer. The Suf�x Tree of a Tree and Minimizing Sequential Transducers. September 1995. 15 pp.

RS-95-46 Dany Breslauer, Livio Colussi, and Laura Toniolo. On the Comparison Complexity of the String Pre�x-Matching Problem. August 1995. 39 pp. Appears in Leeuwen, editor, Algorithms - ESA ’94: Second Annual European Symposium proceedings, LNCS 855, 1994, pages 483�494.

RS-95-45 Gudmund Skovbjerg Frandsen and Sven Skyum. Dynamic Maintenance of Majority Information in Constant Time per Update. August 1995. 9 pp.

RS-95-44 Bruno Courcelle and Igor Walukiewicz. Monadic Second-Order Logic, Graphs and Unfoldings of Transition Systems. August 1995. 39 pp. To be presented at CSL ’95.

RS-95-43 Noam Nisan and Avi Wigderson. Lower Bounds on Arithmetic Circuits via Partial Derivatives (Preliminary Version). August 1995. 17 pp. To appear in 36th Annual Conference on Foundations of Computer Science, FOCS ’95, IEEE, 1995.

RS-95-42 Mayer Goldberg. An Adequate Left-Associated Binary Numeral System in the λ-Calculus. August 1995. 16 pp.

RS-95-41 Olivier Danvy, Karoline Malmkj�r, and Jens Palsberg. Eta-Expansion Does The Trick. August 1995. 23 pp.

RS-95-40 Anna Ing� olfsd� ottir and Andrea Schalk. A Fully Abstract Denotational Model for Observational Congruence. August 1995. 29 pp.

RS-95-39 Allan Cheng. Petri Nets, Traces, and Local Model Checking. July 1995. 32 pp. Full version of paper appearing in Proceedings of AMAST ’95, LNCS 936, 1995.

RS-95-38 Mayer Goldberg. G� odelisation in the λ-Calculus. July 1995. 7 pp.