Pairwise independence

Inprobability theory,apairwise independentcollection ofrandom variablesis a set of random variables any two of which areindependent.Any collection ofmutually independentrandom variables is pairwise independent, but some pairwise independent collections are not mutually independent. Pairwise independent random variables with finitevarianceareuncorrelated.

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

$F_{X,Y}(x,y)=F_{X}(x)F_{Y}(y),$

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

$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.

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

Example

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

SupposeXandYare two independent tosses of a fair coin, where we designate 1 for heads and 0 for tails. Let the third random variableZbe equal to 1 if exactly one of those coin tosses resulted in "heads", and 0 otherwise (i.e.,$Z=X\oplus Y$). Then jointly the triple (X,Y,Z) has the followingprobability distribution:

$(X,Y,Z)=\left\{{\begin{matrix}(0,0,0)&{\text{with probability}}\ 1/4,\\(0,1,1)&{\text{with probability}}\ 1/4,\\(1,0,1)&{\text{with probability}}\ 1/4,\\(1,1,0)&{\text{with probability}}\ 1/4.\end{matrix}}\right.$

Here themarginal probability distributionsare identical:$f_{X}(0)=f_{Y}(0)=f_{Z}(0)=1/2,$and $f_{X}(1)=f_{Y}(1)=f_{Z}(1)=1/2.$Thebivariate distributionsalso agree:$f_{X,Y}=f_{X,Z}=f_{Y,Z},$where$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:

• XandYare independent, and
• XandZare independent, and
• YandZare independent.

However,X,Y,andZarenotmutually independent,since$f_{X,Y,Z}(x,y,z)\neq 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$\{X,Y,Z\}$is completely determined by the other two (any ofX,Y,Zis thesum (modulo 2)of the others). That is as far from independence as random variables can get.

Probability of the union of pairwise independent events

Bounds on theprobabilitythat the sum ofBernoullirandom variablesis at least one, commonly known as theunion bound,are provided by theBoole–Fréchetinequalities. While these bounds assume onlyunivariateinformation, several bounds with knowledge of generalbivariateprobabilities, have been proposed too. Denote by$\{{A}_{i},i\in \{1,2,...,n\}\}$a set of$n$Bernoullievents withprobabilityof occurrence$\mathbb {P} (A_{i})=p_{i}$for each$i$.Suppose thebivariateprobabilities are given by$\mathbb {P} (A_{i}\cap A_{j})=p_{ij}$for every pair of indices$(i,j)$.Kouniasderived the followingupper bound:

$\mathbb {P} (\displaystyle {\cup }_{i}A_{i})\leq \displaystyle \sum _{i=1}^{n}p_{i}-{\underset {j\in \{1,2,..,n\}}{\max }}\sum _{i\neq j}p_{ij},$

which subtracts the maximum weight of astarspanning treeon acomplete graphwith$n$nodes (where the edge weights are given by$p_{ij}$) from the sum of themarginalprobabilities$\sum _{i}p_{i}$.
Hunter-Worsleytightened thisupper boundby optimizing over$\tau \in T$as follows:

$\mathbb {P} (\displaystyle {\cup }_{i}A_{i})\leq \displaystyle \sum _{i=1}^{n}p_{i}-{\underset {\tau \in T}{\max }}\sum _{(i,j)\in \tau }p_{ij},$

where$T$is the set of allspanning treeson the graph. These bounds are not thetightestpossible with generalbivariates$p_{ij}$even whenfeasibilityis guaranteed as shown in Boros et.al.However, when the variables arepairwise independent($p_{ij}=p_{i}p_{j}$), Ramachandra—Natarajanshowed that the Kounias-Hunter-Worsleybound istightby proving that the maximum probability of the union of events admits aclosed-form expressiongiven as:

$\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 theprobabilitiesare sorted in increasing order as$0\leq p_{1}\leq p_{2}\leq \ldots \leq p_{n}\leq 1$.Thetightbound inEq. 1depends only on the sum of the smallest$n-1$probabilities$\sum _{i=1}^{n-1}p_{i}$and the largest probability$p_{n}$.Thus, whileorderingof theprobabilitiesplays a role in the derivation of the bound, theorderingamong the smallest$n-1$probabilities$\{p_{1},p_{2},...,p_{n-1}\}$is inconsequential since only their sum is used.

Comparison with theBoole–Fréchetunion bound

It is useful to compare the smallest bounds on the probability of the union with arbitrarydependenceandpairwise independencerespectively. ThetightestBoole–Fréchetupperunion bound(assuming onlyunivariateinformation) is given as:

$\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,it can be easily verified that the ratio of the twotightbounds inEq. 2andEq. 1isupper boundedby$4/3$where the maximum value of$4/3$is attained when

$\sum _{i=1}^{n-1}p_{i}=1/2$,$p_{n}=1/2$

where theprobabilitiesare sorted in increasing order as$0\leq p_{1}\leq p_{2}\leq \ldots \leq p_{n}\leq 1$.In other words, in the best-case scenario, the pairwise independence bound inEq. 1provides an improvement of$25\%$over theunivariatebound inEq. 2.

Generalization

More generally, we can talk aboutk-wise independence, for anyk≥ 2. The idea is similar: a set ofrandom variablesisk-wise independent if every subset of sizekof 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 hashingfunctions are secure unforgeablemessage authentication codes.

See also

• Pairwise
• Disjoint sets