# Why is the convergence rate important?

Basically I am trying to find the intuition behind why in some theorems we care so much about the convergence rate.

For example, many theorems state that the convergence rate is $$\sqrt{n}$$

Why should I care about it?

• This is related to the concept of efficiency (and consistency) of an estimator. If $T_1$ is more efficient than $T_2$ in estimating $\theta$, then $T_1$ converges to $\theta$ more rapidly than $T_2$ does. The $\sqrt n$ you mention indicates a $\sqrt n$-consistent estimator.. – StubbornAtom Apr 22 '20 at 21:12
• Here is a definition of $\sqrt n$-consistency alongwith some intuition: – StubbornAtom Apr 22 '20 at 21:22

Perhaps the two most familiar and most used limit theorems are the Central Limit Theorem (CLT) and the Law of Large Numbers (LLN). Both are useful for proving other theoretical theorems. Here I discuss a few kinds of practical applications in which one hopes sample size is large enough to use CLT and LLN to make useful approximations.

CLT. If $$X_i,$$ for $$i = 1,2,3,\dots,$$ is a random sample from a distribution with mean $$\mu$$ and variance $$\sigma^2 < \infty,$$ then the limiting distribution of $$Z_n = \frac{\sum_{i-1}^nX_i - n\mu}{\sigma\sqrt{n}} = \frac{\bar X -\mu}{\sigma/\sqrt{n}}$$ is the standard normal distribution $$\mathsf{Norm}(0,1).$$

Depending on the shape of the distribution of the $$X_i$$ this convergence can be very fast or rather slow.

Sample from uniform population: For example if $$X_i \sim \mathsf{Unif}(0,1),$$ then the sum $$\sum_{i=1}^{12} X_i$$ of a sample of size of only $$n = 12$$ has very nearly the distribution $$\mathsf{Norm}(6, 1)$$ so $$Z = \sum_{i=1}^{12} X_i - 6$$ is very nearly standard normal.

In the early days of computation this fact was used to sample from the standard normal distribution using only variables from a random number generator that are indistinguishable in practice from independent standard uniform random variables, along with simple arithmetic.

The R code below uses this method to generate 5000 values that are difficult to distinguish from standard normal. The mean of these 5000 values is very nearly $$0$$ and their standard deviation is very nearly 1. Also, a Shapiro-Wilk normality test does not reject the null hypothesis that they are normal.

set.seed(422)
z = replicate(5000, sum(runif(12)) - 6)
mean(z);  sd(z)
[1] 0.001091293  # aprx 0
[1] 1.00467      # aprx 1


However, more sensitive tests do detect that these 5000 values are not exactly standard normal. In particular, all random variables $$Z$$ generated by this method lie between $$\pm 6.$$ So, although the convergence is very fast, twelve observations are not enough for a perfect fit to standard normal.

Sample from exponential population. The extreme right-skewness of exponential random variables causes the convergence guaranteed by the CLT to be rather slow. The mean of a random sample of size 12 from the distribution $$\mathsf{Exp}(1)$$ has the distribution $$\mathsf{Gamma}(\mathrm{shape}=12, \mathsf{rate}=12),$$ which is again noticeably right skewed. [The density function is shown in the left panel of the figure below.]

However, the mean of 100 standard exponential random variables has the distribution $$\mathsf{Gamma}(100,100)$$ [black density in the right panel] which is very nearly $$\mathsf{Norm}(1,0.01)$$ [broken red]. The CLT is "working" as promised, but much more slowly than for sums of uniformly distributed random variables.

Binomial approximation to normal. Also, by applying the CLT to independent Bernoulli random variables with success probability $$p,$$ one can approximate some binomial probabilities using normal distributions. Using binomial probability functions in R and other widely used statistical software, it now easy and often better to get exact binomial probabilities. Even so, normal approximations are still widely used.

Various 'rules of thumb' have been suggested to determine when $$n$$ is large enough for a good normal approximation to $$\mathsf{Binom}(n,p).$$ Many of these try to avoid substantial normal probability outside $$(0, n).$$ Perhaps the most popular rule is that $$\min(np, n(1-p)) \ge 5.$$ (I have seen bounds 3, 10, etc. by less or more fastidious authors.) This rule largely ignores that approximations tend to be better for $$p \approx 1/2$$ (for any $$n)$$ because better fits are possible when the binomial distribution in question is nearly symmetrical.

The two graphs below show a bad normal approximation to $$\mathsf{Binom}(20, .2)$$ on the left and relatively good ones for $$\mathsf{Binom}(10, .5)$$ and $$\mathsf{Binom}(40, .5)$$ center and right.

