Pairwise Independence in Weak-Law Arguments

Why Pairwise Independence Can Be Enough

A weak law asks whether an average becomes close to a constant in probability as the sample size grows. Full mutual independence is one familiar route to a useful variance calculation, but it is stronger than necessary for that calculation. If every pair of distinct observations is independent, their pairwise covariances vanish, and the variance of a sum is still the sum of the individual variances.

This distinction is useful when a model guarantees independence only in pairs. It also marks a limit: pairwise independence controls the variance of a sum, but it does not give all the joint independence properties that might be needed for other arguments.

Definition: Random variables $X_1,\ldots,X_n$ are pairwise independent if, for every distinct $i,j$, the random variables $X_i$ and $X_j$ are independent. A sequence is pairwise independent if every finite subcollection is pairwise independent. They are mutually independent if every finite subcollection has a joint distribution equal to the product of its marginal distributions. Mutual independence implies pairwise independence, but the converse need not hold.

For a sequence of observations, write $S_n=\sum_{i=1}^n X_i$. The average can be compared either with its own mean $n^{-1}\sum_{i=1}^n E[X_i]$ or with a fixed target $c$. These are different centers when the observations do not all have the same mean. Keeping that distinction explicit prevents a bias in the average from being mistaken for random variation.

The Variance Calculation

Suppose $X_1,\ldots,X_n$ are pairwise independent and $E[X_i^2]<\infty$ for every $i$. Finite second moments ensure that the variances exist and that the covariance calculation is well-defined. For distinct $i,j$, independence gives $E[X_iX_j]=E[X_i]E[X_j]$, so $\operatorname{Cov}(X_i,X_j)=0$.

\begin{aligned} \operatorname{Var}(S_n) &=\sum_{i=1}^n\operatorname{Var}(X_i) +2\sum_{1\leq i<j\leq n}\operatorname{Cov}(X_i,X_j)\\ &=\sum_{i=1}^n\operatorname{Var}(X_i). \end{aligned}

No mutual independence is used in this identity. The pairwise covariances are exactly the terms needed to compute the variance of the sum, and each is zero under pairwise independence.

Theorem: If $X_1,\ldots,X_n$ are pairwise independent with finite second moments, then, for every $t>0$, $$ P\left(\left|S_n-E[S_n]\right|>t\right) \leq \frac{\sum_{i=1}^n\operatorname{Var}(X_i)}{t^2}. $$ Equivalently, for every $\varepsilon>0$, $$ P\left(\left|\frac{S_n}{n}-\frac{1}{n}\sum_{i=1}^n E[X_i]\right|>\varepsilon\right) \leq \frac{\sum_{i=1}^n\operatorname{Var}(X_i)}{n^2\varepsilon^2}. $$

To prove the bound, use the variance identity above and Chebyshev's inequality. In detail, for any random variable $Z$ with finite variance and any $t>0$, $t^2\mathbf{1}_{\{|Z-E[Z]|>t\}}\leq (Z-E[Z])^2$. Taking expectations and dividing by $t^2$ gives $P(|Z-E[Z]|>t)\leq\operatorname{Var}(Z)/t^2$. Apply this to $Z=S_n$, substitute the pairwise-independence variance identity, and then set $t=n\varepsilon$ to obtain the average bound. $\square$

Worked Example: Alternating Bernoulli Means and a Small Bias

Let $X_1,X_2,\ldots$ be independent Bernoulli random variables, with $P(X_i=1)=1/4$ for odd $i$ and $P(X_i=1)=3/4$ for even $i$. Show that their average converges in probability to $1/2$, taking care with odd sample sizes.

Each variance is $p(1-p)=3/16$, regardless of whether $p=1/4$ or $p=3/4$. Independence implies pairwise independence, so $\operatorname{Var}(S_n)=3n/16$, and the variance of the average is $3/(16n)$.

