Two-sample Dvoretzky-Kiefer-Wolfowitz inequalities

The Dvoretzky-Kiefer-Wolfowitz (DKW) inequality says that if F _n is an empirical distribution function for variables i.i.d. with a distribution function F, and K _n is the Kolmogorov statistic nsupx{pipe}(Fn-F)(x){pipe}, then there is a constant C such that for any M>0, Pr(K _n>M)≤Cexp(-2M ²). Massart proved that one can take C=2 (DKWM inequality), which is sharp for F continuous. We consider the analogous Kolmogorov-Smirnov statistic for the two-sample case and show that for m=n, the DKW inequality holds for n≥n ₀ for some C depending on n ₀, with C=2 if and only if n ₀≥458.The DKWM inequality fails for the three pairs (m, n) with 1 ≤ m< n≤ 3. We found by computer search that the inequality always holds for n≥ 4 if 1 ≤ m< n≤ 200, and further for n= 2 m if 101 ≤ m≤ 300. We conjecture that the DKWM inequality holds for all pairs m≤ n with the 457 + 3 = 460 exceptions mentioned.