Pointwise Concentration of the Empirical Distribution Function

From a Distribution Function to Indicator Averages

The empirical distribution function summarizes a sample by recording the fraction of observations at or below each threshold. At any one fixed threshold, that fraction is an average of bounded independent random variables, so Hoeffding’s inequality gives an immediate concentration bound. The useful distinction is between a bound at one threshold, a bound at several fixed thresholds, and a bound over every real threshold. The first two follow directly from Hoeffding’s inequality and a union bound; the third needs an additional argument.

Definition: Let \(X_1,\ldots,X_n\) be independent and identically distributed real-valued random variables with distribution function \(F\). Their empirical distribution function is

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

Here \(\mathbf{1}\{A\}\) equals 1 when the event \(A\) occurs and 0 otherwise. Thus \(F_n(t)\) is the observed proportion of sample values no larger than \(t\).

For a fixed, nonrandom \(t\), the indicators \(\mathbf{1}\{X_i\le t\}\) are independent Bernoulli random variables with success probability \(F(t)\). In particular,

$$ E[F_n(t)]=F(t). $$

The fixed-threshold condition matters: the indicators are being evaluated at a specified value, not at a threshold selected after inspecting the sample.

Pointwise Hoeffding Bounds

Hoeffding’s inequality states that if \(Y_1,\ldots,Y_n\) are independent random variables with \(a_i\le Y_i\le b_i\) almost surely, then for \(u>0\),

P\left(\frac{1}{n}\sum_{i=1}^n(Y_i-E[Y_i])\ge u\right) \le \exp\left(-\frac{2n^2u^2}{\sum_{i=1}^n(b_i-a_i)^2}\right).

For indicators, every range has length 1, so the denominator in the exponent is \(n\). Applying the inequality to the indicators and then to their negatives gives the following result.

Theorem (pointwise empirical-CDF concentration): For independent and identically distributed real-valued \(X_1,\ldots,X_n\), every fixed \(t\in\mathbb{R}\), and every \(\varepsilon>0\),

P\bigl(F_n(t)-F(t)\ge\varepsilon\bigr)\le e^{-2n\varepsilon^2}, \qquad P\bigl(F(t)-F_n(t)\ge\varepsilon\bigr)\le e^{-2n\varepsilon^2},

and consequently

P\bigl(|F_n(t)-F(t)|\ge\varepsilon\bigr)\le 2e^{-2n\varepsilon^2}.

To verify the application, set \(Y_i=\mathbf{1}\{X_i\le t\}\). These variables are independent, lie in \([0,1]\), and have expectation \(F(t)\). Their average is \(F_n(t)\). Hoeffding’s inequality therefore gives the upper-tail bound. Applying the same inequality to \(-Y_i\), whose range also has length 1, gives the lower-tail bound. The two-sided bound follows because the event \(\{|F_n(t)-F(t)|\ge\varepsilon\}\) is the union of the two one-sided events, so its probability is at most the sum of their probabilities. \(\square\)

Worked Example: A Single Threshold

Suppose \(n=100\) observations are drawn independently from a distribution with \(F(t)=0.30\) at a specified threshold \(t\). Bound the probability that the empirical proportion below or at \(t\) differs from 0.30 by at least 0.10.

The pointwise two-sided bound gives

P\bigl(|F_{100}(t)-0.30|\ge 0.10\bigr) \le 2\exp\bigl(-2(100)(0.10)^2\bigr).

Since \(2(100)(0.10)^2=2\), this is

2e^{-2}\approx 2(0.1353353)=0.2706706.

Thus the bound is approximately 0.2707. It is a valid upper bound, not an estimate of the actual probability. The value \(F(t)=0.30\) identifies the Bernoulli success probability, but the Hoeffding bound itself does not depend on that probability.

Combining Bounds at Finitely Many Thresholds

A common goal is to control the empirical CDF at several thresholds simultaneously. Let \(t_1,\ldots,t_m\) be fixed real numbers. If any one of the \(m\) deviations is at least \(\varepsilon\), then the event is contained in the union of the \(m\) individual deviation events. The union bound therefore combines the pointwise results without requiring independence between those events.

