Etemadi's Strong Law Under Pairwise Independence

Why Pairwise Independence Is Enough

A strong law says that sample averages converge almost surely, not merely with high probability at a fixed sample size. For independent observations, standard strong-law arguments can use independence of whole groups of variables. Etemadi’s strong law reaches the same conclusion with the weaker assumption of pairwise independence: every two distinct observations are independent, but larger collections need not be mutually independent.

The moment condition is correspondingly economical. Finite absolute first moment suffices; finite variance is not required. The proof below truncates large observations, controls the resulting variances along a geometric sequence, and uses monotonicity to fill the gaps between those sample sizes.

Definition: Random variables $X_1,X_2,\ldots$ are pairwise independent and identically distributed if they have the same distribution and every pair $X_i,X_j$, $i\ne j$, is independent. This does not assert mutual independence of every finite collection. The finite absolute first moment condition is $E[|X_1|]<\infty$.

Theorem (Etemadi’s strong law): If $X_1,X_2,\ldots$ are pairwise independent and identically distributed, and $E[|X_1|]<\infty$, then, with $\mu=E[X_1]$, $$ \frac{1}{n}\sum_{i=1}^n X_i \xrightarrow{a.s.} \mu. $$

Truncation Along a Geometric Sequence

We first prove the result for nonnegative observations $W_i$ that are pairwise independent, identically distributed, and satisfy $E[W_1]<\infty$. Fix a number $r>1$ and set $a_m=\lfloor r^m\rfloor$. We consider sufficiently large $m$, so that the $a_m$ are strictly increasing. For a fixed $m$, truncate each of the first $a_m$ observations at the common threshold $a_m$:

Z_{i,m}=W_i\mathbf{1}_{\{W_i\leq a_m\}},\qquad \mu_m=E[Z_{1,m}],\qquad v_m=\operatorname{Var}(Z_{1,m}).

The truncated observations remain pairwise independent: applying a measurable function separately to each variable preserves the independence of each pair. Thus their centered sum has variance $a_m v_m$. Two summability bounds make this truncation useful.

Lemma: For fixed $r>1$ and $a_m=\lfloor r^m\rfloor$, if $W\geq0$ and $E[W]<\infty$, then $$ \sum_m a_m P(W>a_m)<\infty,\qquad \sum_m \frac{E[W^2\mathbf{1}_{\{W\leq a_m\}}]}{a_m}<\infty. $$

To verify both bounds, note that the $a_m$ eventually grow geometrically: there are constants $c,C>0$ such that $c r^m\leq a_m\leq C r^m$ for all sufficiently large $m$. Consequently, for each fixed $w\geq0$, the sum of the $a_m$ below $w$ is at most $C_r w$, for some finite constant $C_r$ depending only on $r$. Also, the sum of $1/a_m$ over the $a_m$ at least $w$ is at most $C_r/w$ when $w\geq1$. When $0\leq w<1$, the sum is bounded by a constant, so $w^2$ times that sum is at most a constant times $w$. In either case,

\sum_m \frac{w^2}{a_m}\mathbf{1}_{\{w\leq a_m\}}\leq C_r w.

Apply these pointwise bounds with $w=W$ and take expectations. The first gives the tail-probability sum, since $a_mP(W>a_m)=E[a_m\mathbf{1}_{\{W>a_m\}}]$. The second gives the truncated second-moment sum. Both are finite because $E[W]<\infty$. This proves the lemma.

Convergence on the Geometric Subsequence

Write $S_n^W=\sum_{i=1}^n W_i$. The probability that truncation changes any of the first $a_m$ observations is bounded by the union bound:

P\bigl(\text{some }i\leq a_m\text{ has }W_i>a_m\bigr) \leq a_m P(W_1>a_m).

These probabilities are summable by the lemma. Also, Chebyshev’s inequality and pairwise independence give, for every $\varepsilon>0$,

