Two-sample Dvoretzky-Kiefer-Wolfowitz inequalities

Fan Wei, Richard M. Dudley

Research output: Contribution to journalArticlepeer-review

3 Scopus citations


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 2). 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 0 for some C depending on n 0, with C=2 if and only if n 0≥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.

Original languageEnglish (US)
Pages (from-to)636-644
Number of pages9
JournalStatistics and Probability Letters
Issue number3
StatePublished - Mar 2012

All Science Journal Classification (ASJC) codes

  • Statistics and Probability
  • Statistics, Probability and Uncertainty


  • Empirical distribution functions
  • Kolmogorov-Smirnov test


Dive into the research topics of 'Two-sample Dvoretzky-Kiefer-Wolfowitz inequalities'. Together they form a unique fingerprint.

Cite this