BRICS RS-95-15 Dubhashi et al.: The Fourth Moment in Luby’s Distribution

BRICS

Basic Research in Computer Science

The Fourth Moment in Luby’s Distribution

Devdatt P. Dubhashi Grammati E. Pantziou Paul G. Spirakis Christos D. Zaroliagis

BRICS Report Series RS-95-15

ISSN 0909-0878 February 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)

The Fourth Moment in Luby’s Distribution ^{∗}

Devdatt P. Dubhashi

BRICS ^{†}

Department of Computer Science, University of Aarhus,

Ny Munkegade, DK-8000 Aarhus C, Denmark

Email: dubhashi@daimi.aau.dk

Grammati E. Pantziou

Department of Computer Science,

University of Central Florida, Orlando FL 32816, USA

Email: pantziou@cs.ucf.edu

Paul G. Spirakis

Computer Technology Institute, P.O. Box 1122, 26110 Patras, Greece

and

Department of Computer Science & Engineering,

Patras University, 26500 Patras, Greece

Email: spirakis@cti.gr

Christos D. Zaroliagis

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

Email: zaro@mpi-sb.mpg.de

February 21, 1995

Abstract

Luby [10] proposed a way to derandomize randomized computations which is based on the construction of a small probability space whose elements are 3-wise independent. In this paper we prove some new properties of Luby’s space. More precisely, we analyze the fourth moment and prove an interesting technical property which helps to understand better Luby’s distribution. As an application, we study the behavior of random edge cuts in a weighted graph.

Keywords: Fourth moment, full independence, k-wise independence, derandomization.

∗This work was partially supported by the EU ESPRIT Basic Research Action No. 7141 (ALCOM II), by the Greek Ministry of Education and by NSF grant CDA-9211155. Part of this work has been done while the first author was with the Max-Planck-Institut für Informatik, Saarbrücken.

†Basic Research in Computer Science, Centre of the Danish National Research Foundation.

1 Introduction

During the last years there is a growing interest in techniques for removing randomness from parallel (and sequential) algorithms. These techniques were originated by [7, 8] and generalized in [1, 2, 4, 6, 9, 10, 11]. The approach usually followed can be summarized as follows: The random variables which are considered are defined over a smaller probability space, specially designed, containing only a polynomial number of sample points. In that space, the random variables are only k-wise independent (for constant k) but this is usually enough to replace the analysis of the randomized algorithm with fully independent random variables.

In most cases, only 3-wise (or 2-wise) independence is enough. However, in some instances, this is not sufficient [3]. The algorithms described in that paper can be derandomized successfully only because of the 4–wise independence property. In particular, an explicit example is given where Luby’s distribution [10], which is 3–wise but not 4–wise independent, cannot be used for the derandomization. But perhaps, it can be hoped that by relating the fourth moments under Luby’s distribution and the fully independent distribution, one can use Luby’s distribution in some other cases. This, so called fourth moment issue [2, 3], is very interesting technically because it might indicate the dividing barrier between the two probability spaces, namely k-wise and complete independence.

In this paper, we prove some new properties of Luby’s probability space, as defined in [10]. More precisely, we examine the fourth moment of this space. We compute the joint probability that four random variables takes particular values, and compare it to the corresponding joint probability under the fully independent distribution. The proof of the result is interesting in its own right and may lead to a general methodology of proving such results. We also relate precisely, the fourth moments under the two distributions. As an application, we study the behavior of random edge cuts in a weighted graph. Based on Luby’s probability space, it is easy to construct a linear sized space of edge cuts. We then prove that this smaller space has bigger variance compared with the variance in the fully independent space of all possible edge cuts taken equiprobably (which is exponential in size). Thus, the smaller space can be a good predictor of extreme values of random variables defined on the larger space, possibly leading to NC algorithms for better approximations to the maximum edge cut problem.

The paper is organized as follows. In section 2 we present the new properties of Luby’s distribution and the fourth moment bound. In Section 3 we discuss the applications of these properties in the computation of edge cuts in weighted graphs.

