In probability theory, a pairwise independent collection of random variables is a set of random variables any two of which are independent.
Pairwise independent random variables with finite variance are uncorrelated.
A pair of random variables X and Y are independent if and only if the random vector (X, Y) with joint cumulative distribution function (CDF)
satisfies or equivalently, their joint density
[2] Unless it is not clear in context, in practice the modifier "mutual" is usually dropped so that independence means mutual independence.
[3] 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 exactly one of those coin tosses resulted in "heads", and 0 otherwise (i.e.,
Then jointly the triple (X, Y, Z) has the following probability distribution: Here the marginal probability distributions are identical:
Since each of the pairwise joint distributions equals the product of their respective marginal distributions, the variables are pairwise independent: However, X, Y, and Z are not mutually independent, since
is completely determined by the other two (any of X, Y, Z is the sum (modulo 2) of the others).
Bounds on the probability that the sum of Bernoulli random variables is at least one, commonly known as the union bound, are provided by the Boole–Fréchet[4][5] inequalities.
While these bounds assume only univariate information, several bounds with knowledge of general bivariate probabilities, have been proposed too.
Bernoulli events with probability of occurrence
Kounias [6] derived the following upper bound: which subtracts the maximum weight of a star spanning tree on a complete graph with
Hunter-Worsley[7][8] tightened this upper bound by optimizing over
is the set of all spanning trees on the graph.
These bounds are not the tightest possible with general bivariates
even when feasibility is guaranteed as shown in Boros et.al.
), Ramachandra—Natarajan [10] showed that the Kounias-Hunter-Worsley [6][7][8] bound is tight by proving that the maximum probability of the union of events admits a closed-form expression given as: where the probabilities are sorted in increasing order as
The tight bound in Eq.
Thus, while ordering of the probabilities plays a role in the derivation of the bound, the ordering among the smallest
It is useful to compare the smallest bounds on the probability of the union with arbitrary dependence and pairwise independence respectively.
The tightest Boole–Fréchet upper union bound (assuming only univariate information) is given as: As shown in Ramachandra-Natarajan,[10] it can be easily verified that the ratio of the two tight bounds in Eq.
is attained when where the probabilities are sorted in increasing order as
In other words, in the best-case scenario, the pairwise independence bound in Eq.
over the univariate bound in Eq.
More generally, we can talk about k-wise independence, for any k ≥ 2.
The idea is similar: a set of random variables is k-wise independent if every subset of size k of those variables is independent.
k-wise independence has been used in theoretical computer science, where it was used to prove a theorem about the problem MAXEkSAT.
k-wise independence is used in the proof that k-independent hashing functions are secure unforgeable message authentication codes.