Dvoretzky–Kiefer–Wolfowitz inequality

Remarks

Dvoretzky, Kiefer and Wolfowitz proved in 1956 a bound of the form $C e^{-2n\varepsilon^2}$ with an unspecified constant $C$. Massart showed in 1990 that $C = 2$ works, and this constant cannot be lowered. The reduction to the uniform law on $[0, 1]$ uses the quantile transform. The variable $X_i$ has the same law as $Q(U_i)$, for $U_i$ uniform and $Q$ the quantile function of $F$. The supremum can only shrink under this change. The hard part is the sharp tail bound for the uniform case.

Example: a confidence band. Given $\alpha \in (0, 1)$, put $\varepsilon = \sqrt{\ln(2/\alpha) / (2n)}$, so that $2e^{-2n\varepsilon^2} = \alpha$. Then the band $F_n(x) \pm \varepsilon$ contains the whole graph of $F$ with probability at least $1 - \alpha$. For $n = 1000$ and $\alpha = 0.05$, this gives $\varepsilon \approx 0.043$.

The bound needs no assumption on $F$: no continuity and no moments. It does need independence and a common law; for dependent data $F_n$ can stay far from $F$.

Going deeper

For a student

The inequality is a quantitative form of the Glivenko–Cantelli theorem. Since $\sum_n 2e^{-2n\varepsilon^2} < \infty$, the Borel–Cantelli lemma gives $\sup_x \abs{F_n - F} \to 0$ almost surely. It also bounds the tail of the Kolmogorov–Smirnov statistic: $P(\sqrt{n} D_n > t) \le 2e^{-2t^2}$ for every $n$, which matches the leading term of the limiting Kolmogorov law. It is a common tool in learning theory and in the analysis of nonparametric estimators, because it is non-asymptotic.