Dyadic Blocking Proof of the Finite-Variance Strong Law

Why Check Only Dyadic Sample Sizes?

A weak law controls the probability of a large sample-average error at each fixed sample size. A strong law asks for more: with probability one, the averages must eventually stay close to their target at all sample sizes. For IID observations with finite variance, Chebyshev’s inequality gives a useful bound at each size, but its generic bound is not summable over all positive integers. The dyadic blocking proof resolves this by checking a geometrically spaced sequence of sample sizes and controlling the fluctuations between consecutive checks.

The proof has two distinct parts. First, Chebyshev’s inequality controls the partial sums at \(2^k\). Second, Kolmogorov’s maximal inequality controls the largest partial-sum increment from \(2^k\) through the next block. Both resulting probability bounds decrease geometrically in \(k\), so the first Borel–Cantelli lemma applies.

Setup and the Main Theorem

Definition: Let \(X_1,X_2,\ldots\) be IID random variables with \(E[X_1]=\mu\) and \(\operatorname{Var}(X_1)=\sigma^2<\infty\). Define the centered variables \(Y_i=X_i-\mu\) and partial sums \(S_n=\sum_{i=1}^n Y_i\). The sample average is \(\bar X_n=n^{-1}\sum_{i=1}^n X_i=\mu+S_n/n\).

Finite variance ensures that the mean \(\mu\) is finite. The variables \(Y_i\) are independent, have mean zero, and have variance \(\sigma^2\). For independent mean-zero variables \(Y_1,\ldots,Y_m\) with finite variances, Kolmogorov’s maximal inequality states that, for every \(t>0\),

P\left(\max_{1\le j\le m}\left|\sum_{i=1}^jY_i\right|\ge t\right) \le \frac{\sum_{i=1}^m\operatorname{Var}(Y_i)}{t^2}.

We use this inequality in its standard form for each block of centered observations. We also use the first Borel–Cantelli lemma: if \(\sum_{k=1}^{\infty}P(A_k)<\infty\), then \(P(A_k\text{ infinitely often})=0\).

Theorem (finite-variance IID strong law): If \(X_1,X_2,\ldots\) are IID and \(E[X_1^2]<\infty\), then \( \bar X_n\xrightarrow{a.s.}\mu=E[X_1]\).

Worked Examples: Identifying the Variance Assumption

Worked Example: Bernoulli Observations

Suppose \(X_i\sim\operatorname{Bernoulli}(0.3)\), independently. Then \(E[X_i]=0.3\), and \(\operatorname{Var}(X_i)=0.3(1-0.3)=0.21\). The theorem therefore gives \(\bar X_n\xrightarrow{a.s.}0.3\).

For example, take the deviation threshold \(\varepsilon=0.1\). At dyadic size \(2^k\), Chebyshev’s inequality gives

P\left(\frac{|S_{2^k}|}{2^k}>0.1\right) \le \frac{0.21}{(0.1)^2\,2^k} =\frac{21}{2^k}.

The same bound will apply to the maximum increment across the next block. Since \(\sum_{k=0}^{\infty}21/2^k=42<\infty\), each kind of bad event occurs only finitely often almost surely. The bound may exceed one for small \(k\); that does not invalidate it, and only its summability matters.

Worked Example: A Normal Model

Let \(X_i\sim N(2,4)\) independently, so the mean is \(2\) and the variance is \(4\). With \(\varepsilon=0.25\), the endpoint bound is

P\left(\left|\bar X_{2^k}-2\right|>0.25\right) =P\left(\frac{|S_{2^k}|}{2^k}>0.25\right) \le \frac{4}{(0.25)^2\,2^k} =\frac{64}{2^k}.

For the increment maximum in the block after \(2^k\), Kolmogorov’s inequality gives the same upper bound \(64/2^k\). Both bound sequences sum to a finite number over \(k\). Thus the averages at all sample sizes, not just at dyadic sizes, converge almost surely to \(2\).

Worked Example: Exponential Observations

Suppose \(X_i\) are IID exponential random variables with rate \(2\), so their density is \(f(x)=2e^{-2x}\) for \(x\ge0\). Integration by parts gives \(E[X_i]=1/2\) and \(E[X_i^2]=1/2\), hence \(\operatorname{Var}(X_i)=1/2-(1/2)^2=1/4\). For the threshold \(\varepsilon=0.05\), the endpoint bound is

P\left(\left|\bar X_{2^k}-\frac12\right|>0.05\right) \le \frac{1/4}{(0.05)^2\,2^k} =\frac{100}{2^k}.

The corresponding bound for the maximum increment is also \(100/2^k\), and \(\sum_{k=0}^{\infty}100/2^k=200<\infty\). The theorem applies even though the exponential distribution is unbounded: bounded observations are not required, only a finite second moment.

The Dyadic Blocking Proof

For each integer \(k\ge0\), the endpoint partial sum has variance \(\operatorname{Var}(S_{2^k})=2^k\sigma^2\), because its summands are independent and each has variance \(\sigma^2\). Chebyshev’s inequality therefore yields, for every \(\varepsilon>0\),

P\left(\frac{|S_{2^k}|}{2^k}>\varepsilon\right) \le \frac{\operatorname{Var}(S_{2^k})}{\varepsilon^2 2^{2k}} =\frac{\sigma^2}{\varepsilon^2 2^k}.