Theorem (finite-grid concentration): For fixed thresholds \(t_1,\ldots,t_m\) and \(\varepsilon>0\),

P\left(\max_{1\le j\le m}|F_n(t_j)-F(t_j)|\ge\varepsilon\right) \le 2m e^{-2n\varepsilon^2}.

For each \(j\), the pointwise theorem bounds the probability of \(|F_n(t_j)-F(t_j)|\ge\varepsilon\) by \(2e^{-2n\varepsilon^2}\). The event that the maximum is at least \(\varepsilon\) is the union of these \(m\) events. By the union bound,

P\left(\bigcup_{j=1}^m\{|F_n(t_j)-F(t_j)|\ge\varepsilon\}\right) \le \sum_{j=1}^m P\bigl(|F_n(t_j)-F(t_j)|\ge\varepsilon\bigr) \le 2m e^{-2n\varepsilon^2}.

This proves the claim. The thresholds need not be equally spaced, and the deviations at different thresholds need not be independent. The bound becomes informative when \(2m e^{-2n\varepsilon^2}\) is small; if the expression exceeds 1, replacing it by 1 is valid but offers no useful guarantee. \(\square\)

Worked Example: Four Prespecified Thresholds

A sample has size \(n=200\), and four thresholds are selected before observing the data. Find an upper bound on the probability that at least one of the four empirical-CDF values differs from its population value by 0.12 or more.

Here \(m=4\) and \(\varepsilon=0.12\). The finite-grid bound is

P\left(\max_{1\le j\le4}|F_{200}(t_j)-F(t_j)|\ge0.12\right) \le 2(4)\exp\bigl(-2(200)(0.12)^2\bigr).

The exponent is \(-2(200)(0.0144)=-5.76\). Numerically,

8e^{-5.76}\approx 8(0.0031511)\approx 0.02521\approx 0.0252.

Thus the probability is at most about 0.0252. Equivalently, with probability at least about \(1-0.02521=0.97479\), all four deviations are smaller than 0.12. This guarantee is simultaneous across the four specified thresholds.

When a Grid Can Control the Whole CDF

A finite-grid bound controls only the listed thresholds. To extend it between grid points, use the fact that both \(F_n\) and \(F\) are nondecreasing. The extension also depends on how much probability mass \(F\) places between adjacent grid points and in the two tails.

Proposition (deterministic grid bracketing): Let \(t_0<t_1<\cdots<t_K\) be a finite grid and let \(\delta\ge0\). Suppose

F(t_0)\le\delta,\qquad 1-F(t_K)\le\delta,\qquad F(t_{j+1})-F(t_j)\le\delta\quad(0\le j<K).

Then, for every sample,

\sup_{x\in\mathbb{R}}|F_n(x)-F(x)| \le \max_{0\le j\le K}|F_n(t_j)-F(t_j)|+\delta.

Write \(D=\max_{0\le j\le K}|F_n(t_j)-F(t_j)|\). If \(t_j\le x\le t_{j+1}\), monotonicity gives \(F_n(t_j)\le F_n(x)\le F_n(t_{j+1})\) and \(F(t_j)\le F(x)\le F(t_{j+1})\). Hence

F_n(x)-F(x) \le F_n(t_{j+1})-F(x) \le D+F(t_{j+1})-F(x) \le D+\delta,

and, in the other direction,

F(x)-F_n(x) \le F(x)-F_n(t_j) \le F(x)-F(t_j)+D \le D+\delta.

For \(x<t_0\), both CDF values are nonnegative, while \(F(x)\le F(t_0)\le\delta\) and \(F_n(x)\le F_n(t_0)\le F(t_0)+D\le\delta+D\). Thus their absolute difference is at most \(\delta+D\). For \(x>t_K\), apply the same reasoning to the nonnegative tail probabilities \(1-F_n(x)\) and \(1-F(x)\): each is at most \(\delta+D\), using \(1-F(t_K)\le\delta\) and the grid error at \(t_K\). These cases cover every real \(x\), proving the result. \(\square\)

