2011/07/26 by Fan Wei, Richard M. Dudley, Wei, Fan +1 · 1 citation
Mathematics · Computer Science · #Statistical Methods and Inference #Random Matrices and Applications #Bayesian Methods and Mixture Models
paper · pdf · doi:10.48550/arxiv.1107.5356
The Dvoretzky--Kiefer--Wolfowitz (DKW) inequality says that if Fn is an empirical distribution function for variables i.i.d. with a distribution function F, and Kn is the Kolmogorov statistic √(n)supx|(Fn-F)(x)|, then there is a finite constant C such that for any M>0, Pr(Kn>M) ≤ Cexp(-2M2). Massart proved that one can take C=2 (DKWM inequality) which is sharp for F continuous. We consider the analogous Kolmogorov--Smirnov statistic KSm,n for the two-sample case and show that for m=n, the DKW inequality holds with C=2 if and only if n≥ 458. For n0≤ n<458 it holds for some C>2 depending on n0. For m≠ n, the DKWM inequality fails for the three pairs (m,n) with 1≤ m < n≤ 3. We found by computer search that for n≥ 4, the DKWM inequality always holds for 1≤ m< n≤ 200, and further that it holds for n=2m with 101≤ m≤ 300. We conjecture that the DKWM inequality holds for pairs m≤ n with the 457+3 =460 exceptions mentioned.