Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
5  
I don't think this question is as elementary as the down voters seem to think. Here is a way of making it sound harder, while being no deeper: Fix finite sets A, B and C. Consider the set of all probability distributions on A x B x C for which every two variables are independent. Can this set be parameterized? For example, it is semi-algebraic; is the underlying variety unirational? –  David Speyer Dec 6 '09 at 14:32
4  
There is a large body of literature on constructions of k-wise independent random variables. I suggest to look at Alon and Spencer's book on the probabilistic method. –  Gil Kalai Dec 6 '09 at 15:53
    
how can I check if an algorithm generates random variates of a specific distribution??? –  user3216 Jan 13 '10 at 7:02
    
[The following is probably obvious stuff, but since this page doesn't yet mention the word "polynomial"…] One standard way to generate n pairwise independent random variables is to take some prime p greater than n, independently generate two values a and b modulo p (a≠0), and take values of the polynomial (ax+b) mod p for different x (say X_i=(ai+b) mod p, for i=0 to i=n). This is pairwise independent but not 3-wise independent. In general, to get random variables that are k-wise independent but not (k+1)-wise, take a polynomial of degree k-1. –  shreevatsa Jun 28 '11 at 4:43
add comment

2 Answers

up vote 5 down vote accepted

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)^{ijk}\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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.