Dvoretzky--Kiefer--Wolfowitz Inequalities for the Two-sample Case

Abstract

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 $\sqrt{n}{\sup }_x|(F_n-F)(x)|$, then there is a finite constant $C$ such that for any $M>0$, $\mathrm{Pr}(K_n>M)\le C\exp (-2M^2).$ Massart proved that one can take C=2 (DKWM inequality) which is sharp for $F$ continuous. We consider the analogous Kolmogorov--Smirnov statistic $K{S}_{m,n}$ for the two-sample case and show that for $m=n$, the DKW inequality holds with C=2 if and only if $n\ge 458$. For $n_0\le n<458$ it holds for some $C>2$ depending on $n_0$. For $m\ne n$, the DKWM inequality fails for the three pairs $(m,n)$ with $1\le m<n\le 3$. We found by computer search that for $n\ge 4$, the DKWM inequality always holds for $1\le m<n\le 200$, and further that it holds for $n=2m$ with $101\le m\le 300$. We conjecture that the DKWM inequality holds for pairs $m\le n$ with the $457+3=460$ exceptions mentioned.

32 pages; 8 tables. Reasons for updating v1: Some probabilities between 10^{-14} and 10^{-8} which previously were computed to relatively few reliable significant digits have been replaced by much more accurately computed upper bounds. All the facts stated in the original version are confirmed

Cited by in corpus (1)

• Multi-waveform cross-correlation search method for intermediate-duration gravitational waves from gamma-ray bursts