19
$\begingroup$

I'm aware of the Law(s) of Large Numbers, concerning the means. However, intuitively, I'd expect not just the mean, but also the observed relative frequencies (or the histogram, if we have a continuous distribution) to approach the theoretical PMF/PDF as the number of trials goes into infinity.

  1. Is my intuition wrong? Always or only for some degenerate cases (e.g. Cauchy)?
  2. If not, is there a special name for that law?
$\endgroup$
2
  • 9
    $\begingroup$ If for a histogram, you are interested in $\mathbb P(a < X \le b)$ over some particular interval $(a,b]$, then this is a consequence of the Law of Large Numbers and can be shown using an indicator variable $\endgroup$
    – Henry
    Dec 9, 2021 at 13:02
  • $\begingroup$ @Henry law of large numbers directly applies here you mean? $\endgroup$
    – BCLC
    Jan 17 at 15:07

4 Answers 4

25
$\begingroup$

While the law of large numbers is framed in terms of "means" this actually gives you a large amount of flexibility to show convergence of other types of quantities. In particular, you can use indicator functions to get convergence results for the probabilities of any specified event. To see how to do this, suppose we start with a sequence $X_1,X_2,X_3 ,... \sim \text{IID } F_X$ and note that the law of large numbers says that (in various probabilistic senses) we have the following convergence:

$$\frac{1}{n} \sum_{i=1}^n X_i \rightarrow \mathbb{E}(X) \quad \quad \quad \quad \quad \text{as } n \rightarrow \infty.$$

In the sections below I will show how you can use this basic result to show that the empirical CDF converges to the true CDF of the underlying distribution in certain useful senses. This will also show you how the law of large numbers can be applied in a creative way to prove convergence results for other things that don't look like "means" of quantities (but actually are).


Pointwise convergence of the empirical CDF to the true CDF: In your question you are interested in the convergence of the empirical distribution function to the true distribution function $F_X$. Let's start by looking at a particular point $x$ by examining the sequence of values $Y_1,Y_2,Y_3 ,...$ defined by $Y_i \equiv \mathbb{I}(X_i \leqslant x)$. This latter sequence is also IID, so the law of large numbers says that (in various probabilistic senses) we have the following convergence:

$$\frac{1}{n} \sum_{i=1}^n Y_i \rightarrow \mathbb{E}(Y) \quad \quad \quad \quad \quad \text{as } n \rightarrow \infty.$$

Now, at the point $x$ the empirical distribution function for the sequence $\mathbf{X}$ and the true CDF for the distribution can be written respectively as:

$$\begin{align} \hat{F}_n(x) &\equiv \frac{1}{n} \sum_{i=1}^n \mathbb{I}(X_i \leqslant x) = \frac{1}{n} \sum_{i=1}^n Y_i, \\[12pt] F_X(x) &\equiv \mathbb{P}(X_i \leqslant x) = \mathbb{E}(Y). \\[6pt] \end{align}$$

(The latter result follows from the fact that $\mathbb{E}(Y) = \mathbb{P}(Y=1)$ for any indicator variable $Y$.) We can therefore re-frame the previous convergence statement from the law of large numbers to give the pointwise convergence result:

$$\hat{F}_n(x) \rightarrow F_X(x) \quad \quad \quad \quad \quad \text{as } n \rightarrow \infty.$$

You can see that this demonstrates that the empirical CDF converges pointwise to the true CDF for IID data; this is a direct consequence of the law of large numbers. Specifically, the weak law of large numbers establishes pointwise convergence in probability, and the strong law of large numbers establishes pointwise convergence almost surely.


Uniform convergence of the empirical CDF to the true CDF: To go further than the above result, you need to use the uniform law of large numbers—or some other similar theorem—to establish uniform convergence of the empirical CDF to the true CDF. If you use the uniform law of large numbers then you can establish uniform convergence of the empirical CDF under some restrictive assumptions on the underlying CDF. However, there is actually a stronger theorem called the Glivenko–Cantelli theorem that establishes uniform convergence of the empirical CDF to the true CDF (almost surely) for any IID sequence of data. That is, the theorem proves that:

