Inference for CDFs

CDF estimation/inference is one of the most fundamental tasks in statistics, as the CDF completely describes the distribution of a random variable. Not so surprisingly, the empirical CDF serves as a natural and effective estimator. Suppose we have iid data $X_i\sim P$. The empirical CDF is defined as the step function:

$${\hat{F}}_n(t)=\frac{1}{n}\sum _{i=1}^n{\mathrm{𝟙}}_{\{t\ge X_i\}}.$$

One can verify that ${\hat{F}}_n$ is a valid CDF as it’s monotonic, right continuous, and has limits $0$ and $1$.

For any distribution $P$ with CDF $F$, the Glivenko–Cantelli theorem states the asymptotic almost sure convergence of $\Vert {\hat{F}}_n-F{\Vert }_{\infty }$, Donsker’s theorem states its asymptotic convergence in distribution, and Dvoretzky–Kiefer–Wolfowitz theorem gives the non-asymptotic convergence rate.

Glivenko–Cantelli

${\hat{F}}_n$ converges uniformly to the true CDF $F$ almost surely:

$$\underset{t\in \mathbb{R}}{\sup }|{\hat{F}}_n(t)-F(t)|\stackrel{\text{a.s.}}{\to }0.$$

Proof

We use the weak Law of Large Numbers to prove Convergence in Probability. The Strong Convergence can be proved similarly using the strong law of large numbers.

We use a grid approach. Fix $m$ for the grid granularity $1/m$. Construct grid points $\{t_k{\}}_{k=1}^m$ such that $F(t_k)=\frac{k}{m+1}$. By LLN, $\hat{F}(t)\stackrel{P}{\to }F(t)$ for all $t$. Therefore, for any $ϵ,\delta >0$, there exists $N_k\in {\mathbb{N}}_{+}$ such that for all $n>N_k$, $P(|\hat{F}(t_k)-F(t_k)|\ge ϵ)\le \delta /m$. Let $N={\max }_k{N}_k$. Then by the union bound,

$$P(\underset{k}{\max }|\hat{F}(t_k)-F(t_k)|\ge ϵ)\le \delta .$$

The above bound also applies when we let $t_0=-\infty$ and $t_{m+1}=+\infty$ as $\hat{F}(-\infty )=F(-\infty )=0$ and $\hat{F}(+\infty )=F(+\infty )=1$.

For any $t\in \mathbb{R}$, let $k$ be such that $t_k\le t\le t_{k+1}$. Then, by the monotonicity,

$$\begin{array}{rl}|\hat{F}(t)-F(t)|\le & \max \{|\hat{F}(t_{k-1})-F(t)|,|\hat{F}(t_k)-F(t)|\}\\ =& \max \{|\hat{F}(t_{k-1})-F(t_{k-1})+F(t_{k-1})-F(t)|,|\hat{F}(t_k)-F(t_k)+F(t_k)-F(t)|\}\\ \le & \underset{k}{\max }\{|\hat{F}(t_k)-F(t_k)|\}+\max \{F(t)-F(t_{k-1}),F(t_k)-F(t)\}\\ \le & \frac{1}{m+1}+ϵ,\text{w.p.}\ge 1-\delta .\end{array}$$

Letting $m\to \infty$ gives the result.

Dvoretzky–Kiefer–Wolfowitz

${\hat{F}}_n$ converges uniformly to the true CDF $F$ with a subGaussian tail bound:

$$P\left(\underset{t\in \mathbb{R}}{\sup }|{\hat{F}}_n(t)-F(t)|\ge ϵ\right)\le 2\exp (-2n{ϵ}^2).$$

Proof

Let $M_n:={\sup }_t|{\hat{F}}_n(t)-F(t)|$. One important observation is that “stretching the x-axis” does not change $M_n$. Therefore, we can arbitrarily stretch $F$ along the x-axis to make it arbitrarily close to $F_{\mathrm{Unif}[0,1]}$.

Formally, we notice that

$${\hat{F}}_n(t)=\frac{1}{n}\sum _{i=1}^n{1}_{\{t\ge X_i\}}$$

is the average of $n$ iid Bernoulli r.v.s with parameter $\mathbb{E}[1_{\{t\ge X_i\}}]=P(X_i\le t)=F(t)$. Let

$${\hat{G}}_n(F(t))=\frac{1}{n}\sum _{i=1}^n{1}_{\{F(t)\ge U_i\}},$$

where $U_i\stackrel{\text{iid}}{\sim }\mathrm{Unif}[0,1]$. We can see that $1\{F(t)\ge U_i\}$ is also a Bernoulli r.v. with parameter $F(t)$. Therefore,

$${\hat{F}}_n(t)\stackrel{d}{=}{\hat{G}}_n(F(t)).$$

This gives

$$\underset{t\in \mathbb{R}}{\sup }|{\hat{F}}_n(t)-F(t)|\stackrel{d}{=}\underset{t\in [0,1]}{\sup }|{\hat{G}}_n(F(t))-F(t)|=\underset{s\in \mathrm{range}(F)}{\sup }|{\hat{G}}_n(s)-s|\le \underset{s\in [0,1]}{\sup }|{\hat{G}}_n(s)-s|,$$

where the equality holds iff $\mathrm{range}(F)=[0,1]$ iff $F$ is continuous.

Note that ${\hat{G}}_n$ is just the empirical CDF of the uniform distribution. Therefore, $M_n$ has the same distribution for any continuous $F$. We call such a distribution-invariant statistic a pivotal statistic.

Apply some concentration analysis to the supreme of uniform empirical CDF gives the desired result.

Donsker

If further $F$ is continuous, then

$$\sqrt{n}\underset{t\in \mathbb{R}}{\sup }|{\hat{F}}_n(t)-F(t)|\stackrel{d}{\to }\underset{t\in [0,1]}{\sup }|B(t)|,$$

where $B$ is a Brownian bridge on $[0,1]$.

To see the emergence of the Brownian bridge, we can fix a specific $t$, and the CLT gives us

$$\sqrt{n}({\hat{F}}_n(t)-F(t))\stackrel{d}{\to }\mathcal{N}(0,F(t)(1-F(t))).$$

This is because ${\hat{F}}_n(t)$ is the average of indicator r.v.s. Then, the stochastic process $\{{\hat{F}}_n(t)-F(t){\}}_{t\in \mathbb{R}}$ has an asymptotic distribution similar to a Brownian motion $B(t)\sim \mathcal{N}(0,t)$, except that ${\hat{F}}_n(-\infty )-F(-\infty )={\hat{F}}_n(+\infty )-F(+\infty )=0\sim \mathcal{N}(0,0)$. Therefore, the stochastic process actually converges to a Brownian bridge: $B(t)\mid B(1)=0$.