most general way to generate pairwise independent random variables?

Question

Is there a sort of structure theorem for pairwise independent random variables or a very general way to create them?

I'm wondering because I find it difficult to come up with a lot of examples of nontrivial pairwise independent random variables. (by 'nontrivial', i mean not mutually independent)

one example (three r.v.):

X = face of dice 1

Y = face of dice 2

Z = X + Y mod 6

another example (three events) from some book:

Throw three coins. A = the number of heads is even, B = the first two flips are the same, C = the second two flips are heads.

another example:

$A_{ij}$ = dice i and dice j having the same face

($A_{ij}$, $i\neq j$) form a set of pairwise independent events, but the triple ($A_{ij}$, $A_{jk}$, $A_{ki}$) is not mutually independent.

Answer 1

I'm sure that Gil's answer is wise and that it is a good idea to look at Alon and Spencer's book. Here also is a quick summary of what is going on.

Suppose that $X_1,\ldots,X_n$ are random variables, and suppose for simplicity that they take finitely many values. Suppose that you prescribe the distribution of each $X_i$, and suppose also that you want the random variables to be pairwise independent or $k$-wise independent. Then the constraints on the joint distribution are a finite list of equalities and inequalities. The solution set is a polytope whose dimension is fairly predictable, and the fully independent distribution is always in the interior of this polytope. If you are interested in $k$-wise independent distributions that are far from $k+1$-wise independent, then it can be difficult to determine what is achievable because the polytope is complicated. (The vertices are a particularly interesting and non-trivial class: $k$-wise independent distributions with small support. These are called "weighted orthogonal arrays".) However, if you're just intersted in examples, it is much easier to write down a small deviation of the fully independent distribution. The deviation just satisfies linear equations.

For example, suppose that $X,Y,Z$ are three unbiased Bernoulli random variables (coin flips) that take values $0$ and $1$. Then there are 8 probabilities $p_{ijk}$, one for each outcome $(X,Y,Z) = (i,j,k)$. Then you can set $$p_{ijk} = \frac18 + (-1)^{i+j+k}\epsilon. \qquad\qquad\qquad \text{(1)}$$ to get a pairwise independent but not independent distribution. In this simple example, there is a 1-dimensional space of deviations and it is easy to compute how far you can vary the independent solution. (Up to $|\epsilon| = \frac18$.) In larger cases, the variations can be multidimensional and the polytope of deviations can be more complicated.

Addendum: If I have not made a mistake, all deviations for any finite list of discrete random variables are linear combinations of those of the form (1). More precisely, given discrete random variables $X_1,\ldots,X_n$, let $f_i$ be some function of the value of $X_i$ which is 1 for one value, $-1$ for another value, and $0$ otherwise. Then you can make deviations proportional to $\prod f_{i_j}$ as long as there are at least $k+1$ factors. It looks like all deviations are a linear combination of those of this form.

Answer 2

One very useful construction: if $X_1,\ldots,X_n$ are i.i.d. RVs, uniform in $\{0,\ldots,q-1\}$ ($q$ prime), then two linear combinations $\sum a_i X_i$ and $\sum b_i X_i$ are independent iff the vectors $a$ and $b$ are linearly independent (all operations are modulo q).

If we take $q=2$, this means that using $n$ i.i.d unbiased coin flips we can generate $2^n-1$ pairwise independent RVs, by taking all nonzero linear combinations.

This can be further generalized and generally yields some connections between k-wise independence and error correcting codes.

Answer 3

Here is the general form of 3 pairwise independent events.

Consider 3 events with respective probabilities $p(i)$ for $i = 1, 2, 3$. Write $p(1, 1, 1)$ for the probability that all 3 events occur. Using pairwise independence, one can determine the probabilities of the 7 other combinations of these 3 events and their complements from the given $p(i)$ and $p(1, 1, 1)$. (For example, $p(1,1,1) + p(1,1,0) = p(1)p(2)$, where $p(1,1,0)$ denotes the probability that only the first two events occur.) Excluding the case where any $p(i) = 0$, the solutions can be written as $$\left(0<p(1)\leq \frac{1}{3}\land \left(\left(0<p(2)\leq \frac{1}{2} (1-p(1))\land p(3)=-p(1)-p(2)+1\land 0\leq p(1,1,1)\leq p(1) p(2)\right)\lor \left(\frac{1}{2} (1-p(1))<p(2)<1-p(1)\land p(3)=-p(1)-p(2)+1\land 0\leq p(1,1,1)\leq p(1) p(3)\right)\right)\right)\\ \lor \left(\frac{1}{3}<p(1)\leq \frac{1}{2}\land ((0<p(2)\leq 1-2 p(1)\land p(3)=-p(1)-p(2)+1\land 0\leq p(1,1,1)\leq p(1) p(2))\lor (1-2 p(1)<p(2)<p(1)\land p(3)=-p(1)-p(2)+1\land 0\leq p(1,1,1)\leq p(2) p(3))\lor (p(1)\leq p(2)<1-p(1)\land p(3)=-p(1)-p(2)+1\land 0\leq p(1,1,1)\leq p(1) p(3)))\right)\\ \lor \left(\frac{1}{2}<p(1)<1\land 0<p(2)<1-p(1)\land p(3)=-p(1)-p(2)+1\land 0\leq p(1,1,1)\leq p(2) p(3)\right)$$ according to Mathematica's Reduce function.

More generally (and I think what Greg said), let $A_1, \ldots, A_n$ be $(n-1)$-wise independent events. For $I \subseteq [n]$, write

$$A_I := \bigcap_{i \in I} A_i^c \cap \bigcap_{i \notin I} A_i.$$

Also, write

$$z_I := P(A_I) - \prod_{i \in I} P(A_i^c) \cdot \prod_{i \notin I} P(A_i).$$

In particular,

$$z := z_\emptyset = P\Bigl(\bigcap_{i=1}^{n} A_i\Bigr) - \prod_{i=1}^{n} P(A_i).$$

Writing the probability of an intersection of events and their complements as an expectation of a product of indicators and expanding the product, we get that

$$z_I = (-1)^{|I|} z$$

for all $I$. Thus, the choices of $z$ that give a probability distribution are those for which

$$\prod_{i \in I} P(A_i^c) \cdot \prod_{i \notin I} P(A_i) + (-1)^{|I} z \in [0, 1]$$

for all $I$.

Answer 4

Let $f$ be the density of $X$ on $\Omega$. Define $F_k: \Omega \times \Omega \to {\mathbb R}$ by $F_1(x, y) = f(x)$ and $F_2(x, y) = f(y)$. The two variables $X_1$ and $X_2$ with densities $F_1$ and $F_2$ should be independent by Fubini's theorem. That way you can produce $n$ copies of a given variable.