$$\sup_x | \hat{F}_n(x) - F_X(x) | \overset{\text{a.s}}{\rightarrow} 0 \quad \quad \quad \quad \quad \text{as } n \rightarrow \infty.$$

If you would like to learn more about this part, it is worth having a look at the proofs of the uniform law of large numbers and the Glivenko–Cantelli theorem to see how each of them work to establish uniform convergence. The former theorem is broader, but it comes with some restrictions on the input function. The latter theorem applies specifically to the empirical CDF of IID data, but it establishes uniform convergence (almost surely) without any additional assumptions.

$\endgroup$
2
  • $\begingroup$ The argument of the Glivenko-Cantelli theorem applies quite broadly: the same proof shows that you can go from pointwise convergence of an empirical CDF to uniform convergence for non-IID sequences as well, and the idea ('bracketing') is behind some more general uniform LLN results $\endgroup$ Dec 14, 2021 at 20:50
  • $\begingroup$ @ThomasLumley: Yes, indeed. Here I am thinking of the original theorem from Glivenko/Cantelli (which I'm pretty sure was for IID only), but I take it you are looking at the class of theorems later established by other authors using the same general argument. I think this hinges on whether you consider "the GC theorem" to be just the original theorem, or the class of theorems that came later, or the class of all theorems that can in principle be derived by this general method, etc. (A bit like the CLT.) But yes, you are right that this can be extended to the non-IID case. $\endgroup$
    – Ben
    Dec 14, 2021 at 21:16
22
$\begingroup$

You may be asking for the Glivenko-Cantelli theorem.

https://en.wikipedia.org/wiki/Glivenko%E2%80%93Cantelli_theorem

Note that this is about cumulative distribution functions, i.e., for data sets relative frequencies that observations are below any given value $x$, or by implication in any interval $[x_1,x_2]$. Histograms are not a standard basis for such a result, as there are many ways to set up a histogram (bar widths etc.), whereas the cdf is uniquely defined.

$\endgroup$
1
  • 5
    $\begingroup$ (+1) The Glivenko-Cantelli theorem is a result of uniform convergence hence is stronger than pointwise convergence of the empirical cdf. $\endgroup$
    – Xi'an
    Dec 9, 2021 at 13:04
6
$\begingroup$

As an alternative to Glivenko–Cantelli, you can look at Sanov's theorem, which uses the Kullback–Leibler divergence as the distance measure. For any set $A$ of frequency distributions, this theorem upper-bounds the probability that the observed frequency distribution $f$ (for $n$ IID instances of a random variable with distribution $q$ on an alphabet $X$) lies in $A$, as follows:

$$P[f\in A] \leq (n+1)^{\left|X\right|} 2^{-d_\mathrm{min} n},$$

where $d_\mathrm{min} = \min_{f\in A} D_\mathrm{KL}(f||q)$ is the minimum KL divergence between frequencies in $A$ and the true distribution $q$. To apply this to directly address the question asked, this result implies that if $\mathcal{B}^{D_\mathrm{KL}}_d(q)$ denotes the "ball" of frequency distributions with KL divergence $<d$ from the true distribution $q$, we can upper-bound the probability of getting a frequency distribution outside this ball as

$$P[f\notin \mathcal{B}^{D_\mathrm{KL}}_d(q)] \leq (n+1)^{\left|X\right|} 2^{-d n}.$$

This expression has the advantage of being an explicit bound for finite sample size, in case you need something more than an asymptotic convergence result. (A weaker option is provided by the asymptotic equipartition property, but the set considered in that theorem potentially includes some number of frequency distributions that are "very far" from the true distribution.)

$\endgroup$
0
2
$\begingroup$

We can define an indicator function that gives whether an observation is inside or outside of an interval, which will have a Bernoulli distribution, and for a sample of multiple observations we have a binomial distribution. We can then apply the CLT to show that the mean converges to the probability mass of the original PDF in the interval. The error in absolute terms converges uniformly to zero, but I don't think the error as a percentage of the expected probability does.

$\endgroup$

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.