If $n=2m$, there are $m$ probabilities of each type. The sum of the means is $m/4+3m/4=m$, so $E[S_n/n]=1/2$.

If $n=2m+1$, there are $m+1$ odd indices and $m$ even indices. Thus \[ E[S_n]=(m+1)\frac14+m\frac34 =\frac{4m+1}{4}=m+\frac14, \] and \[ E[S_n/n]=\frac{m+1/4}{2m+1} =\frac12-\frac{1}{4n}. \] The average mean is not exactly $1/2$ for odd $n$; its bias from $1/2$ is $1/(4n)$.

For even $n$, Chebyshev's inequality gives \[ P\left(\left|S_n/n-\frac12\right|>\varepsilon\right) \leq \frac{3}{16n\varepsilon^2}. \] For odd $n$, when $\varepsilon>1/(4n)$, the triangle inequality and the centered bound give \[ P\left(\left|S_n/n-\frac12\right|>\varepsilon\right) \leq \frac{3}{16n\left(\varepsilon-\frac{1}{4n}\right)^2}. \] For any fixed $\varepsilon>0$, once $1/(4n)\leq\varepsilon/2$, both parities satisfy the common bound $3/(4n\varepsilon^2)$. This tends to zero, proving convergence in probability to $1/2$.

A Weak-Law Criterion

The variance bound is centered at the average mean, not automatically at a desired constant. The following criterion makes both requirements explicit.

Theorem: Let $X_1,X_2,\ldots$ be pairwise independent random variables with $E[X_i^2]<\infty$ for every $i$. Define $a_n=n^{-1}\sum_{i=1}^n E[X_i]$. If $a_n\to c$ and \[ \frac{1}{n^2}\sum_{i=1}^n\operatorname{Var}(X_i)\longrightarrow 0, \] then $S_n/n\xrightarrow{p}c$.

To prove the theorem, fix $\varepsilon>0$. Since $a_n\to c$, for all sufficiently large $n$, $|a_n-c|<\varepsilon/2$. For those $n$, if $|S_n/n-c|>\varepsilon$, then \[ |S_n/n-a_n|\geq |S_n/n-c|-|a_n-c|>\varepsilon/2. \] Therefore, by the average variance bound, \[ P(|S_n/n-c|>\varepsilon) \leq P(|S_n/n-a_n|>\varepsilon/2) \leq \frac{4}{n^2\varepsilon^2} \sum_{i=1}^n\operatorname{Var}(X_i). \] The final expression tends to zero by assumption. This is precisely $S_n/n\xrightarrow{p}c$. $\square$

A common sufficient condition for the variance requirement is a uniform bound on the individual variances: if $\operatorname{Var}(X_i)\leq C$ for every $i$, where $C<\infty$, then $n^{-2}\sum_{i=1}^n\operatorname{Var}(X_i)\leq C/n\to0$. If, in addition, the average means tend to $c$, the theorem applies. Identical distributions are not required.

Worked Example: Rare Bernoulli Observations

Let $X_i$ be independent Bernoulli random variables with $P(X_i=1)=1/(i+1)$. Show that their average converges in probability to zero using the variance criterion.

The average mean is \[ a_n=\frac{1}{n}\sum_{i=1}^n\frac{1}{i+1}. \] Since $1/k\leq\int_{k-1}^{k} dx/x$ for integers $k\geq2$, \[ \sum_{i=1}^n\frac{1}{i+1} =\sum_{k=2}^{n+1}\frac1k\leq \log(n+1), \] so $0\leq a_n\leq\log(n+1)/n\to0$.

Also, $\operatorname{Var}(X_i)=p_i(1-p_i)\leq p_i$. Hence \[ \frac{1}{n^2}\sum_{i=1}^n\operatorname{Var}(X_i) \leq\frac{\log(n+1)}{n^2}\longrightarrow0. \] The criterion applies with $c=0$, giving $S_n/n\xrightarrow{p}0$. Here both the average mean and the average’s random fluctuation are controlled; neither condition is omitted.

