Uniform Empirical-CDF Convergence by Finite Grids

Why a Finite Grid Can Control an Entire CDF

The empirical distribution function \(F_n\) is built from the observations, so it changes with the sample size and has jumps at observed values. Pointwise convergence says that for each fixed \(x\), \(F_n(x)\) approaches the population value \(F(x)\). Uniform convergence is stronger: it requires the largest discrepancy over all real \(x\) to become small. The key idea here is to check errors at finitely many carefully chosen points, then use monotonicity to control the values between them.

Continuity of \(F\) makes it possible to choose grid points that divide the population probability into nearly equal increments. The strong law controls the empirical CDF at those finitely many points. As the grid is refined, the probability increment between adjacent points becomes arbitrarily small, which turns finite-grid control into uniform control.

Definition: For IID real-valued observations \(X_1,X_2,\ldots\) with common CDF \(F\), the empirical CDF based on the first \(n\) observations is

F_n(x)=\frac{1}{n}\sum_{i=1}^n \mathbf{1}\{X_i\le x\}, \qquad x\in\mathbb{R}.

Here \(\mathbf{1}\{X_i\le x\}\) equals 1 when \(X_i\le x\) and 0 otherwise. The uniform error is \(\sup_{x\in\mathbb{R}}|F_n(x)-F(x)|\).

For a fixed \(x\), the indicators \(\mathbf{1}\{X_i\le x\}\) are IID Bernoulli random variables with mean \(F(x)\). The strong law of large numbers therefore gives \(F_n(x)\xrightarrow{a.s.}F(x)\). This is pointwise convergence: the exceptional probability-zero set can depend on \(x\). The finite-grid argument will first use only finitely many fixed points at a time, then handle the required countably many grids together.

A Deterministic Bound from Grid Errors

Suppose \(F\) is continuous. Fix an integer \(m\ge 2\). Since a CDF tends to 0 at \(-\infty\) and to 1 at \(+\infty\), continuity ensures that for each \(j=1,\ldots,m-1\), there is a real number \(q_j\) satisfying \(F(q_j)=j/m\). These points are strictly increasing: if \(j<k\), the inequality \(q_j\ge q_k\) would contradict the monotonicity of \(F\), because \(F(q_j)=j/m<k/m=F(q_k)\).

Define the largest error at the selected grid points by

D_{n,m}=\max_{1\le j\le m-1}|F_n(q_j)-F(q_j)|.

The grid separates the real line into two tails and intervals between consecutive grid points. On each middle interval, both CDFs are trapped between their values at the endpoints. The population CDF rises by exactly \(1/m\) between those endpoints, so the discrepancy anywhere in the interval is at most the largest grid error plus \(1/m\). The tails obey the same bound because the population probability outside the first and last grid points is \(1/m\).

Lemma: For any CDF \(F\), any nondecreasing CDF \(F_n\), and grid points \(q_1<\cdots<q_{m-1}\) satisfying \(F(q_j)=j/m\),

\sup_{x\in\mathbb{R}}|F_n(x)-F(x)|\le D_{n,m}+\frac{1}{m}.

Proof. If \(q_j\le x\le q_{j+1}\), monotonicity gives \(F_n(x)\le F_n(q_{j+1})\) and \(F(x)\ge F(q_j)\). Hence

F_n(x)-F(x) \le F_n(q_{j+1})-F(q_j) =F_n(q_{j+1})-F(q_{j+1})+\frac{1}{m} \le D_{n,m}+\frac{1}{m}.

In the other direction, \(F(x)\le F(q_{j+1})\) and \(F_n(x)\ge F_n(q_j)\), so

F(x)-F_n(x) \le F(q_{j+1})-F_n(q_j) =\frac{1}{m}+F(q_j)-F_n(q_j) \le D_{n,m}+\frac{1}{m}.

For \(x<q_1\), \(F(x)\le 1/m\), so \(F(x)-F_n(x)\le 1/m\). Also \(F_n(x)\le F_n(q_1)\), which implies \(F_n(x)-F(x)\le F_n(q_1)\le D_{n,m}+1/m\). For \(x\ge q_{m-1}\), \(F(x)\ge (m-1)/m\), giving \(F_n(x)-F(x)\le 1/m\). Further, \(F_n(x)\ge F_n(q_{m-1})\), and thus

F(x)-F_n(x)\le 1-F_n(q_{m-1}) =\frac{1}{m}+F(q_{m-1})-F_n(q_{m-1}) \le D_{n,m}+\frac{1}{m}.

These cases cover the real line and prove the bound. \(\square\)

Worked Example: Checking an Exponential Grid Carefully

Let \(F(x)=1-e^{-x}\) for \(x\ge 0\), with \(F(x)=0\) for \(x<0\), and consider observations \(0.2,0.6,1.4,2.0\). For \(m=4\), choose grid points satisfying \(F(q_j)=j/4\). Solving \(1-e^{-q_j}=j/4\) gives

q_1=-\log(3/4)\approx0.288,\qquad q_2=\log 2\approx0.693,\qquad q_3=-\log(1/4)\approx1.386.

At \(q_1\), the observation \(0.2\) is below the grid point, while the other three observations are above it. Therefore \(F_4(q_1)=1/4\), matching \(F(q_1)=1/4\), for error 0. At \(q_2\), \(0.2\) and \(0.6\) are at or below the point, so \(F_4(q_2)=2/4=1/2\), again giving error 0. At \(q_3\), only \(0.2\) and \(0.6\) are at or below it, so \(F_4(q_3)=2/4\), while \(F(q_3)=3/4\); the error is \(1/4\).

Consequently \(D_{4,4}=1/4\), and the lemma gives

