A Moving-Spike Failure of Uniform Convergence

Pointwise Convergence Is Not Uniform Convergence

A law of large numbers controls the empirical average of a fixed function. In statistical learning, however, the function of interest may be chosen after observing the sample: an estimator can select whichever function makes the empirical discrepancy largest. Convergence for each fixed function does not, by itself, control that sample-dependent choice.

We will make this distinction exact using indicator functions under the uniform distribution on $[0,1]$. Every fixed function in the class will obey the strong law, but for every sample there will be a function in the class whose empirical average is one and whose population average is as close to zero as desired.

Empirical Averages and Two Notions of Convergence

Let $X_1,\ldots,X_n$ be independent and identically distributed observations with distribution $P$. For a measurable function $f$ with finite expectation, write $Pf=E[f(X)]$ for its population average and

P_n f=\frac{1}{n}\sum_{i=1}^n f(X_i)

for its empirical average. For an indicator $f=1_A$, these are $P(A)$, the probability of the set $A$, and $P_n(A)$, the fraction of observations in $A$.

Definition: A class $\mathcal F$ has pointwise almost-sure convergence if, for every fixed $f\in\mathcal F$, $P_n f\to Pf$ almost surely. It has uniform almost-sure convergence if $$ \sup_{f\in\mathcal F}|P_n f-Pf|\xrightarrow{a.s.}0. $$ Uniform convergence requires one bound to hold across the entire class at each sample size. The function that makes the supremum large may therefore change with the sample.

Worked Example: A Fixed Interval

Suppose $X_i\sim\mathrm{Uniform}[0,1]$ and take the fixed interval $A=(1/4,1/2)$. Its length, and hence its probability, is $P(A)=1/2-1/4=1/4$. The indicator values $1_A(X_i)$ are independent Bernoulli random variables with success probability $1/4$, so their average is $P_n(A)$.

For instance, if 3 of 8 observations fall in $A$, then $P_8(A)=3/8$, and the absolute discrepancy is $|3/8-1/4|=|3/8-2/8|=1/8$. If 11 of 40 fall in $A$, then $P_{40}(A)=11/40$, and the discrepancy is $|11/40-10/40|=1/40$. These finite calculations illustrate the discrepancy; the strong law, rather than either particular sample, establishes convergence for this fixed interval.

A Class of Rational Intervals

Let $P$ be uniform (Lebesgue) probability on $[0,1]$. Let $\mathcal C$ consist of all finite unions of sets of the form $(a,b)\cap[0,1]$, where $a<b$ are rational numbers. Include the empty union. This is a countable class: there are countably many rational intervals and countably many finite lists of them. For each $A\in\mathcal C$, consider the indicator function $1_A$.

Each fixed $A$ has a fixed probability $P(A)$, and the observations $1_A(X_i)$ are independent Bernoulli variables with that probability. The following elementary argument gives their strong law and makes explicit the pointwise claim needed here.

Result: For any fixed measurable $A$, if $X_i$ are iid with $P(A)=p$, then $P_n(A)\to p$ almost surely.

Proof. Set $S_n=\sum_{i=1}^n1_A(X_i)$. At square sample sizes $k^2$, Chebyshev's inequality gives, for any $\varepsilon>0$,

P\left(\left|\frac{S_{k^2}}{k^2}-p\right|>\varepsilon\right) \leq \frac{\operatorname{Var}(S_{k^2})}{\varepsilon^2 k^4} =\frac{k^2p(1-p)}{\varepsilon^2 k^4} \leq \frac{1}{4\varepsilon^2 k^2}.

The right-hand side is summable over $k$. By the first Borel–Cantelli lemma, for each fixed $\varepsilon>0$, only finitely many of these deviations occur almost surely. Applying this to $\varepsilon=1,1/2,1/3,\ldots$ shows $S_{k^2}/k^2\to p$ almost surely.

For $k^2\leq n<(k+1)^2$, the counts are nondecreasing, so

\frac{S_{k^2}}{(k+1)^2} \leq \frac{S_n}{n} \leq \frac{S_{(k+1)^2}}{k^2}.

The left side equals $(S_{k^2}/k^2)\,k^2/(k+1)^2$, which tends to $p$. The right side equals $(S_{(k+1)^2}/(k+1)^2)\,(k+1)^2/k^2$, which also tends to $p$. The squeeze theorem gives $S_n/n\to p$ almost surely. $\square$

Applying this result to each fixed $A\in\mathcal C$ proves pointwise almost-sure convergence. In fact, because $\mathcal C$ is countable, the convergence holds for every $A\in\mathcal C$ on a single probability-one event: intersect the probability-one events for the individual sets. This stronger pointwise statement still will not give uniform convergence.

Worked Example: A Sample-Selected Union of Small Intervals

Suppose the observed sample is $0.13, 0.41, 0.77$. Take the rational intervals $(1/8,3/20)$, $(2/5,17/40)$, and $(3/4,4/5)$, and let $A$ be their union. The first interval contains $0.13$, the second contains $0.41$, and the third contains $0.77$. Thus all three observations lie in $A$, so $P_3(A)=3/3=1$.

The interval lengths are $3/20-1/8=1/40$, $17/40-2/5=1/40$, and $4/5-3/4=1/20$. The intervals are disjoint, so $P(A)=1/40+1/40+1/20=1/10$. The discrepancy is therefore $|P_3(A)-P(A)|=|1-1/10|=9/10$. Here $A$ was selected using the observed points; it is not a fixed set to which the pointwise strong law applies as the sample size grows.

The Uniform Failure

