cdf concentration

What can we say about the concentration of the empirical CDF about the true CDF?

Scalar DKW inequality

For real valued observations $X_1,\dots ,X_n$ with $F_n(x)=\frac{1}{n}{\sum }_{i\le n}1(X_i\le x)$, the DKW (Dvoretzky-Kiefer-Wolfowitz) inequality states that

$$\mathbb{P}\left(\underset{x\in \mathbb{R}}{\sup }|F_n(x)-F(x)>t\right)\le 2\exp (-2n{t}^2).$$

Note this statement is uniform in $x$ which, depending on your expectations, is kind of remarkable. The intuition is that if $F(x)$ sharply increases (it can’t decrease, of course) at some $x$, then these are precisely the places where we expect to see many observations, so $F_n(x)$ won’t be too far from $F(x)$.

The original DKW inequality was an asymptotic statement: it bounded the probability as $\lesssim \exp (-2n{t}^2)$. In 1990, Paul Massart proved that the constant on the right hand side was 2, and he proved that this was tight.

Multivariate DKW inequality

In 2021, Naaman gave a multivariate extension of DKW. Namely,

$$\mathbb{P}\left(\underset{x\in {\mathbb{R}}^d}{\sup }|F_n(x)-F(x)>t\right)\le d(n+1)\exp (-2n{t}^2).$$

For sufficiently large $n$, $n+1$ can be replaced by $2$ in which case the constant in front of the exponential is $2d$, which is optimal. Here the empirical CDF is as above, but $1(X_i\le x$) is interpreted component-wise: to be true each component of $X_i$ must be at most $x_i$.

In 1977, Devroye gave a similar result but with $2e^2(2n{)}^d$ replacing $d(n+1)$.

Both the univariate and multivariate DKW inequalities hold under slightly weaker assumptions than the usual iid assumption.

Glivenko-Cantelli theorem

Glivenko and Cantelli proved that, in the scalar case,

$$\underset{x\in \mathbb{R}}{\sup }|F_n(x)-F(x)|={\left|F_n-F\right|}_{\infty }\stackrel{a.s.}{\to }0.$$

The DKW inequality implies almost sure convergence (via the Borel-Cantelli) lemma, so the Glivenko-Cantelli theorem is strictly weaker than the DKW inequality, which provides explicit rates of convergence. But the Glivenko-Cantelli theorem is part of a broader conversation about Glivenko-Cantelli classes in empirical process theory.