\sup_x|F_4(x)-F(x)|\le \frac14+\frac14=\frac12.

This is a guaranteed upper bound obtained from the grid. It need not equal the actual largest discrepancy between grid points.

The Uniform Almost-Sure Convergence Theorem

Theorem: Let \(X_1,X_2,\ldots\) be IID real-valued random variables with continuous CDF \(F\), and let \(F_n\) be their empirical CDF. Then

\sup_{x\in\mathbb{R}}|F_n(x)-F(x)|\xrightarrow{a.s.}0.

Proof. For each integer \(m\ge2\), choose deterministic grid points \(q_{m,j}\) satisfying \(F(q_{m,j})=j/m\), for \(j=1,\ldots,m-1\). At each fixed grid point, the strong law applied to the IID indicators \(\mathbf{1}\{X_i\le q_{m,j}\}\) gives

F_n(q_{m,j})\xrightarrow{a.s.}F(q_{m,j}).

For a fixed \(m\), there are only finitely many grid points, so all these convergences hold together on an event of probability one. There are only countably many integers \(m\ge2\). Intersecting the corresponding probability-one events still gives an event \(\Omega_0\) with \(P(\Omega_0)=1\). On \(\Omega_0\), for every fixed \(m\),

D_{n,m}=\max_{1\le j\le m-1}|F_n(q_{m,j})-F(q_{m,j})| \xrightarrow[n\to\infty]{}0.

Apply the deterministic lemma for each \(m\). On \(\Omega_0\),

\sup_x|F_n(x)-F(x)|\le D_{n,m}+\frac{1}{m} \qquad\text{for every }m\ge2.

Taking the limit superior in \(n\), with \(m\) fixed, yields

\limsup_{n\to\infty}\sup_x|F_n(x)-F(x)|\le \frac{1}{m} \qquad\text{for every }m\ge2.

The left side is nonnegative and is bounded above by \(1/m\) for arbitrarily large \(m\). It must therefore equal zero. This proves the asserted almost-sure convergence. The supremum is a measurable random variable: since \(F_n\) and \(F\) are right-continuous, the supremum of their absolute difference over the reals equals its supremum over the rationals. \(\square\)

Worked Example: Turning the Proof into an Epsilon Bound

Suppose the target is to make the uniform error eventually less than \(0.05\). Choose \(m=41\), so the grid contribution is \(1/41\approx0.02439\). If the error at every point of this grid is less than \(0.025\), then \(D_{n,41}<0.025\), and the deterministic bound gives

\sup_x|F_n(x)-F(x)| <0.025+\frac{1}{41} \approx0.04939<0.05.

There are only 40 grid points for this choice of \(m\). At each one, the strong law says its empirical error tends to zero almost surely; since the grid is finite, eventually all 40 errors are less than \(0.025\) on a probability-one event. This illustrates the proof’s order of choices: first choose a sufficiently fine fixed grid, and then take \(n\) sufficiently large for that grid.

Why Continuity Matters to This Argument

Continuity is used to create grid points at prescribed probability levels, and thereby to ensure that the population CDF changes by only \(1/m\) between neighboring grid points. Without that small-increment property, monotonicity alone cannot make the bound arbitrarily tight. This is a limitation of this particular proof strategy, not a conclusion that uniform convergence must fail whenever \(F\) has a jump.

Worked Example: A Jump That an Equal-Probability Grid Cannot Split

Let \(X\) take values 0 and 1, each with probability \(1/2\). Its CDF is 0 for \(x<0\), \(1/2\) for \(0\le x<1\), and 1 for \(x\ge1\). For \(m=4\), an equal-probability grid would need points with CDF values \(1/4\), \(1/2\), and \(3/4\). But this CDF takes only the values 0, \(1/2\), and 1, so no point has CDF value \(1/4\) or \(3/4\).

Thus the continuous-CDF construction cannot be carried out here. The jump from 0 to \(1/2\) cannot be divided into smaller increments by selecting a point within the jump. This example shows exactly where the finite-grid argument needs continuity; it does not, by itself, decide whether uniform convergence holds in a discontinuous case.

Common Mistakes

Confusing pointwise and uniform convergence. Pointwise convergence at each fixed \(x\) does not immediately control a supremum over all \(x\). The finite grids and the deterministic bound supply that missing step.
Using only the grid errors. A small \(D_{n,m}\) does not alone bound errors between grid points. The additional \(1/m\) term accounts for the population probability change between adjacent grid points.
Choosing a grid before checking its values. At a grid point \(q\), observations equal to \(q\) count in \(F_n(q)\), because the definition uses \(X_i\le q\). Comparisons with approximate decimal grid locations should respect that inequality.
Taking an uncountable intersection of probability-one events. The proof uses a finite set of points for each fixed \(m\), then a countable intersection over integer \(m\). It does not assert that an uncountable collection of probability-one events has probability one.

Key takeaway: Continuity supplies finite grids with arbitrarily small population increments; the strong law controls errors on each fixed grid; and monotonicity extends that control between grid points. Together, these steps prove uniform almost-sure convergence of the empirical CDF.

Check Your Understanding

Use the definitions and arguments above to answer these questions.

Why does the strong law apply to \(F_n(q)\) for a fixed, nonrandom \(q\)?
In the grid bound, what role does the term \(1/m\) play?
Why can the probability-one events for all integer grid sizes \(m\ge2\) be intersected while retaining probability one?
For the exponential sample in the worked example, why is \(F_4(q_1)=1/4\), not 0?
What part of the finite-grid proof is unavailable for the two-point distribution, and what conclusion should not be inferred from that fact alone?