Distribution-Specific and Distribution-Free Glivenko–Cantelli Properties

Two Different Uniformity Questions

A uniform law of large numbers asks whether empirical averages approximate population averages simultaneously across a function class. There is a second, distinct question: does the guarantee hold for one fixed sampling distribution, or uniformly over a family of possible distributions? The order of these quantifiers matters. A class can behave well under every fixed distribution while having no common convergence rate over all distributions.

Let $(\mathcal X,\mathcal A)$ be a measurable space, let $P$ be a probability distribution on it, and let $X_1,\ldots,X_n$ be independent observations with common distribution $P$. Write $P f=E_P[f(X)]$ for a measurable function $f$, and define the empirical average by

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

For a function class $\mathcal F$, the uniform deviation is $\sup_{f\in\mathcal F}|P_n f-Pf|$. In the definitions below, assume these suprema are measurable; the classes used in the examples are countable, so their suprema are measurable.

Definition: A class $\mathcal F$ of measurable functions is Glivenko–Cantelli for a fixed distribution $P$ if, under an i.i.d. sample from $P$, $$ \sup_{f\in\mathcal F}|P_n f-Pf|\xrightarrow{p}0. $$ It is almost-surely Glivenko–Cantelli for $P$ if the same convergence holds almost surely. For a family of distributions $\mathcal P$, the class is distribution-free Glivenko–Cantelli over $\mathcal P$ if, for every $\varepsilon>0$, $$ \sup_{P\in\mathcal P}P^n\left\{\sup_{f\in\mathcal F}|P_n f-Pf|>\varepsilon\right\}\longrightarrow 0. $$

The fixed-$P$ definition keeps the distribution unchanged as sample size grows. Distribution-free convergence allows the worst distribution in $\mathcal P$ to depend on $n$. That is a stronger requirement: it asks for one convergence guarantee that works across the entire family, including distributions that may change with sample size.

Finite Classes Have a Distribution-Free Bound

For a finite class of bounded functions, concentration for each function and a union bound give a uniform guarantee. This is a basic case in which the distinction between fixed-distribution and distribution-free convergence disappears: the result holds for every distribution on the sample space.

Theorem: Suppose $\mathcal F=\{f_1,\ldots,f_m\}$ is a finite class of measurable functions taking values in $[0,1]$. For every probability distribution $P$, every $n\geq 1$, and every $\varepsilon>0$, $$ P^n\left\{\max_{1\leq j\leq m}|P_n f_j-P f_j|>\varepsilon\right\} \leq 2m\exp(-2n\varepsilon^2). $$ Consequently, $\mathcal F$ is distribution-free Glivenko–Cantelli over the family of all probability distributions on $(\mathcal X,\mathcal A)$.

Proof. Fix $P$ and $j$. The random variables $f_j(X_1),\ldots,f_j(X_n)$ are independent, identically distributed, and lie in $[0,1]$. Hoeffding’s inequality for independent bounded random variables therefore gives

P^n\{|P_n f_j-P f_j|>\varepsilon\} \leq 2\exp(-2n\varepsilon^2).

If the maximum over $j$ exceeds $\varepsilon$, then at least one of the $m$ individual deviations exceeds $\varepsilon$. Applying the union bound gives

P^n\left\{\max_{1\leq j\leq m}|P_n f_j-P f_j|>\varepsilon\right\} \leq \sum_{j=1}^m P^n\{|P_n f_j-P f_j|>\varepsilon\} \leq 2m\exp(-2n\varepsilon^2).

The right-hand side does not depend on $P$, so it also bounds the supremum of the probability over all distributions. For fixed $\varepsilon>0$, it tends to zero as $n\to\infty$, proving distribution-free convergence in probability. Moreover, for fixed $\varepsilon>0$, the sum over $n$ of these bounds is finite. The first Borel–Cantelli lemma implies that deviations larger than $\varepsilon$ occur only finitely often almost surely. Applying this to $\varepsilon=1/r$ for positive integers $r$ proves almost-sure convergence for each fixed $P$. $\square$

