Simple proof of sharp constant in DKW inequality

Question

The DKW inequality says that if $F_n$ is the empirical CDF corresponding to real-valued random variables $X_1, \dots, X_n$ distributed identically and independently from a distribution with CDF $F$, then for all $\lambda > 0$, we have $$ P(\sqrt{n} \sup_{t} |F_n(t) - F(t)| > \lambda) \leq 2 \exp(-2\lambda^2). $$

This was proved by Pascal Massart in 1990. The proof is quite lengthy, and based on tedious calculations related to the Kolmogorov-Smirnoff distribution.

In the last 30+ years have there been any simplifications to this argument? Is it possible to provide a shorter proof?

Answer 1

Thank you for your question. It motivated me to go through that paper. While I don't have a direct answer, I broke the paper down. The difficult details are non-omitable.. you have to find them in the paper.

---

Dvoretzky-Kiefer-Wolfowitz inequality is really about bounding the $\infty$-norm (sup-norm) of the Kolmogorov distribution $D_{n} := sup_{x\in R} |\hat{F}_{n}(x) - F(x)|$, where $F$ is the cdf and $\hat{F}_{n}$ is the empirical distribution function) of a single variate distribution.

To my surprise, Kolmogorov distribution is distribution-free, meaning that it does not depend on the underlying cdf! And this is actually not difficult to see - Hints:

1. Any random variable $X$ with continuous cdf $F$ satisfies that $F(X)$ is a $Unif_{[0,1]}$!
2. Replace $x$ with $F^{-1}(t)$ and $x \in \mathbb{R}$ with $t \in [0,1]$ in the definition $D_{n}$. (This argument should also work for other $L_{p}$-norms (up to a Jacobian of $F$), but I still can't find a version of DKL inequality for them.)

Therefore, in this paper, the author first assumed that $F$ is the cdf of the uniform disribution on [0,1]. Then the bounding problem becomes very explicit. And that's why it is about the Kolmogorov-Smirnoff distribution. It is very natural to inspect this due to the reduction above.

Main Steps

We follow the notations in the paper. $D_{n}$ is easily transformed to $D_{n}^{-}$, which the paper will focus. The main theorem (DKW with sharp bound) is

• Theorem 1: $P(D_{n}^{-} > \lambda) \leq exp(-2 \lambda^{2})$, under some very mild conditions.

The key idea is to compare $D_{n}^{-}$ with some quantities $f_{\lambda}(s)$ derived from Brownian bridge.

More precisely, we have

• (2.3) $P(D_{n}^{-} > \lambda) = \sum_{0 \leq j \leq n - \lambda \sqrt{n}} p_{\lambda,n}(j)$
• (2.4) $exp(-2\lambda^{2}) = \int_{0}^{1} f_{\lambda}(s) ds$
• (Prop. 1) compares $p_{\lambda,n}(j) and f_{\lambda}(s)$

Finally, in the last 5 pages, the author broke things down to two cases and proved them separately by hard estimation.

1. $n \geq 39$ and $\lambda \leq \sqrt(n)/2$
2. $n \leq 38$ or $\lambda > \sqrt(n)/2$

Answer 2

I can recommend reading this recent note of Reeve, titled 'A short proof of the Dvoretzky--Kiefer--Wolfowitz--Massart inequality', which uses a nice reverse martingale approach, and builds on the original DKW inequality in a few interesting ways.