P\left(\left|\sum_{i=1}^{a_m}(Z_{i,m}-\mu_m)\right|>\varepsilon a_m\right) \leq \frac{a_m v_m}{\varepsilon^2a_m^2} \leq \frac{E[W_1^2\mathbf{1}_{\{W_1\leq a_m\}}]}{\varepsilon^2a_m}.

Here $v_m\leq E[W_1^2\mathbf{1}_{\{W_1\leq a_m\}}]$. The right-hand side is summable over $m$, again by the lemma. The first Borel–Cantelli lemma therefore implies that, almost surely, only finitely many truncation changes occur and the centered truncated sums divided by $a_m$ converge to zero. Applying this conclusion for $\varepsilon=1,1/2,1/3,\ldots$ gives convergence to zero rather than just an eventual bound at one fixed $\varepsilon$.

Since $Z_{i,m}=W_i$ for every $i\leq a_m$ whenever no truncation change occurs, and since $\mu_m\uparrow E[W_1]=\mu$ by monotone convergence, we obtain

\frac{S_{a_m}^W}{a_m} =\frac{1}{a_m}\sum_{i=1}^{a_m}(Z_{i,m}-\mu_m)+\mu_m \xrightarrow{a.s.}\mu.

Filling the Gaps and Handling Signed Observations

For nonnegative observations, the partial sums are increasing. If $a_m\leq n\leq a_{m+1}$, then

\frac{S_{a_m}^W}{a_{m+1}} \leq \frac{S_n^W}{n} \leq \frac{S_{a_{m+1}}^W}{a_m}.

This is a blockwise maximal bound: every average in the block is bounded using its two endpoint sums. It is also a probability bound when combined with endpoint estimates. For example, for $t>0$,

P\left(\max_{a_m\leq n\leq a_{m+1}}\frac{S_n^W}{n}>t\right) \leq P(S_{a_{m+1}}^W>a_m t).

The almost-sure endpoint convergence already proved shows that the lower and upper bounds on the block averages have limiting values $\mu/r$ and $r\mu$, respectively, because $a_{m+1}/a_m\to r$. Thus, for this fixed $r$, the lower limit of the averages is at least $\mu/r$ and the upper limit is at most $r\mu$, almost surely. Apply the argument for the countable sequence $r_j=1+1/j$, $j=1,2,\ldots$, and intersect the resulting probability-one events. Letting $j\to\infty$ forces both limits to equal $\mu$. This proves the strong law for nonnegative observations.

For real-valued $X_i$, define $X_i^+=\max(X_i,0)$ and $X_i^-=\max(-X_i,0)$. Each sequence is pairwise independent and identically distributed, and both have finite expectation because $E[|X_1|]<\infty$. Apply the nonnegative result to each sequence and subtract their almost-sure limits. Since $X_i=X_i^+-X_i^-$ and $E[X_1]=E[X_1^+]-E[X_1^-]$, this proves Etemadi’s theorem. $\square$

Worked Examples

Worked Example: Bernoulli Observations

Suppose $X_i$ are pairwise independent Bernoulli observations with $P(X_i=1)=0.3$ and $P(X_i=0)=0.7$. They are nonnegative and have mean $E[X_i]=0.3$, so Etemadi’s theorem gives

\frac{1}{n}\sum_{i=1}^n X_i\xrightarrow{a.s.}0.3.

The truncation calculations are particularly simple. For every integer $m\geq0$, $a_m=\lfloor r^m\rfloor\geq1$, so truncation at $a_m$ changes no observation. Thus $Z_{i,m}=X_i$, $\mu_m=0.3$, and $v_m=0.3(0.7)=0.21$. At the geometric sample size $a_m$, Chebyshev’s bound is

P\left(\left|\frac{1}{a_m}\sum_{i=1}^{a_m}X_i-0.3\right|>\varepsilon\right) \leq \frac{0.21}{\varepsilon^2a_m}.

The right-hand side is summable in $m$ because $a_m$ grows geometrically. Monotonicity of the nonnegative partial sums then extends the convergence from these sample sizes to all $n$.

Worked Example: Finite Mean but Infinite Variance