Worked Example: A Numerical Bound for Four Functions

Suppose $\mathcal F$ contains four functions taking values in $[0,1]$. Find a sample size that guarantees, for every sampling distribution, that the probability of a uniform deviation greater than $0.1$ is at most $0.05$.

Here $m=4$, $\varepsilon=0.1$, and the theorem gives the upper bound

2m\exp(-2n\varepsilon^2) =8\exp(-0.02n).

We require $8\exp(-0.02n)\leq 0.05$. Taking logarithms and rearranging,

-0.02n\leq \log(0.05/8), \qquad n\geq \frac{\log(8/0.05)}{0.02} =\frac{\log(160)}{0.02} \approx 253.77.

Thus $n=254$ suffices according to this bound. This is a sufficient, not necessary, sample size: the actual deviation probability may be smaller. The guarantee is distribution-free because neither the calculation nor the theorem’s right-hand side uses $P$.

Worked Examples: Reading the Quantifiers

Worked Example: Two Functions Under a Specified Distribution

Let $\mathcal X=\{a,b,c\}$, with $P(a)=0.2$, $P(b)=0.3$, and $P(c)=0.5$. Consider $f_1=1_{\{a\}}$ and $f_2=1_{\{a,b\}}$, and the observed sample $(a,c,c,b,c)$. Calculate the two empirical deviations.

For $f_1$, one of the five observations is $a$, so $P_n f_1=1/5=0.2$. The population average is $P f_1=P(a)=0.2$, giving $|P_n f_1-P f_1|=0$.

For $f_2$, two observations are in $\{a,b\}$, so $P_n f_2=2/5=0.4$. Its population average is $P f_2=P(a)+P(b)=0.2+0.3=0.5$, giving $|P_n f_2-P f_2|=0.1$. The uniform deviation for these two functions on this sample is therefore $\max(0,0.1)=0.1$. This calculation describes one sample under one specified $P$; the finite-class theorem supplies a probability guarantee that holds for every $P$.

Worked Example: A Class Glivenko–Cantelli for Each Fixed Distribution

Let $\mathcal X$ be the positive integers and let $\mathcal F=\{f_k:k\geq1\}$, where $f_k(x)=1_{\{k\}}(x)$. For any fixed distribution $P$, write $p_k=P(\{k\})$. Show why the class is almost-surely Glivenko–Cantelli for that $P$, despite being infinite.

Fix a positive integer $K$. The functions $f_1,\ldots,f_K$ form a finite class, so the strong law of large numbers applied to each coordinate gives $\max_{1\leq k\leq K}|P_n f_k-p_k|\to0$ almost surely. The maximum converges because it is over finitely many quantities, each of which converges almost surely.

For $k>K$, let $T_K=\{K+1,K+2,\ldots\}$. Since $\{k\}\subseteq T_K$,

|P_n f_k-p_k| \leq P_n(T_K)+P(T_K).

For this fixed $K$, the strong law applied to $1_{T_K}$ gives $P_n(T_K)\to P(T_K)$ almost surely. Combining the finite part and the tail yields

\limsup_{n\to\infty}\sup_{k\geq1}|P_n f_k-p_k| \leq 2P(T_K) \quad\text{almost surely}.

As $K\to\infty$, the sets $T_K$ decrease to the empty set, so continuity of probability from above gives $P(T_K)\to0$. Taking the intersection of the probability-one events used for the countably many $K$ shows that the limsup is zero almost surely. The argument fixes $P$; it does not provide a bound uniform over all distributions. $\square$

Why Fixed-Distribution Convergence Need Not Be Uniform

The preceding example illustrates a fixed-distribution argument. The next construction makes the quantifier distinction explicit: a countable class is almost-surely Glivenko–Cantelli for every fixed distribution, but its worst-case deviation probability does not vanish when the distribution may vary with sample size.

Worked Example: A Moving Block That Defeats a Distribution-Free Guarantee

