In probability theory, a pairwise independent collection of random variables is a set of random variables any two of which are independent.[1] Any collection of mutually independent random variables is pairwise independent, but some pairwise independent collections are not mutually independent. Pairwise independent random variables with finite variance are uncorrelated.
Example
Here is perhaps the simplest example. Suppose X and Y are two independent tosses of a fair coin, where we designate 1 for heads and 0 for tails. Let the third random variable Z be equal to 1 if one and only one of those coin tosses resulted in "heads", and 0 otherwise. Then jointly the triple (X, Y, Z) has the following probability distribution:
It is easy to verify that
- X and Y are independent, and
- X and Z are independent, and
- Y and Z are independent, however
- jointly X, Y, and Z are not independent, since any of them is completely determined by the other two (any of X, Y, Z is the mod 2 sum of the others). That is as far from independence as random variables can get. However, X, Y, and Z are pairwise independent, i.e. in each of the pairs (X, Y), (X, Z), and (Y, Z), the two random variables are independent.
More generally, we can talk about ℓ-wise independence, for any ℓ ≥ 2.
The idea is similar: a set of random variables is ℓ-wise independent if every subset of size ℓ of those variables is independent.
ℓ-wise independence has been used in theoretical computer science, where it (as k-wise independence) was used to prove a theorem about the problem MAXEkSAT.
See also
References
- ^ Alan Gut, Probability: a Graduate Course, Springer-Verlag, 2005, pp. 71–72.
This entry is from Wikipedia, the leading user-contributed encyclopedia. It may not have been reviewed by professional editors (see full disclaimer)
