The Tight Constant in the Dvoretzky-Kiefer-Wolfowitz Inequality

摘要: Let $\hat{F}_n$ denote the empirical distribution function for a sample of $n$ i.i.d. random variables with $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 can be taken as 1 (as conjectured by Birnbaum McCarty in 1958), provided $\exp(-2\lambda^2) \frac{1}{2}$. particular, two-sided inequality \sup_x|\hat{F}_n(x) F(x)| 2 \exp(-2\lambda^2)$ holds without any restriction on $\lambda$. one-sided well case, constants cannot further improved.