Pairwise independence

Quality 0.50 · 3 views · Updated 2 months ago

Set of random variables of which any two are independent

title: "Pairwise independence" type: doc version: 1 created: 2026-02-28 author: "Wikipedia contributors" status: active scope: public tags: ["theory-of-probability-distributions", "independence-(probability-theory)"] description: "Set of random variables of which any two are independent" topic_path: "science/mathematics" source: "https://en.wikipedia.org/wiki/Pairwise_independence" license: "CC BY-SA 4.0" wikipedia_page_id: 0 wikipedia_revision_id: 0

::summary Set of random variables of which any two are independent ::

In probability theory, a pairwise independent collection of random variables is a set of random variables any two of which are independent. 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.

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) 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 that independence means mutual independence. A statement such as " X, Y, Z are independent random variables" means that X, Y, Z are mutually independent.

Example

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

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., Z = X \oplus Y). Then jointly the triple (X, Y, Z) has the following probability distribution:

(X,Y,Z) = \begin{cases} (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{cases}

Here the marginal probability distributions are identical: f_X(0) = f_Y(0) = f_Z(0) = 1/2, and f_X(1) = f_Y(1) = f_Z(1) = 1/2. The bivariate distributions also 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:

  • X and Y are independent, and
  • X and Z are independent, and
  • Y and Z are independent.

However, X, Y, and Z are not mutually 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 of X, Y, Z is the sum (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 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 inequalities. While these bounds assume only univariate information, several bounds with knowledge of general bivariate probabilities, have been proposed too. Denote by {{A}i, i \in {1,2,...,n}} a set of n Bernoulli events with probability of occurrence \mathbb{P}(A{i})=p_i for each i. Suppose the bivariate probabilities are given by \mathbb{P}(A_{i} \cap A_{j})=p_{ij} for every pair of indices (i,j). Kounias derived the following upper bound: \mathbb{P}(\displaystyle {\cup}iA{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 a star spanning tree on a complete graph with n nodes (where the edge weights are given by p_{ij}) from the sum of the marginal probabilities \sum_i p_i.

Hunter-Worsley tightened this upper bound by 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 all spanning trees on the graph. These bounds are not the tightest possible with general bivariates p_{ij} even when feasibility is guaranteed as shown in Boros et.al.{{cite journal | last1=Boros | first1=Endre | authorlink1=Endre Boros | last2=Scozzari | first2=Andrea | last3=Tardella | first3=Fabio | last4=Veneziani | first4=Pierangela | title=Polynomially computable bounds for the probability of the union of events | journal=Mathematics of Operations Research | volume=39 | number=4 | pages=1311–1329 | date=2014 | doi=10.1287/moor.2014.0657}} However, when the variables are pairwise independent (p_{ij}=p_ip_j), Ramachandra—Natarajan {{cite journal | last1=Ramachandra | first1=Arjun Kodagehalli | last2=Natarajan | first2=Karthik | title=Tight Probability Bounds with Pairwise Independence | journal=SIAM Journal on Discrete Mathematics | volume=37 | issue=2 | pages=516–555 | date=2023 | arxiv=2006.00516 | doi=10.1137/21M140829}} showed that the Kounias-Hunter-Worsley 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 0 \leq p_1 \leq p_2 \leq \ldots \leq p_n \leq 1. The tight bound in depends only on the sum of the smallest n-1 probabilities \sum_{i=1}^{n-1} p_{i} and the largest probability p_n. Thus, while ordering of the probabilities plays a role in the derivation of the bound, the ordering among the smallest n-1 probabilities {p_1,p_2,\dots,p_{n-1}} is inconsequential since only their sum is used.

Comparison with the [[Fréchet inequalities|Boole–Fréchet]] [[Boole's inequality|union bound]]

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:

\displaystyle \max \mathbb{P}(\displaystyle {\cup}i A{i}) = \displaystyle \min\left(\sum_{i=1}^n p_{i},1\right) |}} As shown in Ramachandra-Natarajan, it can be easily verified that the ratio of the two tight bounds in and is upper bounded by 4/3 where the maximum value of 4/3 is attained when \sum_{i=1}^{n-1} p_i = 1/2 , , \quad p_n=1/2 where the probabilities are sorted in increasing order as 0 \leq p_1 \leq p_2 \leq \dots \leq p_n \leq 1. In other words, in the best-case scenario, the pairwise independence bound in provides an improvement of 25% over the univariate bound in .

Generalization

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.

References

References

  1. Gut, A. (2005) ''Probability: a Graduate Course'', Springer-Verlag. {{isbn. 0-387-27332-8. pp. 71–72.
  2. Hogg, R. V., McKean, J. W., Craig, A. T.. (2005). "Introduction to Mathematical Statistics". Pearson Prentice Hall.
  3. Hogg, R. V., McKean, J. W., Craig, A. T.. (2005). "Introduction to Mathematical Statistics". Pearson Prentice Hall.
  4. Boole, G. (1854). ''An Investigation of the Laws of Thought, On Which Are Founded the Mathematical Theories of Logic and Probability.'' Walton and Maberly, London. See Boole's "major" and "minor" limits of a conjunction on page 299.
  5. Fréchet, M. (1935). Généralisations du théorème des probabilités totales. ''Fundamenta Mathematicae'' '''25''': 379–387.
  6. E. G. Kounias. (1968). "Bounds for the probability of a union, with applications". The Annals of Mathematical Statistics.
  7. D. Hunter. (1976). "An upper bound for the probability of a union". Journal of Applied Probability.
  8. K. J. Worsley. (1982). "An improved Bonferroni inequality and applications". Biometrika.

::callout[type=info title="Wikipedia Source"] This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page. ::

theory-of-probability-distributionsindependence-(probability-theory)