The Tight Constant in the Dvoretzky-Kiefer-Wolfowitz Inequality
Pascal Massart · The Annals of Probability · 1990
Let $\hat{F}_n$ denote the empirical distribution function for a sample of $n$ i.i.d. random variables with distribution function $F$. In 1956 Dvoretzky, Kiefer and Wolfowitz proved that $P\big(\sqrt{n} \sup_x(\hat{F}_n(x) - F(x)) > \lambda\big) \leq C \exp(-2\lambda^2),$ where $C$ is some unspecified constant. We show that $C$ can be taken as 1 (as conjectured by Birnbaum and McCarty in 1958), provided that $\exp(-2\lambda^2) \leq \frac{1}{2}$. In particular, the two-sided inequality $P\big(\sqrt{n} \sup_x|\hat{F}_n(x) - F(x)| > \lambda\big) \leq 2 \exp(-2\lambda^2)$ holds without any restriction on $\lambda$. In the one-sided as well as in the two-sided case, the constants cannot be further improved.
Cited by 735 works. doi:10.1214/aop/1176990746 Open-access PDF
Authors
References
- Empirical Processes with Applications to Statistics
- Asymptotic Minimax Character of the Sample Distribution Function and of the Classical Multinomial Estimator
- Sulla determinazione empirica di una legge di distribuzione
- On the recovery of discrete probability densities from imperfect measurements
- Hungarian Constructions from the Nonasymptotic Viewpoint
- A Uniform Bound for the Tail Probability of Kolmogorov-Smirnov Statistics