Combining this deterministic proposition with the finite-grid theorem yields a whole-line probability bound. Under the proposition’s grid conditions, if there are \(K+1\) grid points, then for any \(\varepsilon>0\),

P\left(\sup_{x\in\mathbb{R}}|F_n(x)-F(x)|>\delta+\varepsilon\right) \le 2(K+1)e^{-2n\varepsilon^2}.

Indeed, the event on the left implies that at least one grid error exceeds \(\varepsilon\), and the finite-grid bound controls that event. The deterministic allowance \(\delta\) is the price of moving between grid thresholds and covering the tails.

Worked Example: A Uniform Grid for a Uniform Distribution

Let \(X_1,\ldots,X_{400}\) be independent observations from the uniform distribution on \([0,1]\). Use the grid \(0,0.25,0.50,0.75,1\) to bound the probability that the empirical CDF differs from \(F\) by more than 0.35 anywhere.

For this distribution, \(F(0)=0\), \(F(1)=1\), and each adjacent grid increment is 0.25. Thus the bracketing proposition applies with \(\delta=0.25\). Moreover, \(F_{400}(0)=F(0)=0\) and \(F_{400}(1)=F(1)=1\) almost surely. Only the three interior grid points need nontrivial bounds. If all three interior errors are smaller than \(\varepsilon=0.10\), the proposition ensures that the supremum error is at most \(0.25+0.10=0.35\). Consequently,

P\left(\sup_{x\in\mathbb{R}}|F_{400}(x)-F(x)|>0.35\right) \le 2(3)e^{-2(400)(0.10)^2} =6e^{-8}.

Since \(e^{-8}\approx0.00033546\), the bound is approximately \(0.002013\). Therefore, with probability at least \(1-0.002013=0.997987\), the empirical CDF stays within 0.35 of the uniform CDF at every real threshold. The grid spacing contributes 0.25 to the error allowance; the remaining 0.10 comes from the concentration bound.

Common Pitfall and Practical Interpretation

A pointwise statement and a uniform statement are different claims. The inequality \(P(|F_n(t)-F(t)|\ge\varepsilon)\le2e^{-2n\varepsilon^2}\) holds for each fixed \(t\). It does not, by itself, give the same bound for the event that the deviation is large at some threshold chosen from the entire real line. Nor does applying the finite-grid theorem control thresholds between grid points unless a bracketing argument and a bound on the CDF increments are supplied.

A useful way to plan a finite-grid guarantee is to choose a target failure probability \(\alpha\) and solve

2m e^{-2n\varepsilon^2}\le\alpha \quad\Longleftrightarrow\quad \varepsilon\ge\sqrt{\frac{\log(2m/\alpha)}{2n}}.

This controls the maximum error at \(m\) prespecified thresholds. For a whole-line guarantee based on a grid, add the grid’s mass-increment allowance \(\delta\) to that error level. The distinction is important: increasing the number of thresholds improves coverage of the CDF’s domain but makes the union-bound term larger, while a finer grid can reduce \(\delta\).

Key takeaway: At a fixed threshold, \(F_n(t)\) is an average of independent Bernoulli indicators and obeys a Hoeffding bound. A union bound gives simultaneous control at finitely many fixed thresholds. Control over all real thresholds additionally requires monotonicity-based bracketing and a grid whose CDF increments, including the tails, are small.

Check Your Understanding

Try these questions using the definitions and bounds above.

For fixed \(t\), identify the Bernoulli random variables whose average is \(F_n(t)\), and state their success probability.
With \(n=50\) and \(\varepsilon=0.2\), write the pointwise two-sided Hoeffding bound at a fixed threshold.
Why does the finite-grid union bound not require the empirical-CDF errors at distinct thresholds to be independent?
For a grid with \(m\) fixed thresholds, what choice of \(\varepsilon\) makes the finite-grid failure bound no larger than a given \(\alpha\in(0,1)\)?
What additional conditions allow grid-point control to imply control over all real thresholds?