2 Properties of Luby’s Sample Space

Luby in [10], considers random variables X_{1}, …, X_{n}, for a positive integer n, defined on the sample space (Ω, Pr), where Ω = GF (2)^{k+1} = {0, 1}^{k+1}, k = ⌈log n⌉ and Pr the equiprobable measure, i.e., for each point ω ∈ Ω we have Pr(ω) = 2^{−(k+1)}. Let i ∈ {0, 1}^{k} denote the binary representation ⟨i_{1}, …, i_{k}⟩ of the integer i for 1 ≤ i ≤ n. At a point ω = ⟨ω_{1}, …, ω_{k+1}⟩, the random variable X_{i}, for 1 ≤ i ≤ n, takes the values given by the formula:

X_{i}(ω) = i · ω + ω_{k+1}  (1)

where the notation i · ω denotes i_{1}ω_{1} + ⋯ + i_{k}ω_{k}. (Note that in this section, all operations are under GF (2). Also, the reader is assumed to be familiar with basic linear algebra terminology and results; see e.g. [12]).

An alternate but equivalent description is as follows: Let L be an n × (k + 1) matrix over GF (2), whose ith row is [i, 1] = [i_{1}, …, i_{k}, 1], for 1 ≤ i ≤ n. Then at the point ω ∈ Ω (where now ω = [ω_{1}, …, ω_{k+1}]^{T}), the random variables take the values given by the vector L · ω. We call the values taken by the random variables at a point ω, their labels at ω.

We call a set of integers dependent if their binary representations are dependent as vectors over GF (2), and independent otherwise. The matrix L has some interesting properties which we give in the following (easy) proposition.

Proposition 1 (i) Any three rows of L are linearly independent. (ii) Any four rows of L are linearly independent unless they correspond to dependent integers, that is, to integers such that the binary representation of any one of them is the sum of the binary representations of the other three.

Proof: First note that no row is 0 on account of the last column. Hence, the only way for two rows to be linearly dependent is if their sum is 0. However, this is impossible as the binary representation of two distinct integers have a position where they differ. Thus any two rows are linearly independent. This in turn implies that the only way for any three rows to be dependent is if their sum is 0, which is impossible since the last column in such a sum is necessarily non-zero. Hence any three rows are linearly independent. From the independence of any three rows, it follows that the only way that any four rows can be dependent is if their sum is zero. This happens iff they correspond to integers with the stated property.

These properties of L imply the following properties of the distribution of the random variables X_{i}, i = 1, 2, …, n, defined above. (Remark: The first three are well-known; we add the last, interesting property.)

Lemma 2 Let i, j, l, m be distinct integers between 1 and n (so necessarily n ≥ 4 below) and b_{i}, b_{j}, b_{l}, b_{m} be an arbitrary bit pattern. Then, the following hold in Luby’s distribution:

1. Pr[X_{i} = b_{i}] = 1/2.

2. Pr[X_{i} = b_{i} ∧ X_{j} = b_{j}] = 1/4.

3. Pr[X_{i} = b_{i} ∧ X_{j} = b_{j} ∧ X_{l} = b_{l}] = 1/8.

