Bounded independence fools And

One of the earliest (and coolest) results in pseudorandomness is the following theorem that shows that k-wise independence “fools” the And function.


Theorem 1. [1] Let x_{1},x_{2},\ldots ,x_{n} be k-wise independent distributions over \{0,1\}. Then

\begin{aligned} |\mathbb {E}[\prod _{i\le n}x_{i}]-\prod _{i\le n}\mathbb{E} [x_{i}]|\le 2^{-\Omega (k)}. \end{aligned}

Proof. First recall that the inclusion-exclusion principle shows that for any random variables y_{1},y_{2},\ldots ,y_{n} jointly distributed over \{0,1\}^{n} according to a distribution D we have (write Or_{i} for the Or function on i bits);

\begin{aligned} \mathbb{E} \prod _{i\le n}y_{i} & =1-\mathbb{E} \text {Or\ensuremath {_{i}}}(1-y_{i})\nonumber \\ & =1-\sum _{j=1}^{n}T_{j}~~~~(1) \end{aligned}

where

\begin{aligned} T_{j}=(-1)^{j}\sum _{S\subseteq [n],|S|=j}\mathbb{E} \prod _{i\in S}1-y_{i}. \end{aligned}

Moreover, if we truncate the sum in Equation (1) to the first t terms, it gives either a lower bound or an upper bound depending on whether t is odd or even.

Because this holds under any distribution, if we show that the right-hand side of Equation (1) is approximately the same if the y_{i} are n-wise independent and k-wise, then the left-hand sides of that equation will also be approximately the same in the two scenarios, giving the result. (Note that \prod _{i\le n}\mathbb{E} [x_{i}] equals the expectation of the product of the x_{i} if the latter are n-wise independent.)

Now, since the terms T_{j} only involve expectations of the product of at most j variables, we have that they are the same under n-wise and k-wise independence up to j=k. This would conclude the argument if we can show that |T_{k}| is 2^{-\Omega (k)} (since this is the quantity that you need to add to go from a lower/upper bound to an upper/lower bound). This is indeed the case if \sum _{i\le n}\mathbb{E} [1-x_{i}]\le k/2e because then by McLaurin’s inequality we have

\begin{aligned} |T_{k}|=\sum _{S\subseteq [n],|S|=k}\prod _{i\in S}\mathbb{E} [1-x_{i}]\le (e/k)^{k}(\sum _{i\le n}\mathbb{E} [1-x_{i}])^{k}\le 2^{-k} \end{aligned}

where the first equality holds because the x_{i} are k-wise independent.

There remains to handle the case where \sum _{i\le n}\mathbb{E} [1-x_{i}]>k/2e. In this case, the expectations are so small that even running the above argument over a subset of the random variables is enough. Specifically, let n' be such that \sum _{i\le n}\mathbb{E} [1-x_{i}]=k/2e (more formally you can find an n' such that this holds up to an additive 1, which is enough for the argument; but I will ignore this for simplicity). Then the above argument still applies to the first n' variables. Moreover, the expectation of the product of just these n' variables is already fairly small. Specifically, because the geometric mean is always less than the arithmetic mean (a fact which is closely related to McLaurin’s inequality), we have:

\begin{aligned} \prod _{i\le n'}\mathbb{E} [x_{i}]\le (\frac {1}{n'}\sum _{i\le n'}\mathbb{E} [x_{i}])^{n'}\le (\frac {1}{n'}(n'-k/2e))^{n'}\le (1-k/2en')^{n'}\le 2^{-\Omega (k)}. \end{aligned}

Since under any distribution the expectation of the product of the first n variables is at most the expectation of the product of the first n', the result follows. \square

An interesting fact is that this theorem is completely false if the variables are over \{-1,1\} instead of \{0,1\}, even if the independence is n-1. The counterexample is well-known: parity. Specifically, take uniform variables and let x_{n}=\prod _{i<n}x_{i}. What may be slightly less known is that this parity counterexample also shows that the error term in the theorem is tight up to the constant in the \Omega . This is because you can write any function on t bits as the disjoint union of 2^{t} rectangles.

A side aim of this post is to try a new system I put together to put math on wordpress. I’ll test it some more and then post about it later, comparing it with the alternatives. Hopefully, my thinking that it was the lack of this system that prevented me from writing math-heavier posts was not just an excuse to procrastinate.

References

[1]   Guy Even, Oded Goldreich, Michael Luby, Noam Nisan, and Boban Velickovic. Approximations of general independent distributions. In ACM Symp. on the Theory of Computing (STOC), pages 10–16, 1992.

Advertisements

3 thoughts on “Bounded independence fools And

  1. Isn’t this a simpler proof: Use triangle inequality and the fact that 0 <= AND(x_1 … x_n) <= AND(x_1 .. x_k).
    | E[\prod_i^n X_i] – E[\prod_i^n U_i] | <= | E[\prod_i^k X_i] | + | E[\prod_i^n U_i] | = 2^-k + 2^-n

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s