Let $X_i$ have the Pareto distribution with density $f(x)=\frac{3}{2}x^{-5/2}$ for $x\geq1$, and suppose the observations are pairwise independent. Direct integration gives

E[X_i]=\frac{3}{2}\int_1^\infty x^{-3/2}\,dx=3, \qquad E[X_i^2]=\frac{3}{2}\int_1^\infty x^{-1/2}\,dx=\infty.

The theorem applies despite the infinite variance. For a dyadic threshold $a_m=2^m$, the tail probability is $P(X_i>a_m)=a_m^{-3/2}$, so the probability of a truncation change among the first $a_m$ observations is at most

a_mP(X_i>a_m)=2^{-m/2}.

For $a_m\geq1$, the truncated second moment is

E[X_i^2\mathbf{1}_{\{X_i\leq a_m\}}] =\frac{3}{2}\int_1^{a_m}x^{-1/2}\,dx =3(\sqrt{a_m}-1).

Consequently, the centered-sum probability at the endpoint is bounded by

P\left(\left|\sum_{i=1}^{a_m}(Z_{i,m}-\mu_m)\right|>\varepsilon a_m\right) \leq\frac{3(\sqrt{a_m}-1)}{\varepsilon^2a_m} \leq\frac{3}{\varepsilon^2}2^{-m/2}.

Both bounds are summable in $m$. The theorem therefore yields $n^{-1}\sum_{i=1}^nX_i\xrightarrow{a.s.}3$, even though variance-based strong laws for the original observations are unavailable.

Worked Example: Pairwise but Not Mutual Independence

For each block $j$, let $U_j$ and $V_j$ be independent fair bits, with different blocks independent, and define

X_{3j-2}=U_j,\qquad X_{3j-1}=V_j,\qquad X_{3j}=U_j\mathbin{\oplus}V_j,

where $\oplus$ denotes addition modulo 2. Each variable is Bernoulli with success probability $1/2$. Within a block, each pair is independent: for example, $U_j$ and $U_j\oplus V_j$ take each of their four possible ordered pairs with probability $1/4$. Variables from different blocks are independent as well. Thus the entire sequence is pairwise independent and identically distributed.

The three variables in a block are not mutually independent, because $X_{3j}=X_{3j-2}\oplus X_{3j-1}$ with probability one. Nevertheless, $E[|X_1|]=1/2<\infty$, so Etemadi’s theorem gives $n^{-1}\sum_{i=1}^nX_i\xrightarrow{a.s.}1/2$. The theorem does not require independence of every finite group.

Common Pitfall and Why the Proof Is Structured This Way

A tempting but invalid shortcut is to treat pairwise independence as mutual independence and invoke a maximal inequality whose hypotheses require independent groups. Pairwise independence does give zero covariance between distinct observations, which is enough for the variance calculation of each truncated endpoint sum. It does not, by itself, make a whole block of observations independent of another collection of variables.

The proof avoids that shortcut. Truncation makes the endpoint variances manageable; Chebyshev’s inequality and Borel–Cantelli control the geometric sample sizes; and nonnegativity supplies the blockwise bounds between them. Splitting a signed observation into its positive and negative parts preserves pairwise independence and lets the same monotonicity argument handle general real-valued observations. Finite absolute first moment is essential to the summability estimates: it controls both the frequency of large observations and the accumulated truncated second moments.

Key takeaway: Pairwise independence and $E[|X_1|]<\infty$ suffice for almost-sure convergence of the sample average. The proof uses truncation and geometric blocking, not an assumption of mutual independence or finite variance.

Check Your Understanding

Use the proof’s truncation and blocking steps to answer the following.

What does pairwise independence assert, and how does it differ from mutual independence?
Why does truncating each $W_i$ at a fixed threshold preserve pairwise independence?
For nonnegative observations, why can convergence along a geometric subsequence be extended by using both endpoint sums?
Why does the theorem apply to the Pareto distribution in the worked example even though its variance is infinite?
How does decomposing $X_i$ into $X_i^+$ and $X_i^-$ extend the nonnegative result to signed observations?