4. Pr[X_{i} = b_{i}∧X_{j} = b_{j}∧X_{l} = b_{l}∧X_{m} = b_{m}] = \{ \begin{matrix}1/16 & if i + j + l ≠ m \\ 1/8 & if i + j + l = m and b_{i} + b_{j} + b_{l} = b_{m} \\ 0 & otherwise \end{matrix}

Proof: Since the proofs of (1)-(3) are similar, we shall prove the strongest one (3). Take the sub-system of L · ω = b corresponding to the rows i, j, l, to get L′ · ω = [b_{i}, b_{j}, b_{l}]^{T}. Take further a full rank square sub-matrix of L′ to form the square system L′′ · [ω_{i′}, ω_{j′}, ω_{l′}]^{T} = [b_{i}, b_{j}, b_{l}]^{T}. Since the coefficient matrix is non-singular, this has a unique solution. Fixing these three co-ordinates of ω as per the unique solution, and the rest to zeroes gives one point ω^{∗} ∈ Ω giving X_{i}, X_{j}, X_{l}, the respective labels b_{i}, b_{j}, b_{l}.

Let C be a 3 × n matrix (over GF (2)) with rows corresponding to i′, j′, l′ such that each row has all zeroes except for the position given by the corresponding integer where it is 1. Note that C has full rank. Now, ω gives the same labels as ω^{∗} to X_{i}, X_{j}, X_{l} iff CL(ω − ω^{∗}) = 0 i.e. iff ω − ω^{∗} ∈ KerCL. Since dim(Ω) = dim(KerCL) + dim(CL) (see e.g. [12], Theorem 6.8) and dim(CL) = rank(CL) = 3, it follows that dim(KerCL) = (k + 1) − 3 = k − 2. Hence |KerCL| = 2^{k−2} and consequently the probability in question is 2^{k−2}/2^{k+1} = 1/8.

Turning now to the final property (4), we have that if i + j + l ≠ m, then the rows corresponding to these integers are independent, and the proof as above gives the stated probability. Otherwise, if i + j + l = m, then the label of X_{m} is determined by those of X_{i}, X_{j} and X_{l} via

X_{m}(ω) = m · ω + ω_{k+1}
= (i + j + l) · ω + ω_{k+1}
= i · ω + ω_{k+1} + j · ω + ω_{k+1} + l · ω + ω_{k+1}
= X_{i}(ω) + X_{j}(ω) + X_{l}(ω)

Hence if b_{i} + b_{j} + b_{l} ≠ b_{m}, there are no points of Ω corresponding to these labels and the probability is zero. Otherwise, the probability is the same as that of the event that the three random variables take on a fixed label pattern which is computed in (3).

One can compare Luby’s distribution to the fully independent distribution where each X_{i} is equiprobably 0 or 1 independently. For this, we shall make use of the following notation.

Notation 1 We shall denote the statistics of Luby’s distribution with operators subscripted by L, for example, E_{L}, σ_{L}^{2} and those of the fully independent distribution by the subscript I, for example, E_{I}, σ_{I}^{2}. If no subscripts appear, then the result holds for both distributions.

The following lemma relates the moments between the two distributions.

Lemma 3 Let X = X_{1} + ⋯ + X_{n}. We have that E_{I}[X^{a}] = E_{L}[X^{a}] for 1 ≤ a ≤ 3 and

E_{L}[X^{4}] = E_{I}[X^{4}] + \frac{1}{64}\binom{n}{3}

Proof: The statements of the third and lower moments follow from the 3-wise independence of Luby’s distribution (Lemma 2). For the fourth moment, we observe by expanding that the only difference will come from terms of the form E_{L}[X_{i}X_{j}X_{l}X_{m}] for distinct i, j, l, m. In turn, this equals the probability computed in Lemma 2 above, applied to the bit pattern consisting of all ones. For integers i, j, l, m which are independent, this is the same as that for the fully independent distribution. For integers i, j, l, m which are dependent, this exceeds the probability of the fully independent distribution by 1/16. The result now follows from the fact that there are a total of \binom{n}{3}/4 such dependent tuples of integers.

3 Computing Edge Cuts in a Weighted Graph

Let G = (V, E) be a graph with weights W_{e} > 0 for each e ∈ E. Let also (V_{1}, V_{2}) be a partition of V into two disjoint sets V_{1} and V_{2}. Then a cut C in G is the set of edges with one endpoint in V_{1} and the other in V_{2}. The weight W (C) of the cut C, is the sum of the weights of all edges in C. The problem of asking whether there is cut in a graph G with weight at least K (K > 0) is known as the max-cut problem and is also known that it is an NP -complete problem [5].

Consider the application of Luby’s distribution to compute a random cut C in a graph G defined as above. Each vertex v ∈ V picks a label X_{v} ∈ {0, 1} and an edge is in C iff its endpoints have different labels. For any given edge, the probability that it is in C is 1/2 if the labels are picked either uniformly and independently from {0, 1}, or using Luby’s scheme. The latter part of the above statement holds because of the 2-wise independence of Luby’s distribution.

For two distinct edges, the probability that they are both in the cut under the fully independent distribution, is 1/4. The next proposition computes this probability under Luby’s distribution.

Proposition 4 Let e, e′ be fixed edges of G. The following hold: (i) If e and e′ share a vertex, then Pr_{L}[e ∈ C ∧ e′ ∈ C] = 1/4. (ii) If e and e′ are disjoint, but their endpoints correspond to independent integers, then Pr_{L}[e ∈ C ∧ e′ ∈ C] = 1/4. (iii) If e and e′ are disjoint, but their endpoints are dependent integers, then Pr_{L}[e ∈ C ∧ e′ ∈ C] = 1/2.

Proof: Follows easily from the probabilities computed in Lemma 2.

Let C be the random variable denoting the weight of the cut C. Then, we have (using the Iversonian APL notation [P] which denotes 1 if the boolean property P is true and 0 otherwise),

C = ∑_{e=(u,v)}[X_{u} ≠ X_{v}]W_{e}
= ∑_{e=(u,v)}(X_{u} + X_{v} − 2X_{u}X_{v})W_{e}
= ∑_{e} Y_{e}W_{e}  (2)

(since X_{u}, X_{v} are 0 − 1 valued). Here we denote, for e = (u, v), Y_{e} := X_{u} + X_{v} − 2X_{u}X_{v}. Hence,

E[C] = E [∑_{e} Y_{e}W_{e}]
= ∑_{e=(u,v)} E[(X_{u} + X_{v} − 2X_{u}X_{v})W_{e}]

= ∑_{e=(u,v)} (E[X_{u}] + E[X_{v}] − 2E[X_{u}X_{v}]) W_{e}
= ∑_{e=(u,v)} (E[X_{u}] + E[X_{v}] − 2E[X_{u}]E[X_{v}]) W_{e}
= 1/2 ∑_{e=(u,v)} W_{e}.  (3)

(In the third line, for Luby’s distribution, we use the 2–wise independence property.) Next we compute the second moment. From (2), we have,

C^{2} = ∑_{e} Y_{e}W_{e} · ∑_{e′} Y_{e′}W_{e′}
= ∑_{e,e′} Y_{e}Y_{e′}W_{e}W_{e′}
= ∑_{e∩e′=∅} Y_{e}Y_{e′}W_{e}W_{e′} + ∑_{e∩e′≠∅} Y_{e}Y_{e′}W_{e}W_{e′}
= ∑_{{e=(u,v) \atop e′=(w,z)}}(X_{u} + X_{v} − 2X_{u}X_{v})(X_{w} + X_{z} − 2X_{w}X_{z})W_{e}W_{e′}

+ ∑_{{e=(u,v) \atop e′=(u,w)}}(X_{u} + X_{v} − 2X_{u}X_{v})(X_{u} + X_{w} − 2X_{u}X_{w})W_{e}W_{e′}

= ∑_{{e=(u,v) \atop e′=(w,z)}} W_{e}W_{e′} ( ∑_{a=u,v} ∑_{b=w,z} X_{a}X_{b} − 2 ∑_{a≠b≠c≠a} X_{a}X_{b}X_{c} + 4X_{u}X_{v}X_{w}X_{z})

+ ∑_{{e=(u,v) \atop e′=(u,w)}} W_{e}W_{e′}(X_{u} + X_{v}X_{w} − X_{u}X_{w} − X_{u}X_{v}).

Hence it follows that

E[C^{2}] = ∑_{{e=(u,v) \atop e′=(w,z)}} 4W_{e}W_{e′}E[X_{u}X_{v}X_{w}X_{z}] + 1/4 ∑_{e∩e′≠∅} W_{e}W′_{e}.  (4)

Here we use for Luby’s distribution, the 3–wise independence property and the probabilities computed in Lemma 2.

For the fully independent distribution, we immediately have that for distinct u, v, w, z, E_{I}[X_{u}X_{v}X_{w}X_{z}] = 1/16. Thus we conclude from (4) that

E_{I}[C^{2}] = 1/4 ∑_{e∩e′=∅} W_{e}W_{e′} + 1/4 ∑_{e∩e′≠∅} W_{e}W_{e′}.  (5)

For Luby’s distribution, we use the probabilities computed in Lemma 2 to get:

E_{L}[X_{u}X_{v}X_{w}X_{z}] = \{ \begin{matrix}1/16 & if u, v, w, z are all distinct and independent; \\ 1/8 & otherwise. \end{matrix}

Hence, using (4),

E_{L}[C^{2}] = 1/4 ∑_{{e∩e′=∅ \atop ¬D(e,e′)}} W_{e}W_{e′} + 1/2 ∑_{D(e,e′)} W_{e}W_{e′} + 1/4 ∑_{e∩e′≠∅} W_{e}W_{e′}  (6)

where we use D(e, e′) to denote that the end–points of e, e′ are disjoint dependent integers. Comparing (5) and (6), we get:

E_{L}[C^{2}] = E_{I}[C^{2}] + 1/4 ∑_{D(e,e′)} W_{e}W_{e′}.

Since by (3) E_{I}[C] = E_{L}[C], we conclude:

Theorem 5 The variance under Luby’s distribution and the variance under the fully independent distribution are related as follows:

σ_{L}^{2}[C] = σ_{I}^{2}[C] + 1/4 ∑_{D(e,e′)} W_{e}W′_{e}

where D(e, e′) denotes that e, e′ have disjoint endpoints which are dependent integers.

Thus the variance under Luby’s distribution is at least as big as the variance under the fully independent distribution. Potentially, this can be used to get a better predictor of extreme values as implied by the following observation:

Observation 6 Given a weighted graph G, we can compute in NC a cut with weight either at most 1/2 ∑_{e} W_{e} − α or at least 1/2 ∑_{e} W_{e} + α where

α^{2} := σ_{I}^{2}(C) + 1/4 ∑_{D(e,e′)} W_{e}W′_{e}.

To see that such a cut exists, use the variance under Luby’s distribution. Further since Luby’s sample space has only linear size, we can exhaustively search it for the “good” point in NC. Remark: Under Luby’s distribution, the random variable X = X_{1} + X_{2} + ⋯ + X_{n} is symmetrically distributed around its mean E[X] = n/2. To see this, consider for each point ω = ⟨ω_{1}, …, ω_{k}, ω_{k+1}⟩ the point ω′ := ⟨ω_{1}, …, ω_{k}, 1 − ω_{k+1}⟩ and compute:

X(ω′) = ∑_{i=1}^{n} X_{i}(ω′) = ∑_{i=1}^{n}(1 − X_{i}(ω)) = n − X(ω)

Thus for each point ω such that X(ω) = n/2 − α, there corresponds the unique point ω′ such that X(ω′) = n/2 + α. Hence for each α, Pr[X = n/2 − α] = Pr[X = n/2 + α]. Unfortunately, this property no longer holds for the variable C we are interested in. We suspect (but cannot prove) that nevertheless, the distribution of C is “shifted upwards” in the sense that if Pr[C = E[C] − α] > 0, then also Pr[C = E[C] + α] > 0 for any α > 0. This would give us a predictor of an extreme value for max–cut.

4 Conclusion

We presented here some new properties of Luby’s probability space [10]. In particular, we analyzed the fourth moment and gave an application to the behavior of random edge cuts in a weighted graph. It would be very interesting if the new properties of Luby’s distribution presented in this paper can find other applications too.

References

[1] N. Alon, L. Babai and A. Itai, A Fast and Simple Randomized Parallel Algorithm for the Maximal Independent Set Problem, Journal of Algorithms 7 (1986) 567-583.

[2] B. Berger, Using Randomness to Design Efficient Deterministic Algorithms, Ph.D. Thesis, Dept. of Electrical Engineering and Computer Science, MIT 1990.

[3] B. Berger, The Fourth Moment Method, Proc. 2nd ACM-SIAM Symp. on Discrete Algorithms, 373-383, 1991.

[4] B. Berger and J. Rompel, Simulating (log^{c} n)-wise independence in NC, Proc. 30th IEEE Symp. on FOCS, 2-7, 1989.

[5] M. Garey and D. Johnson, Computers and Intractability – A Guide to the Theory of NP-Completeness (Ed. Freeman and Co, San Francisco, 1979).

[6] M. Goldberg and T. Spencer, A New Parallel Algorithm for the Maximal Independent Set Problem, SIAM J. on Computing, 18:2 (1989) 419-427.

[7] A. Joffe, On a set of almost deterministic k-independent random variables, Ann. Probability, 2 (1974) 161-162.

[8] R. Karp and A. Wigderson, A Fast Parallel Algorithm for the Maximal Independent Set Problem, Journal of the ACM, 32:4 (1985), 762-773.

[9] M. Luby, A Simple Parallel Algorithm for the Maximal Independent Set Problem, SIAM J. on Computing, 15:4 (1986), 1036-1053.

[10] M. Luby, Removing Randomness in Parallel Computation without a Processor Penalty, Proc. 29th IEEE Symp. on FOCS, 162-174, 1988.

[11] R. Motwani, J. Naor and M. Naor, The Probabilistic Method Yields Deterministic Parallel Algorithms, Proc. 30th IEEE Symp. on FOCS, 8-13, 1989.

[12] B. Noble and J.W. Daniel, Applied Linear Algebra, (Prentice-Hall International, 3rd edition, 1988).

Recent Publications in the BRICS Report Series

RS-95-15 Devdatt P. Dubhashi, Grammati E. Pantziou, Paul G. Spirakis, and Christos D. Zaroliagis. The Fourth Moment in Luby’s Distribution. February 1995. 10 pp.

RS-95-14 Devdatt P. Dubhashi. Inclusion�Exclusion(3) Implies Inclusion�Exclusion(n). February 1995. 6 pp.

RS-95-13 Torben Bra� uner. The Girard Translation Extended with Recursion. 1995. Full version of paper to appear in Proceedings of CSL ’94, LNCS.

RS-95-12 Gerth St�lting Brodal. Fast Meldable Priority Queues. February 1995. 12 pp.

RS-95-11 Alberto Apostolico and Dany Breslauer. An Optimal O(log log n) Time Parallel Algorithm for Detecting all Squares in a String. February 1995. 18 pp. To appear in SIAM Journal on Computing.

RS-95-10 Dany Breslauer and Devdatt P. Dubhashi. Transforming Comparison Model Lower Bounds to the Parallel-Random-Access-Machine. February 1995. 11 pp.

RS-95-9 Lars R. Knudsen. Partial and Higher Order Differentials and Applications to the DES. February 1995. 24 pp.

RS-95-8 Ole I. Hougaard, Michael I. Schwartzbach, and Hosein Askari. Type Inference of Turbo Pascal. February 1995. 19 pp.

RS-95-7 David A. Basin and Nils Klarlund. Hardware Veri�cation using Monadic Second-Order Logic. January 1995. 13 pp.

RS-95-6 Igor Walukiewicz. A Complete Deductive System for the μ-Calculus. January 1995. 39 pp.

RS-95-5 Luca Aceto and Anna Ing� olfsd� ottir. A Complete Equational Axiomatization for Pre�x Iteration with Silent Steps. January 1995. 27 pp.

RS-95-4 Mogens Nielsen and Glynn Winskel. Petri Nets and Bisimulations. January 1995. 36 pp. To appear in TCS.