Let $X_1,X_2,\ldots,X_n$ be i.i.d. random variables in $\mathbb{R}$ with common cumulative distribution function (CDF) $F(x)$. The empirical approximation to $F(x)$ is defined as follows:

$$\hat{F}_n(x)=\frac{1}{n}\sum_{i=1}^n\mathbf{1}_{\{X_i\leq x\}}(x)\tag{1}$$

where $\mathbf{1}_A(x)$ is an indicator function: unity when $x\in A$ and zero otherwise.

The Glivenko-Cantelli Theorem states that $\hat{F}_n(x)$ converges to $F(x)$ uniformly, that is, $\sup_{x\in\mathbb{R}}|\hat{F}_n(x)-F(x)|\rightarrow 0$ almost surely as $n\rightarrow\infty$. The Dvoretzky–Kiefer–Wolfowitz inequality quantifies the rate of convergence as follows: $P(\sup_{x\in\mathbb{R}}|\hat{F}_n(x)-F(x)|>\epsilon)\leq2e^{-2n\epsilon^2}$.

I am wondering if anything is known about the distributions of the errors in the empirical approximation of a CDF: that is, how is the random variable $\varepsilon_n(x)\equiv\hat{F}_n(x)-F(x)$ distributed? Is there perhaps asymptotic Gaussianity here, maybe for some classes of $F(x)$?

Here is the reason for my question: suppose I draw $nM$ random variables i.i.d. that have the common CDF $F(x)$ where $m=1,2,\ldots,M$, and compute $M$ empirical approximations as follows:

$$\hat{F}_{n,m}(x)=\frac{1}{n}\sum_{i=n(m-1)+1}^{nm}\mathbf{1}_{\{X_i\leq x\}}(x)\tag{2}.$$

Now I need to approximate $F(x_0)$ for a given $x_0$. Which approach would yield a better estimate: the average $\frac{1}{M}\sum_{m=1}^M\hat{F}_{n,m}(x_0)$ over the approximations in (2), or using $nM$ samples in constructing the approximation in (1)? If it helps, the distribution that I am trying to approximate is a mixture of binomial random variables.


I believe your two empirical approximations are the same: aren't they both the total fraction of observations less than or equal to $x_0$?

As for the question of asymptotic normality, Donsker's Theorem gives the main result in this direction, namely that the processes $\sqrt{n}\left(\hat{F}_n(x)-F(x)\right)$ converge in an appropriate sense to the process $B(F(x))$, where $B$ is a standard Brownian bridge.

  • $\begingroup$ Oh, right! Didn't think about approximations in (1) and (2) in that way. The reason for (2) was to estimate the variance of the approximation for $F(x_0)$. Thanks for the pointer to the Donsker's Theorem! I think the first sentence of the "History" section of the article is very relevant to what I am doing, however, I have a question about it that I will post separately (and will link to this question). Again, thanks! $\endgroup$ – Bullmoose Mar 24 '14 at 18:32
  • $\begingroup$ Follow-up question posted: mathoverflow.net/questions/161282/… $\endgroup$ – Bullmoose Mar 24 '14 at 19:03

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.