In particular, if $$X \sim \mathsf{Binom}(20,.2),$$ then the exact probability $$P(1.5 < X < 4.5) = 0.5605,$$ but the normal approximation gives $$0.5289.$$ However, if $$X \sim \mathsf{Binom}(40,.5),$$ we have $$P(9.5 < X < 20.5) = 0.5623$$ exactly, and the approximation gives $$0.5624.$$ In general use with $$\min(np,n(1-p)) \ge 5,$$ one is hopes the approximation is accurate to about two decimal places.

LLN. If $$X_i$$ for $$i = 1,2,3. \dots,$$ is a random sample from a distribution with mean $$\mu$$ and variance $$\sigma^2 < \infty,$$ then the sequence of sample means $$\bar X_n = \frac 1n\sum_{i=1}^n X_i$$ converges in probability to $$\mu.$$ That is, $$\lim_{n\rightarrow\infty} P(|\bar X_n - \mu| < \epsilon) = 1,$$ for any $$\epsilon > 0.$$

The words "large numbers" in the name of the theorem suggests that the theorem is a useful approximation only for large $$n.$$

For example, in a public opinion poll we may get Yes and No answers from subjects. If $$1$$ stands for Yes and $$0$$ for No, then the estimate of Yes opinions in the population $$p$$ is estimated by $$\hat p_n = \bar X_n,$$ the mean of the 0's and 1's. The LLN guarantees that, for sufficiently large $$n,$$ it is very likely that $$\hat p_n$$ is within $$\epsilon$$ of $$p.$$ However, in order for the result to be useful, $$\epsilon$$ needs to be small, say $$\epsilon = 0.02.$$

The following simulation makes a 'trace' of the successive values of $$\hat p_n$$ as we interview increasingly may subjects. Suppose $$p = 0.55.$$ At the start the trace fluctuates widely and then for large $$n$$ it begins to "settle" near $$p.$$

set.seed(2020)
n = 3000;  p = 0.55
x = sample(0:1, n, rep=T, prob=c(1-p,p))
p.hat = cumsum(x)/(1:n)
plot(p.hat, ylim=c(.4,.6), type="l", lwd=2, xaxs="i")
abline(h = p, col="green2")
abline(h = c(p+.02, p-.02), col="red")


This run was a 'lucky' one; it often takes about 2500 interviews before the trace settles to within $$\pm 2\%$$ of the population proportion. That is not to say that the LLN is useless for practical purposes because of its relatively slow convergence, it's just that this theorem doesn't guarantee pollsters an easy life.

• Thank you very much! – Lex Apr 23 '20 at 10:04

Here is an example of how to apply such theorems:

Let us say that we want to fit a function $$g$$ to some data observed and let us assume that the setting is 'good' in the sense that the data really comes from a true function $$f$$ and the observed data points really come from IID random variables or so (assumptions that we can never truly verify nor falsify for real world data!) and the assumptions of the convergence theorem works. Let us say that the theorem states that the error $$|f-g|$$ is roughly $$1/n$$ where $$n$$ is the amount of data points observed. Let us say that we start with $$10$$ data points. Then the error will be roughly $$1/10 = 0.1$$. A number that is small but not 'impressively small' I would say. If we take $$100$$ data points then the error will be roughly $$0.001$$. So far so good.

So we see that knowing the rate of convergence lets us compute a minimal number of data points that we need in order to achieve a certain error. So let us say that we are talking about a physics experiment and the data is some sensor data and we really want that the temperature is captured up to an error of $$0.0001$$ (otherwise the experiment will fail or something). Then how many data points do we need to capture? Given the convergence rate we know that we need roughly $$10000$$ data points.

This is one of the applications of the convergence rate but it has more in theory I guess... If I remember correctly there are situations like this: If some $$g$$ converges 'fast enough' then it might help you showing (in a purely mathematical sense) that the target function $$f$$ lies in a special space of functions. That in turn has to be read as 'if we want a theorem like this with functions $$g$$ then we MUST assume that the target function $$f$$ lies in that special space, otherwise it will not work'.

NB: To be precise: Actually we usually want to fit a sequence of functions $$g_n$$ to $$f$$ but $$g_n$$ comes from some kind of training routine involving $$n$$ data points.

• This Answer appeared while I was fussing with the graphics in mine. Too tired to read it last night. Returned here this morning. Read it. Nice approach. (+1) – BruceET Apr 22 '20 at 17:34
• Thank you very much! – Lex Apr 29 '20 at 11:22