Two-sample Dvoretzky-Kiefer-Wolfowitz inequalities

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

s q r t n s u p_{x} | (F_{n} - F) (x) |

, then there is a finite constant

C

such that for any

M > 0

,

P r (K_{n} > M) l e q C e x p (- 2 M^{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 g e q 458

. For

n_{0} l e q n < 458

it holds for some

C > 2

depending on

n_{0}

. For

m e q n

, the DKWM inequality fails for the three pairs

(m, n)

with

1 l e q m < n l e q 3

. We found by computer search that for

n g e q 4

, the DKWM inequality always holds for

1 l e q m < n l e q 200

, and further that it holds for

n = 2 m

with

101 l e q m l e q 300

. We conjecture that the DKWM inequality holds for pairs

m l e q n

with the

457 + 3 = 460

exceptions mentioned.

Recommendations

Cites Work

Cited In (4)

This page was built for publication: Two-sample Dvoretzky-Kiefer-Wolfowitz inequalities