Dvoretzky-Kiefer-Wolfowitz inequality

From Wikipedia, the free encyclopedia

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.

[edit] The DKW inequality

Let Xi be i.i.d. from some distribution with distribution function F. Let Fn be the associated empirical distribution functions. The Dvoretzky-Kiefer-Wolfowitz inequality states that

\mathrm{P} \left( \sup_t | F_n(t) - F(t)| > \varepsilon \right) \leq 2e^{-2n\varepsilon^2}.

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

[edit] 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 = 50\ln{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 90% precision and 90% confidence.

[edit] References

  • Dvoretzky, A.; Kiefer, J. & Wolfowitz, J. (1956), “Asymptotic minimax character of the sample distribution function and of the classical multinomial estimator”, Annals of Mathematical Statistics 27: 642–669, MR0083864 
  • Wasserman, Larry A. (2004). All of Statistics: A Concise Course in Statistical Inference. Springer-Verlag. ISBN 0-387-40272-1.