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. Probability is the likelihood or chance that something is the case or will happen In Statistics, an empirical distribution function is a cumulative probability distribution function that concentrates probability 1/ n at each of the It is named after Aryeh Dvoretzky, Jack Kiefer, and Jacob Wolfowitz. Jack Carl Kiefer ( January 25, 1924 – August 10, 1981) was an American statistician. Jacob Wolfowitz PhD ( March 19, 1910 &ndash July 16, 1981) was a Polish -born American Statistician

The DKW inequality

Let X_i be i.i.d. from some distribution with distribution function F. "IID" or "iid" redirects here For other uses see IID (disambiguation. This article describes the distribution function as used in physics 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)| > \varepsilon \right) \leq 2e^{-2n\varepsilon^2}.$

This strengthens the Glivenko-Cantelli theorem by quantifying the rate of convergence. The study of empirical processes is a branch of Mathematical statistics and a sub-area of Probability theory.

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. In Statistics, a confidence interval (CI is an interval estimate of a Population parameter. 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.

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, MR 0083864

Wasserman, Larry A. Jack Carl Kiefer ( January 25, 1924 – August 10, 1981) was an American statistician. Jacob Wolfowitz PhD ( March 19, 1910 &ndash July 16, 1981) was a Polish -born American Statistician Mathematical Reviews is a journal and online database published by the American Mathematical Society that contains brief synopses (and occasionally evaluations of many (2004). All of Statistics: A Concise Course in Statistical Inference. Springer-Verlag. ISBN 0-387-40272-1.

© 2009 citizendia.org; parts available under the terms of GNU Free Documentation License, from http://en.wikipedia.org
network: | |