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:
- Any random variable $X$ with continuous cdf $F$ satisfies that $F(X)$ is a $Unif_{[0,1]}$!
- 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, 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.
- $n \geq 39$ and $\lambda \leq \sqrt(n)/2$
- $n \leq 38$ or $\lambda > \sqrt(n)/2$