These bounds are summable in \(k\), since \(\sum_{k=0}^{\infty}2^{-k}=2\). Borel–Cantelli implies that, for each fixed \(\varepsilon>0\), the event \(|S_{2^k}|/2^k>\varepsilon\) occurs only finitely often almost surely.

Now control the observations after each endpoint. Define the largest within-block increment

M_k=\max_{1\le j\le 2^k} \left|\sum_{i=2^k+1}^{2^k+j}Y_i\right|.

The \(2^k\) variables in this block are independent, have mean zero, and have total variance \(2^k\sigma^2\). Applying Kolmogorov’s maximal inequality with threshold \(\varepsilon 2^k\) gives

P\left(\frac{M_k}{2^k}>\varepsilon\right) \le \frac{2^k\sigma^2}{\varepsilon^2 2^{2k}} =\frac{\sigma^2}{\varepsilon^2 2^k}.

This is again summable in \(k\), so Borel–Cantelli implies that \(M_k/2^k>\varepsilon\) only finitely often almost surely, for each fixed \(\varepsilon>0\).

Apply Borel–Cantelli at endpoints.
For any fixed \(\varepsilon>0\), the endpoint deviation probabilities have a finite sum. Almost surely, \(|S_{2^k}|/2^k\le\varepsilon\) for all sufficiently large \(k\).

Apply Borel–Cantelli to block maxima.
The probabilities that \(M_k/2^k>\varepsilon\) also have a finite sum. Almost surely, \(M_k/2^k\le\varepsilon\) for all sufficiently large \(k\).

Combine the two controls.
Every index between consecutive dyadic endpoints is the endpoint sum plus an increment bounded by the corresponding block maximum.

To make the almost-sure statements hold as the tolerance tends to zero, apply them for the countable sequence \(\varepsilon=1/r\), \(r=1,2,\ldots\), and intersect the resulting probability-one events. On this intersection, both \(|S_{2^k}|/2^k\) and \(M_k/2^k\) tend to zero.

Proof of the theorem: Work on the probability-one event just obtained. For any \(n\ge1\), choose \(k\) so that \(2^k\le n<2^{k+1}\). Then \(n=2^k+j\) for some \(0\le j<2^k\). If \(j=0\), the increment is zero; otherwise its absolute value is at most \(M_k\). Since \(n\ge2^k\),

\frac{|S_n|}{n} \le \frac{|S_{2^k}|+M_k}{2^k} =\frac{|S_{2^k}|}{2^k}+\frac{M_k}{2^k}.

As \(n\to\infty\), its block index \(k\to\infty\), and the right-hand side tends to zero on this event. Hence \(S_n/n\to0\) almost surely. Because \(\bar X_n=\mu+S_n/n\), it follows that \(\bar X_n\to\mu\) almost surely. \(\square\)

Why the Blocking Step Is Necessary

For any fixed \(\varepsilon>0\), Chebyshev’s inequality at an arbitrary sample size \(n\) gives

P\left(\frac{|S_n|}{n}>\varepsilon\right) \le \frac{\sigma^2}{\varepsilon^2 n}.

The Chebyshev upper bounds are proportional to \(1/n\), so those bounds are not summable over all positive integers. Thus, applying the first Borel–Cantelli lemma using these bounds at every sample size does not prove almost-sure convergence. This does not assert that the actual deviation probabilities are nonsummable: they may be smaller than their Chebyshev bounds. The point is that this particular generic bound is insufficient for that direct Borel–Cantelli argument.

At dyadic sizes, the endpoint bounds form a geometric series. The maximal inequality supplies a second geometric series that covers every intermediate index. The blocks overlap neither in their increments nor in their probability accounting, and each has length \(2^k\), the same order as its starting index. That balance makes the block fluctuation bound proportional to \(2^{-k}\) as well.

Finite variance enters directly through the endpoint variance and the total variance within each block. Independence is needed for the variance sums and for the maximal inequality. If \(\sigma^2=0\), then \(X_i=\mu\) almost surely for each \(i\), so the conclusion holds immediately; the displayed bounds also reduce to zero.

Common Pitfall

Common mistake: “Chebyshev gives a bound of order \(1/n\), so the probabilities of deviations are not summable, and therefore the averages cannot converge almost surely.” This confuses an upper bound with the actual probabilities and draws a conclusion the bound does not justify. The correct statement is that the Chebyshev upper bounds are not summable over all \(n\), so this direct use of Borel–Cantelli does not establish the strong law. Dyadic blocking instead produces summable bounds for both endpoints and within-block maxima, which is enough to prove almost-sure convergence.

Check Your Understanding

Use the proof structure to answer these questions.

Why does the endpoint Chebyshev bound at sample size \(2^k\) have order \(2^{-k}\)?
Which random quantity controls the fluctuation from \(S_{2^k}\) to \(S_{2^k+j}\) for all \(1\le j\le2^k\)?
State precisely what the first Borel–Cantelli lemma implies when the probabilities of a sequence of events have finite sum.
Why does a nonsummable sequence of Chebyshev upper bounds not show that the actual deviation probabilities are nonsummable?
Where are independence and finite variance used in the dyadic blocking argument?