# Intuition behind Dvoretzky Kiefer Wolfowitz inequality

I've been reading about the Dvoretzky-Kiefer-Wolfowitz inequality, in the context of confidence bands on empirical distribution functions.

I think I understand the inequality at face value: that the probability that the empirical distribution function differs from the real distribution function by more than some amount is bounded by a function of sample size. (And a surprisingly aggressive function of sample size at that, at least to my mind).

What I'm completely lacking, though, is any sense of why the inequality holds. Given we're not (I think) making any assumptions about the real distribution function, apart from that it is a distribution function, I don't really see why we can say anything useful about it at all! It probably doesn't help that I've yet to find a comprehensible proof of the theorem (my definition of comprehensible is that which might be understood by a competent physicist!)

So, can anyone point me towards a readable proof? Or perhaps supply a hint as to the intuition behind this inequality?

This answer might help you to understand its origin. You will need to fill some details up, though.

Another reference of interest with a formal proof of an improved version of the inequallity is

Massart, P. (1990). The Tight Constant in the Dvoretzky-Kiefer-Wolfowitz Inequality. Annals of Probability 18: 1269-1283.

The Kolmogorov-Smirnov distribution is not as simple as one would love it were and the results involving this distribution tend to be not-straightforward.

• Thanks, I'll take a look at those. Although I think you might overestimate the competence of a competent physicist :-) – JonyEpsilon Apr 12 '13 at 21:27
• @JonyEpsilon I see your point. The KS distribution is unfortunately very difficult. I hope this helps anyway. – Macallan Apr 15 '13 at 8:47

Consider an i.i.d. sample $$X_{1}, \dots, X_{n}$$ from a distribution with CDF $$F\left(x\right)$$, and let $$$$\widehat{F}_{n}\left(x\right) = \dfrac{1}{n}\sum_{i = 1}^{n}\mathbb{I}_{X_{i} \leq x}$$$$ denote the usual empirical distribution function. The Dvoretzky-Kiefer-Wolfowitz inequality states that $$$$\operatorname{Pr}\left(\sup_{x\in\mathbb{R}}\left\{\sqrt{n}\left|\widehat{F}_{n}\left(x\right) - F\left(x\right)\right|\right\} > \epsilon\right) \leq 2e^{-2\epsilon^{2}}$$$$ for all $$\epsilon > 0$$. To provide some intuition behind this result, first recognise that for any $$x$$ such that $$F\left(x\right) \in \left(0, 1\right)$$, the Central Limit Theorem (or alternatively using the weaker De Moivre–Laplace theorem) gives that $$$$\sqrt{n}\left(\widehat{F}_{n}\left(x\right) - F\left(x\right)\right) \overset{\mathrm{d}}{\to} \mathcal{N}\left(0, F\left(x\right)\left(1 - F\left(x\right)\right)\right)$$$$ since $$\widehat{F}_{n}\left(x\right)$$ is essentially the sample proportion of observations not greater than $$x$$, which we can compute to have variance $$$$\operatorname{Var}\left(\widehat{F}_{n}\left(x\right)\right) = \dfrac{F\left(x\right)\left(1 - F\left(x\right)\right)}{n}$$$$ (eg. by the binomial distribution). The takeaway here is that $$\widehat{F}_{n}\left(x\right)$$ will be approximately Gaussian for large $$n$$. Now, we use the fact that for a Gaussian random variable $$Y \sim \mathcal{N}\left(\mu, \sigma^{2}\right)$$, a well-known two-sided concentration inequality is given by $$$$\operatorname{Pr}\left(\left|Y - \mu\right| > \varepsilon\right) \leq 2\exp\left(-\dfrac{\varepsilon^{2}}{2\sigma^{2}}\right)$$$$ for all $$\varepsilon > 0$$. As an aside, this inequality can be proven using the moment generating function of a Gaussian distribution in combination with the Chernoff bound to obtain the one-sided tail inequality, and then Boole's inequality for the two-sided tail inequality. See for example (2.9) of here to obtain further details.

Here is where the 'intuitive' step comes in. If we treat $$\widehat{F}_{n}\left(x\right)$$ as actually being Gaussian and apply the concentration inequality for Gaussians, we will recover the Dvoretzky-Kiefer-Wolfowitz inequality. Note that $$F\left(x\right)\left(1 - F\left(x\right)\right)$$ is maximised at $$F\left(x\right) = 1/2$$, hence $$\sup_{x\in\mathbb{R}}F\left(x\right)\left(1 - F\left(x\right)\right) = 1/4$$. So this gives \begin{align} \operatorname{Var}\left(\widehat{F}_{n}\left(x\right)\right) &= \dfrac{F\left(x\right)\left(1 - F\left(x\right)\right)}{n} \\ &\leq \dfrac{1}{4n} \end{align} Treating $$\widehat{F}_{n}\left(x\right)$$ as Gaussian and plugging it into the concentration inequality gives for any $$x \in \mathbb{R}$$: $$$$\operatorname{Pr}\left(\left|\widehat{F}_{n}\left(x\right) - F\left(x\right)\right| > \varepsilon\right) \leq 2\exp\left(-\dfrac{\varepsilon^{2}}{2\operatorname{Var}\left(\widehat{F}_{n}\left(x\right)\right)}\right)$$$$ Taking the worst-case supremum over $$x$$ on either side separately: \begin{align} \operatorname{Pr}\left(\sup_{x\in\mathbb{R}}\left|\widehat{F}_{n}\left(x\right) - F\left(x\right)\right| > \varepsilon\right) &\leq 2\exp\left(-\dfrac{\varepsilon^{2}}{2\sup_{x'\in\mathbb{R}}\operatorname{Var}\left(\widehat{F}_{n}\left(x'\right)\right)}\right) \\ &\leq 2\exp\left(-\dfrac{\varepsilon^{2}}{2/\left(4n\right)}\right) \\ &= 2e^{-2n\varepsilon^{2}} \end{align} Applying the substitution $$\epsilon = \sqrt{n}\varepsilon$$ then yields the Dvoretzky-Kiefer-Wolfowitz inequality as originally claimed: $$$$\operatorname{Pr}\left(\sqrt{n}\sup_{x\in\mathbb{R}}\left|\widehat{F}_{n}\left(x\right) - F\left(x\right)\right| > \epsilon\right) \leq 2e^{-2\epsilon^{2}}$$$$