THE TIGHT CONSTANT IN THE DVORETZKY-KIEFER-WOLFOWITZ INEQUALITY

THE TIGHT CONSTANT IN THE DVORETZKY-KIEFER-WOLFOWITZ INEQUALITY

1990, Vol. 18, No. 3, 1269-1283 | P. MASSART
The paper by P. Massart addresses the tight constant in the Dvoretzky-Kiefer-Wolfowitz (DKW) inequality, which bounds the probability that the empirical distribution function deviates from the true distribution function. Specifically, the DKW inequality states that for a sample of $n$ independent and identically distributed (i.i.d.) random variables with distribution function $F$, the probability that the supremum of the difference between the empirical distribution function $\hat{F}_n$ and the true distribution function $F$ exceeds a certain threshold $\lambda$ is bounded by a constant $C$ times $\exp(-2\lambda^2)$. The main result of the paper is that this constant $C$ can be taken as 1, provided that $\exp(-2\lambda^2) \leq \frac{1}{2}$. This conjecture was previously made by Birnbaum and McCarty in 1958. The paper provides a detailed proof of this result, including asymptotic expansions and numerical computations to support the conjecture. Additionally, the paper derives a two-sided inequality and shows that the constants in the DKW inequality cannot be further improved. The proof involves complex mathematical techniques, including the use of Brownian bridges and detailed inequalities for binomial tails. The results have implications for the statistical significance of the Kolmogorov-Smirnov test for goodness of fit.The paper by P. Massart addresses the tight constant in the Dvoretzky-Kiefer-Wolfowitz (DKW) inequality, which bounds the probability that the empirical distribution function deviates from the true distribution function. Specifically, the DKW inequality states that for a sample of $n$ independent and identically distributed (i.i.d.) random variables with distribution function $F$, the probability that the supremum of the difference between the empirical distribution function $\hat{F}_n$ and the true distribution function $F$ exceeds a certain threshold $\lambda$ is bounded by a constant $C$ times $\exp(-2\lambda^2)$. The main result of the paper is that this constant $C$ can be taken as 1, provided that $\exp(-2\lambda^2) \leq \frac{1}{2}$. This conjecture was previously made by Birnbaum and McCarty in 1958. The paper provides a detailed proof of this result, including asymptotic expansions and numerical computations to support the conjecture. Additionally, the paper derives a two-sided inequality and shows that the constants in the DKW inequality cannot be further improved. The proof involves complex mathematical techniques, including the use of Brownian bridges and detailed inequalities for binomial tails. The results have implications for the statistical significance of the Kolmogorov-Smirnov test for goodness of fit.
Reach us at info@study.space