Pairwise Does Not Mean Mutual

Worked Example: A Pairwise-Independent Sequence That Is Not Mutually Independent

For each $k\geq1$, let $U_k,V_k$ be independent random signs, each taking values $1$ and $-1$ with probability $1/2$. Assume the pairs $(U_k,V_k)$ are mutually independent across $k$, and set $W_k=U_kV_k$. List the observations in blocks $U_k,V_k,W_k$.

Within a block, $U_k$ and $V_k$ are independent. For signs $a,b\in\{-1,1\}$, $P(U_k=a,W_k=b)=P(U_k=a,V_k=ab)=1/4$, so $U_k$ and $W_k$ are independent; the same calculation shows $V_k$ and $W_k$ are independent. Variables from different blocks are independent by construction. Thus the entire sequence is pairwise independent.

The triple in a block is not mutually independent: $U_kV_kW_k=1$ with probability one. In particular, $P(U_k=V_k=W_k=1)=1/4$, not $1/8$, as mutual independence would require. Nevertheless, each variable has mean zero and variance one. For the first $n$ observations, the sum has mean zero and variance $n$ by pairwise independence, so \[ P\left(\left|\frac{1}{n}\sum_{i=1}^nX_i\right|>\varepsilon\right) \leq\frac{1}{n\varepsilon^2}\longrightarrow0. \] Thus the weak law holds even though the sequence is not mutually independent.

What the Conditions Do—and Do Not—Guarantee

Pairwise independence provides a clean way to control variance, but finite variance for each observation is not, by itself, enough. The sum of variances must be small relative to $n^2$, and the average of the means must approach the proposed limit.

Worked Example: Finite Variance for Each Observation Is Not Enough

Let $X_i$ be independent with $X_i\sim N(0,i)$. Each observation has a finite variance, but \[ \operatorname{Var}(S_n/n) =\frac{1}{n^2}\sum_{i=1}^n i =\frac{n+1}{2n}\longrightarrow\frac12, \] not zero. In fact, $S_n/n\sim N(0,(n+1)/(2n))$. For any fixed $\varepsilon>0$, \[ P(|S_n/n|>\varepsilon) =P\left(|N(0,1)|>\varepsilon\sqrt{\frac{2n}{n+1}}\right) \longrightarrow P(|N(0,1)|>\sqrt{2}\varepsilon)>0. \] So the averages do not converge in probability to zero. The issue is not a lack of pairwise independence or finite individual variances; the total variance grows too quickly for the weak-law bound to vanish.

A frequent mistake is to say, “The observations are pairwise independent, so their average converges to its mean.” Pairwise independence only supplies the variance identity. A weak-law conclusion also needs the variance of the average to vanish, and a conclusion about a fixed constant needs the average mean to approach that constant. Another mistake is to treat pairwise independence as mutual independence. That can invalidate arguments that require the full joint distribution, even though the variance calculation remains valid.

Key takeaway: For pairwise independent observations with finite second moments, the variance of the sum is the sum of the variances. A weak law follows when that sum is $o(n^2)$ and the average means converge to the target. Full mutual independence is unnecessary for this variance-based argument.

Check Your Understanding

Use the variance calculation and keep the mean of the average distinct from its random fluctuation.

State the difference between pairwise independence and mutual independence.
For pairwise independent $X_1,\ldots,X_n$ with finite second moments, what is $\operatorname{Var}(\sum_{i=1}^nX_i)$, and why?
If the average means tend to $c$, what additional variance condition in the theorem ensures convergence in probability to $c$?
In the alternating Bernoulli example, calculate the average mean when $n=2m+1$. Why must the bias be considered in a Chebyshev bound centered at $1/2$?
Can a sequence be pairwise independent without being mutually independent? Describe the feature of the sign-block example that demonstrates this.