Theorem: For iid $X_i\sim\mathrm{Uniform}[0,1]$ and the countable class $\mathcal C$ of finite unions of rational intervals defined above, $$ \sup_{A\in\mathcal C}|P_n(A)-P(A)|=1 $$ for every finite sample $X_1,\ldots,X_n\in[0,1]$. Nevertheless, for every fixed $A\in\mathcal C$, $P_n(A)\to P(A)$ almost surely.

Proof. The fixed-set convergence was established above. For the uniform claim, fix any sample $x_1,\ldots,x_n\in[0,1]$ and any $\varepsilon>0$. Around each $x_i$, choose a rational-endpoint interval $I_i=(a_i,b_i)\cap[0,1]$ containing $x_i$ and having length less than $\varepsilon/n$. Such intervals exist because rational numbers are dense; for an observation at an endpoint of $[0,1]$, an interval with an endpoint outside $[0,1]$ can contain it after intersection with $[0,1]$.

The finite union $A=\bigcup_{i=1}^n I_i$ belongs to $\mathcal C$, contains every observation, and satisfies

P_n(A)=1,\qquad P(A)\leq\sum_{i=1}^n P(I_i)<n\frac{\varepsilon}{n}=\varepsilon.

Consequently, $|P_n(A)-P(A)|=1-P(A)>1-\varepsilon$. Since this holds for every $\varepsilon>0$, the supremum over $A\in\mathcal C$ is at least 1. It is also at most 1 because both $P_n(A)$ and $P(A)$ lie in $[0,1]$. The supremum is therefore exactly 1. The class is countable, so this supremum is measurable; moreover, the construction shows the equality for each finite sample, not just almost surely. $\square$

Worked Example: Four Observations and a Small Union

Consider the sample $0.13,0.41,0.77,0.92$. The four rational intervals $(1/8,5/32)$, $(13/32,7/16)$, $(3/4,25/32)$, and $(29/32,15/16)$ each have length $1/32$ and contain, respectively, one of the four observations. Their union $A$ therefore has $P(A)=4/32=1/8$, since they are disjoint, while $P_4(A)=4/4=1$. The discrepancy is $1-1/8=7/8$.

More generally, for any $n$ observed points, choosing each interval to have length less than $1/n^2$ gives a union with $P(A)<1/n$ and $P_n(A)=1$. The resulting discrepancy exceeds $1-1/n$. The theorem is stronger: at each fixed $n$, the supremum is 1 because the intervals can be made arbitrarily short.

Not Every Moving Set Causes Failure

The counterexample does not say that every sequence of changing sets defeats convergence. The crucial feature is that the set is selected after seeing the sample and can cover all of its observations. A deterministic sequence of shrinking sets provides a useful contrast.

Worked Example: A Deterministic Shrinking Interval

For $X_i\sim\mathrm{Uniform}[0,1]$, let $B_n=[0,1/n]$, chosen in advance rather than from the data. Then $P(B_n)=1/n$, and $P_n(B_n)$ is an average of $n$ independent Bernoulli variables with success probability $1/n$. Its expectation is $1/n$, and its variance is

\operatorname{Var}(P_n(B_n)) =\frac{(1/n)(1-1/n)}{n} =\frac{n-1}{n^3} \leq \frac{1}{n^2}.

For any fixed $\varepsilon>0$, Chebyshev's inequality therefore gives

P\left(|P_n(B_n)-P(B_n)|>\varepsilon\right) \leq \frac{\operatorname{Var}(P_n(B_n))}{\varepsilon^2} \leq \frac{1}{n^2\varepsilon^2}\longrightarrow 0.

Thus the discrepancy for this particular deterministic sequence tends to zero in probability. For example, at $n=10$, $P(B_{10})=0.1$ and the variance of $P_{10}(B_{10})$ is $9/1000=0.009$. This does not assert a uniform law over a rich class: it controls only the one set $B_n$ specified at each sample size.

What the Counterexample Teaches

The difference is a change in the order of the quantifiers. Pointwise convergence says: choose a fixed $A$, then let the sample size grow. Uniform convergence says: at every sample size, control all $A$ at once, including one chosen to fit the observed data. In symbols, knowing that each fixed discrepancy vanishes does not imply that the supremum of the discrepancies vanishes.

This matters in learning because empirical objectives are often optimized over a class: the chosen predictor or decision rule depends on the training sample. A guarantee for each predictor considered separately does not automatically guarantee that the data-selected predictor has a small population-to-empirical discrepancy. Uniform control is a stronger requirement, not a rearrangement of the pointwise law of large numbers.

A common mistake is to argue, “Every fixed set obeys the strong law, so the largest discrepancy over the class must also go to zero.” The fixed-set result holds the set constant while $n$ grows. In the counterexample, for each $n$, the union $A$ is built around that sample’s observations; the function changes with the data. The pointwise result has no bound that is uniform over these changing choices.

Key takeaway: A class can satisfy the strong law for every fixed indicator and still have maximal empirical discrepancy at every sample size. To pass from pointwise to uniform convergence, one needs additional control on the function class; pointwise convergence alone is insufficient.

Check Your Understanding

Use the definitions and construction above to answer the following questions.

For a fixed measurable set $A$, what random variables are being averaged in $P_n(A)$, and what is their expectation?
Why does countability of $\mathcal C$ allow the fixed-set strong laws to hold on one common probability-one event?
In the moving-union proof, why can $P(A)$ be made arbitrarily small while $P_n(A)=1$?
Explain why the equality of the supremum to 1 does not contradict convergence for each fixed $A$.
What is different about the deterministic sequence $B_n=[0,1/n]$ compared with the sample-selected union?