Uniform law of large numbers (ULLN)

Let $X_1,X_2,\dots$ be independent and identically distributed with probability law $P$, and let $\mathcal{G}$ be a class of measurable $P$-integrable functions. Write $P_{n}g=n^{-1}{\sum }_{i=1}^{n}g(X_i)$ and $Pg=\mathbb{E}g(X_1)$. A uniform law of large numbers concernswith measurability of the supremum assumed. A uniform weak law uses convergence in probability; a uniform strong law uses almost sure convergence. The mode and sampling assumptions are part of the statement.

For a finite class, the strong law of large numbers for each function holds simultaneously and gives the uniform strong law. For infinite classes, pointwise convergence alone is insufficient. For example, let $P$ be the uniform distribution on $[0,1]$ and take indicators of all finite subsets. Each fixed function has expectation zero and empirical mean tending to zero almost surely. Yet for every sample the finite set $\{X_1,\dots ,X_n\}$ belongs to the class and its empirical mean is one. The displayed supremum is therefore one for every $n$.

Conditions such as finite bracketing of a function class at every positive width control this complexity. The Glivenko-Cantelli theorem gives the uniform strong law for indicators of half-lines, the class determining the empirical distribution function.

A measurable-function class is pointwise separable if it has a countable subclass such that every member is the pointwise limit of a sequence from that subclass. With an integrable common envelope, dominated convergence theorem makes both empirical averages and population expectations converge along each such sequence. Thus the supremum of the absolute empirical errors equals the supremum over the countable subclass and is measurable. A finite integrable bracketing cover provides an integrable envelope by taking the maximum absolute value of all its endpoints.

A bracket $[\ell ,u]$ contains every measurable function $h$ satisfying $\ell \le h\le u$ pointwise. For a Probability measure $P$, its $L^1(P)$ width is $P(u-\ell )$, with integrable endpoints. Finite bracketing at every positive width is a sufficient complexity condition for a uniform law of large numbers. Pointwise inequalities, or inequalities outside a single common null set, allow empirical inequalities to hold simultaneously throughout the class.

A measurable function $M$ is an integrable envelope of a function class for a class $\mathcal{H}$ under a probability law $P$ if $|h(x)|\le M(x)$ for every $h\in \mathcal{H}$ and $PM<\infty$. Such an envelope permits the dominated convergence theorem to control shrinking function brackets.

Suppose an integrable measurable-function class can be covered by finitely many function brackets of every positive $L^1(P)$ width. For an independent sample with common law $P$, the empirical measure satisfies ${\sup }_h|P_{n}h-Ph|\to 0$ on a common probability-one event. For one finite $\epsilon$-cover, the supremum is bounded by $\epsilon$ plus the largest empirical error among its endpoints. The strong law of large numbers makes that finite maximum vanish. Taking a countable sequence of widths decreasing to zero proves the assertion. A measurable supremum can be obtained from a pointwise separable function class; otherwise the probability-one-event formulation expresses the same pathwise conclusion.

Let $\Theta$ be a compact metric space, let $q(\theta ,x)$ be continuous in $\theta$ for each $x$ and measurable in $x$ for each $\theta$, and assume the envelope $M(x)={\sup }_{\theta \in \Theta }|q(\theta ,x)|$ is integrable under $P$. For an independent and identically distributed sample,Compact metric structure supplies both finite parameter nets and countable dense sets, so the relevant suprema can be treated measurably under these continuity assumptions.

For a proof, define ${\omega }_{\delta }(x)={\sup }_{d(\theta ,\eta )\le \delta }|q(\theta ,x)-q(\eta ,x)|$. Uniform continuity on the compact parameter set gives ${\omega }_{\delta }(x)\to 0$ for each $x$, and ${\omega }_{\delta }\le 2M$. Thus $P{\omega }_{\delta }\to 0$ by the dominated convergence theorem. At a finite $\delta$-net of centers, apply the strong law of large numbers to every center and to ${\omega }_{\delta }$. For a nearby center $\eta$,The limiting supremum is at most $2P{\omega }_{\delta }$. A countable sequence $\delta \downarrow 0$ proves the claim. Equivalently, these center functions and their oscillation envelopes give the function brackets used in the uniform strong law from finite L1 bracketing.

For independent and identically distributed real observations $X_i$ with cumulative distribution function $F$, the empirical distribution functionsatisfies the Glivenko-Cantelli theoremThe population law may have atoms; continuity of $F$ is not required. The conclusion is uniform over every threshold, strengthening the separate strong laws for fixed thresholds.^[ref]

Here is a proof using inverse transform sampling. First take iid uniforms and their empirical CDF $G_n$. At the finitely many grid points $j/m$, the strong law of large numbers gives $G_n(j/m)\to j/m$ simultaneously. Monotonicity bounds the discrepancy between grid points by the largest grid discrepancy plus $1/m$. Taking countably many $m\to \infty$ proves uniform convergence on $[0,1]$.

For general $F$, construct $X_i=F^{-1}(U_i)$ using the quantile function. Then $X_i\le x$ exactly when $U_i\le F(x)$, so $F_n(x)=G_n(F(x))$ and the general supremum is bounded by the uniform one. This also handles jumps of $F$. The theorem does not apply merely because an empirical CDF was formed: for repeated copies of the same nondegenerate random observation, the empirical CDF does not approach its population law in this way.

For a cumulative distribution function $G$, let $Q(u)=\inf \{x:G(x)\ge u\}$, $0<u<1$. Right continuity gives $Q(u)\le x$ exactly when $u\le G(x)$, including at atoms. Thus applying $Q$ to independent uniform variables $U_i$ constructs an independent sample with distribution function $G$. Its empirical distribution function is $G_n(x)=F_n(G(x))$, where $F_n$ is the uniform-sample empirical distribution function. Consequently ${\sup }_x|G_n(x)-G(x)|\le {\sup }_{t\in [0,1]}|F_n(t)-t|$. For the uniform sample, monotonicity and a grid of mesh $1/m$ bound the last supremum by the largest error at grid points plus $1/m$. The strong law of large numbers on the countable union of all such grids proves the almost-sure limit. This construction proves the theorem for distributions with atoms as well as continuous distributions.