Pairwise independence

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 ${\displaystyle \{A_i,i\in \{1,2,...,n\}\}}$ a set of ${\displaystyle n}$ Bernoulli events with probability of occurrence ${\displaystyle \mathbb{P}(A_i)=p_i}$ for each ${\displaystyle i}$. Suppose the bivariate probabilities are given by ${\displaystyle \mathbb{P}(A_i\cap A_j)=p_{ij}}$ for every pair of indices ${\displaystyle (i,j)}$. Kounias derived the following upper 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 a star spanning tree on a complete graph with ${\displaystyle n}$ nodes (where the edge weights are given by ${\displaystyle p_{ij}}$) from the sum of the marginal probabilities ${\displaystyle \sum _i{p}_i}$.
Hunter-Worsley tightened this upper 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 all spanning trees on the graph. These bounds are not the tightest possible with general bivariates ${\displaystyle p_{ij}}$ even when feasibility is guaranteed as shown in Boros et.al. However, when the variables are pairwise independent (${\displaystyle p_{ij}=p_i{p}_j}$), Ramachandra—Natarajan 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 ${\displaystyle 0\le p_1\le p_2\le \dots \le p_n\le 1}$. The tight bound in Eq. 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, while ordering of the probabilities plays a role in the derivation of the bound, the ordering among the smallest ${\displaystyle n-1}$ probabilities ${\displaystyle \{p_1,p_2,...,p_{n-1}\}}$ is inconsequential since only their sum is used.

Comparison with the Boole–Fréchet 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:

As shown in Ramachandra-Natarajan, it can be easily verified that the ratio of the two tight bounds in Eq. 2 and Eq. 1 is upper 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}$, ${\displaystyle p_n=1/2}$

where the probabilities are sorted in increasing order as ${\displaystyle 0\le p_1\le p_2\le \dots \le p_n\le 1}$. In other words, in the best-case scenario, the pairwise independence bound in Eq. 1 provides an improvement of ${\displaystyle 25\mathrm{\%}}$ over the univariate bound in Eq. 2.

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.