DVORETZKY-KIEFER-WOLFOWITZ INEQUALITY

In the theory of probability, the 'Dvoretzky-Kiefer-Wolfowitz inequality' predicts how quickly an empirically determined distribution function will converge to the distribution from which empirical samples are drawn. It is named after Aryeh Dvoretzky, Jack Kiefer, and Jacob Wolfowitz.

Contents

The DKW inequality

An example

References

The DKW inequality

Let ''X_i'' be i.i.d. from some distribution with distribution function ''F''. Let ''F_n'' be the associated empirical distribution functions. The Dvoretzky-Kiefer-Wolfowitz inequality states that
:$$
mathrm{P} left( sup_t | F_n(t) - F(t)| > arepsilon
ight) leq 2e^{-2narepsilon^2}.

This strengthens the Glivenko-Cantelli theorem by quantifying the rate of convergence.

An example

Suppose that we wish to draw a large enough sample to ensure that the deviation between our empirical distribution and the true distribution is less than or equal to 10%, with 90% confidence.
Setting ε = 0.1 in the DKW inequality, we see that we must find ''n'' such that
:$$
2e^{-0.02 n} = 1 - 0.9 quad Rightarrow quad 0.02 ln{n} - ln{2} = ln{10} quad Rightarrow quad n = 50ln{20}.

By plugging in the approximate natural logarithm of 20 (which is 3, very nearly) we see that a sample size of 150 is large enough to estimate the distribution function with 10% precision and 90% confidence.

References

★ {{citation
| last1 = Dvoretzky
| first1 = A.
| authorlink1 = Aryeh Dvoretzky
| last2 = Kiefer
| first2 = J.
| authorlink2 = Jack Kiefer (mathematician)
| last3 = Wolfowitz
| first3 = J.
| authorlink3 = Jacob Wolfowitz
| title = Asymptotic minimax character of the sample distribution function and of the classical multinomial estimator
| journal = Annals of Mathematical Statistics
| volume = 27
| year = 1956
| pages = 642–669
| id =

★ All of Statistics: A Concise Course in Statistical Inference, , Larry A., Wasserman, Springer-Verlag, ,