# Empirical distribution function

File:Empirical CDF.png
The blue line shows an empirical distribution function. The black bars represent the samples corresponding to the ecdf and the gray curve is the true cumulative distribution function.

In statistics, the empirical distribution function, or empirical cdf, is the cumulative distribution function associated with the empirical measure of the sample. This cdf is a step function that jumps up by 1/n at each of the n data points. The empirical distribution function estimates the true underlying cdf of the points in the sample and converges with probability 1 according to the Glivenko–Cantelli theorem. A number of results exist to quantify the rate of convergence of the empirical cdf to the underlying cdf.

## Definition

Let (x1, …, xn) be iid real random variables with the common cdf F(t). Then the empirical distribution function is defined as [1][2]

$ \hat F_n(t) = \frac{ \mbox{number of elements in the sample} \leq t}n =  \frac{1}{n} \sum_{i=1}^n \mathbf{1}\{x_i \le t\}, $


where 1{A} is the indicator of event A. For a fixed t, the indicator 1{xi ≤ t} is a Bernoulli random variable with parameter p = F(t), hence <math style="vertical-align:-.3em">\scriptstyle n \hat F_n(t)[/itex] is a binomial random variable with mean nF(t) and variance nF(t)(1 − F(t)). This implies that <math style="vertical-align:-.3em">\scriptstyle \hat F_n(t)[/itex] is an unbiased estimator for F(t).

## Asymptotic properties

By the strong law of large numbers, the estimator <math style="vertical-align:-.3em">\scriptstyle\hat{F}_n(t)[/itex] converges to F(t) as n → ∞ almost surely, for every value of t: [1]

$ \hat F_n(t)\ \xrightarrow{a.s.}\ F(t),$


thus the estimator <math style="vertical-align:-.3em">\scriptstyle\hat{F}_n(t)[/itex] is consistent. This expression asserts the pointwise convergence of the empirical distribution function to the true cdf. There is a stronger result, called the Glivenko–Cantelli theorem, which states that the convergence in fact happens uniformly over t: [3]

$ \|\hat F_n-F\|_\infty \equiv \sup_{t\in\mathbb{R}} \big|\hat F_n(t)-F(t)\big|\ \xrightarrow{a.s.}\ 0.$


The sup-norm in this expression is called the Kolmogorov–Smirnov statistic for testing the goodness-of-fit between the empirical distribution <math style="vertical-align:-.3em">\scriptstyle\hat{F}_n(t)[/itex] and the assumed true cdf F. Other norm functions may be reasonably used here instead of the sup-norm. For example, the L²-norm gives rise to the Cramér–von Mises statistic.

The asymptotic distribution can be further characterized in several different ways. First, the central limit theorem states that pointwise, <math style="vertical-align:-.3em">\scriptstyle\hat{F}_n(t)[/itex] has asymptotically normal distribution with the standard <math style="vertical-align:-.3em">\sqrt{n}[/itex] rate of convergence:[1]

$ \sqrt{n}\big(\hat F_n(t) - F(t)\big)\ \ \xrightarrow{d}\ \ \mathcal{N}\Big( 0, F(t)\big(1-F(t)\big) \Big).$


This result is extended by the Donsker’s theorem, which asserts that the empirical process <math style="vertical-align:-.3em">\scriptstyle\sqrt{n}(\hat{F}_n - F)[/itex], viewed as a function indexed by <math style="vertical-align:-.3em">\scriptstyle t\in\mathbb{R}[/itex], converges in distribution in the Skorokhod space <math style="vertical-align:-.3em">\scriptstyle D[-\infty, +\infty][/itex] to the mean-zero Gaussian process <math style="vertical-align:-.3em">\scriptstyle G_F = B \circ F[/itex], where B is the standard Brownian bridge.[3] The covariance structure of this Gaussian process is

$ \mathrm{E}[\,G_F(t_1)G_F(t_2)\,] = F(t_1\wedge t_2) - F(t_1)F(t_2).$


The uniform rate of convergence in Donsker’s theorem can be quantified by the result known as the Hungarian embedding: [4]

$ \limsup_{n\to\infty} \frac{\sqrt{n}}{\ln^2 n} \big\| \sqrt{n}(\hat F_n-F) - G_{F,n}\big\|_\infty < \infty, \quad \text{a.s.}$


Alternatively, the rate of convergence of <math style="vertical-align:-.3em">\scriptstyle\sqrt{n}(\hat{F}_n-F)[/itex] can also be quantified in terms of the asymptotic behavior of the sup-norm of this expression. Number of results exist in this venue, for example the Dvoretzky–Kiefer–Wolfowitz inequality provides bound on the tail probabilities of <math style="vertical-align:-.3em">\scriptstyle\sqrt{n}\|\hat{F}_n-F\|_\infty[/itex]:[4]

$ \Pr\!\Big( \sqrt{n}\|\hat{F}_n-F\|_\infty > z \Big) \leq 2e^{-2z^2}.$


In fact, Kolmogorov has shown that if the cdf F is continuous, then the expression <math style="vertical-align:-.3em">\scriptstyle\sqrt{n}\|\hat{F}_n-F\|_\infty[/itex] converges in distribution to <math style="vertical-align:-.3em">\scriptstyle\|B\|_\infty[/itex], which has the Kolmogorov distribution that does not depend on the form of F.

Another result, which follows from the law of the iterated logarithm, is that [4]

$ \limsup_{n\to\infty} \frac{\sqrt{n}\|\hat{F}_n-F\|_\infty}{\sqrt{2\ln\ln n}} \leq \frac12, \quad \text{a.s.}$


and

$ \liminf_{n\to\infty} \sqrt{2n\ln\ln n} \|\hat{F}_n-F\|_\infty = \frac{\pi}{2}, \quad \text{a.s.}$


## References

1. ^ a b c van der Vaart, A.W. (1998). Asymptotic statistics. Cambridge University Press. p. 265. ISBN 0-521-78450-6.
2. ^ PlanetMath
3. ^ a b van der Vaart, A.W. (1998). Asymptotic statistics. Cambridge University Press. p. 266. ISBN 0-521-78450-6.
4. ^ a b c van der Vaart, A.W. (1998). Asymptotic statistics. Cambridge University Press. p. 268. ISBN 0-521-78450-6.