Inprobability theory, apairwise independent collection ofrandom variables is a set of random variables any two of which areindependent.^[1] Any collection ofmutually independent random variables is pairwise independent, but some pairwise independent collections are not mutually independent. Pairwise independent random variables with finitevariance areuncorrelated.

A pair of random variablesX andY areindependentif and only if the random vector (X,Y) withjointcumulative distribution function (CDF)${\displaystyle F_{X,Y}(x,y)}$ satisfies

$${\displaystyle F_{X,Y}(x,y)=F_X(x)F_Y(y),}$$

or equivalently, their joint density${\displaystyle f_{X,Y}(x,y)}$ satisfies

$${\displaystyle f_{X,Y}(x,y)=f_X(x)f_Y(y).}$$

That is, the joint distribution is equal to the product of the marginal distributions.^[2]

Unless it is not clear in context, in practice the modifier "mutual" is usually dropped so thatindependence meansmutual independence. A statement such as "X,Y,Z are independent random variables" means thatX,Y,Z are mutually independent.

Pairwise independence does not imply mutual independence, as shown by the following example attributed to S. Bernstein.^[3]

SupposeX andY are two independent tosses of afair coin, where we designate 1 for heads and 0 for tails. Let the third random variableZ be equal to 1 if exactly one of those coin tosses resulted in "heads", and 0 otherwise (i.e.,${\displaystyle Z=X\oplus Y}$). Then jointly the triple (X,Y,Z) has the followingprobability distribution:

Here themarginal probability distributions are identical:${\displaystyle f_X(0)=f_Y(0)=f_Z(0)=1/2,}$ and${\displaystyle f_X(1)=f_Y(1)=f_Z(1)=1/2.}$ Thebivariate distributions also agree:${\displaystyle f_{X,Y}=f_{X,Z}=f_{Y,Z},}$ where${\displaystyle f_{X,Y}(0,0)=f_{X,Y}(0,1)=f_{X,Y}(1,0)=f_{X,Y}(1,1)=1/4.}$

Since each of the pairwise joint distributions equals the product of their respective marginal distributions, the variables are pairwise independent:

• X andY are independent, and
• X andZ are independent, and
• Y andZ are independent.

However,X,Y, andZ arenotmutually independent, since${\displaystyle f_{X,Y,Z}(x,y,z)\ne f_X(x)f_Y(y)f_Z(z),}$ the left side equalling for example 1/4 for (x,y,z) = (0, 0, 0) while the right side equals 1/8 for (x,y,z) = (0, 0, 0). In fact, any of${\displaystyle \{X,Y,Z\}}$ is completely determined by the other two (any ofX,Y,Z is thesum (modulo 2) of the others). That is as far from independence as random variables can get.

Bounds on theprobability that the sum ofBernoullirandom variables is at least one, commonly known as theunion bound, are provided by theBoole–Fréchet^[4][5] inequalities. While these bounds assume onlyunivariate information, several bounds with knowledge of generalbivariate probabilities, have been proposed too. Denote by${\displaystyle \{A_i,i\in \{1,2,...,n\}\}}$ a set of${\displaystyle n}$Bernoulli events withprobability of occurrence${\displaystyle \mathbb{P}(A_i)=p_i}$ for each${\displaystyle i}$. Suppose thebivariate probabilities are given by${\displaystyle \mathbb{P}(A_i\cap A_j)=p_{ij}}$ for every pair of indices${\displaystyle (i,j)}$. Kounias^[6] derived the followingupper bound:$${\displaystyle \mathbb{P}({\displaystyle {\cup }_i{A}_i)\le {\displaystyle \sum _{i=1}^n{p}_i-\underset{j\in \{1,2,..,n\}}{max}\sum _{i\ne j}{p}_{ij},}}}$$which subtracts the maximum weight of astarspanning tree on acomplete graph with${\displaystyle n}$ nodes (where the edge weights are given by${\displaystyle p_{ij}}$) from the sum of themarginal probabilities${\displaystyle \sum _i{p}_i}$.
Hunter-Worsley^[7][8] tightened thisupper bound by optimizing over${\displaystyle \tau \in T}$ as follows:$${\displaystyle \mathbb{P}({\displaystyle {\cup }_i{A}_i)\le {\displaystyle \sum _{i=1}^n{p}_i-\underset{\tau \in T}{max}\sum _{(i,j)\in \tau }{p}_{ij},}}}$$where${\displaystyle T}$ is the set of allspanning trees on the graph. These bounds are not thetightest possible with generalbivariates${\displaystyle p_{ij}}$ even whenfeasibility is guaranteed as shown in Boros et.al.^[9] However, when the variables arepairwise independent (${\displaystyle p_{ij}=p_i{p}_j}$), Ramachandra—Natarajan^[10] showed that the Kounias-Hunter-Worsley^[6][7][8] bound istight by proving that the maximum probability of the union of events admits aclosed-form expression given as:

$${\displaystyle max\mathbb{P}({\displaystyle {\cup }_i{A}_i)={\displaystyle min\left(\sum _{i=1}^n{p}_i-p_n\left(\sum _{i=1}^{n-1}{p}_i\right),1\right)}}}$$

1

where theprobabilities are sorted in increasing order as${\displaystyle 0\le p_1\le p_2\le \dots \le p_n\le 1}$. Thetight bound inEq. 1 depends only on the sum of the smallest${\displaystyle n-1}$probabilities${\displaystyle \sum _{i=1}^{n-1}{p}_i}$ and the largest probability${\displaystyle p_n}$. Thus, whileordering of theprobabilities plays a role in the derivation of the bound, theordering among the smallest${\displaystyle n-1}$probabilities${\displaystyle \{p_1,p_2,\dots ,p_{n-1}\}}$ is inconsequential since only their sum is used.

It is useful to compare the smallest bounds on the probability of the union with arbitrarydependence andpairwise independence respectively. ThetightestBoole–Fréchetupperunion bound (assuming onlyunivariate information) is given as:

$${\displaystyle {\displaystyle max\mathbb{P}({\displaystyle {\cup }_i{A}_i)={\displaystyle min\left(\sum _{i=1}^n{p}_i,1\right)}}}}$$

2

As shown in Ramachandra-Natarajan,^[10] it can be easily verified that the ratio of the twotight bounds inEq. 2 andEq. 1 isupper bounded by${\displaystyle 4/3}$ where the maximum value of${\displaystyle 4/3}$ is attained when$${\displaystyle \sum _{i=1}^{n-1}{p}_i=1/2,p_n=1/2}$$where theprobabilities are sorted in increasing order as${\displaystyle 0\le p_1\le p_2\le \cdots \le p_n\le 1}$. In other words, in the best-case scenario, the pairwise independence bound inEq. 1 provides an improvement of${\displaystyle 25\mathrm{\%}}$ over theunivariate bound inEq. 2.

More generally, we can talk aboutk-wise independence, for anyk ≥ 2. The idea is similar: a set ofrandom variables isk-wise independent if every subset of sizek 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 problemMAXEkSAT.

k-wise independence is used in the proof thatk-independent hashing functions are secure unforgeablemessage authentication codes.

• Pairwise
• Disjoint sets

• Theory of probability distributions
• Independence (probability theory)

• CS1 maint: multiple names: authors list
• Articles with short description
• Short description is different from Wikidata
• Pages that use a deprecated format of the math tags