Let the sample space be a disjoint union of finite blocks $B_j$, with $|B_j|=j^3$. Let $\mathcal F$ contain $1_A$ for every subset $A$ of every single block $B_j$. For any fixed distribution $P$, this class is almost-surely Glivenko–Cantelli. To see this, fix $K$. There are only finitely many subsets of the blocks $B_1,\ldots,B_K$; the strong law applied to their indicators gives convergence of the maximum deviation over those subsets. For the remaining blocks, set $T_K=\bigcup_{j>K}B_j$. If $A\subseteq B_j$ with $j>K$, then

|P_n(A)-P(A)|\leq P_n(T_K)+P(T_K).

For fixed $K$, the strong law gives $P_n(T_K)\to P(T_K)$ almost surely. Therefore the limsup of the supremum over the entire class is at most $2P(T_K)$. Since $T_K$ decreases to the empty set, $P(T_K)\to0$, proving the asserted fixed-$P$ convergence.

Now, for each sample size $n$, let $Q_n$ be uniform on the block $B_n$, which has $n^3$ points. The probability that two of $n$ independent draws from $Q_n$ coincide is at most

\binom{n}{2}\frac{1}{n^3} =\frac{n-1}{2n^2},

by the union bound over pairs of draws. Thus, with probability at least $1-(n-1)/(2n^2)$, all observations are distinct. On that event, let $A\subseteq B_n$ be the set of the $n$ observed points. This subset is among the sets defining $\mathcal F$. Its empirical average is $P_n1_A=1$, whereas its population average under $Q_n$ is $Q_n1_A=n/n^3=1/n^2$. Hence the supremum deviation is at least $1-1/n^2$, and in particular exceeds $1/2$ for $n\geq2$. Consequently,

\sup_Q Q^n\left\{\sup_{f\in\mathcal F}|P_n f-Qf|>\frac12\right\} \geq 1-\frac{n-1}{2n^2}\longrightarrow1.

Here $Q$ ranges over all distributions on the sample space, and the empirical average inside the event is computed from the sample drawn under $Q$. The distribution $Q_n$ changes with $n$, which is permitted by the supremum. Thus fixed-distribution Glivenko–Cantelli convergence for every $P$ does not imply distribution-free convergence. $\square$

Interpretation and Common Pitfall

Distribution-free convergence is useful when a result must apply without knowing the sampling distribution, or when a guarantee must remain valid over a specified family of distributions. Finite classes of bounded functions provide such a guarantee directly through a union bound. For larger or infinite classes, additional structure or restrictions may be needed; fixed-distribution convergence alone does not supply a common bound.

Pitfall: swapping the quantifiers. From “for every fixed $P$, the deviation tends to zero” one might conclude that the supremum over $P$ of the deviation probabilities tends to zero. This does not follow: the rate or behavior can depend on $P$, and the worst-case $P$ can change with $n$.
Correction: Check the order in the definition. Distribution-free convergence takes $\sup_{P\in\mathcal P}$ at each sample size before taking the limit. A proof for each fixed $P$ does not establish that stronger statement.
Pitfall: confusing the two kinds of uniformity. The supremum over $f\in\mathcal F$ makes convergence uniform over functions, but it does not make the conclusion uniform over distributions.

Key takeaway: “Uniform over a function class” and “uniform over sampling distributions” are separate requirements. Finite bounded classes satisfy both through a distribution-independent concentration bound; for an infinite class, convergence for each fixed distribution may still fail to be uniform over distributions.

Check Your Understanding

Use the definitions and examples above to answer these questions.

In the distribution-free definition, which quantity is maximized over distributions, and at what stage does that supremum occur?
Why does the finite-class bound remain valid when the sampling distribution is unknown?
For four functions and $\varepsilon=0.1$, write the probability bound as a function of $n$.
In the moving-block example, why is the set of observed points a permissible choice of $A$ after the sample is drawn?
Explain why proving convergence for every fixed $P$ does not by itself establish a distribution-free convergence rate.