pairwise independence and general independence

[gusl]

Given that X,Y,Z are pairwise independent, does it follow that X,Y,Z are jointly independent?
In order words, does P(x,y) = P(x)P(y), P(y,z) = P(y)P(z), P(x,z) = P(x)P(z) imply P(x,y,z) = P(x)P(y)P(z)?

Comments

[rdore.livejournal.com]

No. Suppose f is a randomly chosen affine function over Z mod 3. Then the values of f at 0, 1, and 2 are pairwise independent, but any two determine the third.

[rdore.livejournal.com]

More generally, n-wise independence does not imply (n+1)-wise independence. Let p be a prime bigger than n. Then let f be a randomly chosen polynomial over Z mod p of degree at most (n-1). Then the values of f at 0,...,n are n-wise independent but f is determined by any n points on it.

[jcreed.livejournal.com]

Such a cute little construction. Reminds me of 15-251.

[rdore.livejournal.com]

Well, this example can traces it's origin (for me) to a homework for Rudich's complexity theory class. There was a problem with a similar costruction where some amount of independence was proved, and that amount was enough for what you wanted to do. That construction was similar to the one above andfailed to have full indepence. Full independence who have been impossible in the context of the problem for some other reason I now forget.

I realized you can do something simpler: let x₁, x₁, ..., x_n each be (uniform) random bits, and let x_n+1 be the parity of those bits. Then the x_is will be n-wise independent, but not (n+1)-wise. This is basically the same example, just reimagined over F₂ instead of some larger F_p. More generally, let V be vector space over a finite field F of dimension n+1. Let S be an n dimensional subspace of V, and B be a basis for V which is disjoint from S. Now if we pick a random vector v in S uniformly, the B-coordinates of v are n-wise independent but not (n+1)-wise independent.

[rdore.livejournal.com]

You want the probability of 110 to be .25 and the probability of 111 to be 0.

[gustavolacerda.livejournal.com]

doh. Thx.

[gustavolacerda.livejournal.com]

Right. Here's a simple counterexample for my special case when n=2.

000 .25
001 0
010 0
011 .25
100 0
101 .25
110 .25
111 0

[ikeepaleopard]

I'm pretty sure this was a 251 problem when I took it.

[gustavolacerda.livejournal.com]

So each function corresponds to an outcome.

Is f real-valued? If so, I can imagine linear functions that produce a correlation between any pair in Z3.


<< but any two determine the third. >>

by drawing a straight line?

[rdore.livejournal.com]

f is a function from Z3 to Z3. f is of the form f(x) = a x + b (where a and b are integers and the calculation is mod 3). There are exactly 9 possible functions f.

[gustavolacerda.livejournal.com]

Tangentially, when I failed to prove it was true, I began believing that it was false.
I think that there is some kind of completeness in the calculus of probability. Perhaps even an "easy-completeness", i.e. if there is no easy proof, then it's false ("easy" could be defined in terms of proof size).
It would be nice to have this as a (non-constructive) tool.