6 Asymptotics

In this chapter we cover some fundamental results from probability theory concerning asymptotics of random sequences.

6.1LLN and CLT¶

The law of large numbers and central limit theorem are two of the pillars of econometrics and statistics. Below we review both theorems, starting with the necessary concepts of convergence in probability and distribution.

6.1.1Convergence of Random Vectors¶

A sequence of random vectors $\{\boldx_n\}$ is said to converge in probability to a random vector $\boldx$ if,

In symbols, we write $\boldx_n \toprob \boldx$. In the scalar case $\|\boldx_n - \boldx\|$ reduces to $|x_n - x|$.

Part (i) is an immediate consequence of the definition. Other proofs are touched on in the exercises. For more details, see, for example, Çinlar (2011).

The scalar sequence $\{x_n\}$ is said to converge to $x$ in mean square if

and we write $x_n \toms x$. Unlike convergence in probability, for convergence in mean square to be defined we require that our variables have finite second moments.

Part (i) follows from Chebyshev’s inequality . In particular, from monotonicity of $\PP$ and (4.19) we get

Part (ii) is implied by the next fact.

As we’ll see later, (6.3) plays an important role in statistics. Its verification is an exercise. (The proof is straightforward. If you want more of a challenge, try to obtain it as a consequence of (iv) of fact 5.2.4.)

6.1.2The Law of Large Numbers¶

The law of large numbers (LLN) is one of the most fundamental theorems of both probability and statistics. As a prelude to the LLN, let’s consider the effects of averaging over independent random quantities. We’ll take the perspective of investors, who often diversify their portfolios in order to decrease risk. To formalize this idea let

• $x_n$ be the payoff from holding one dollar of asset $n$,

• $\EE x_n = \mu$ and $\var[x_n] = \sigma^2$ for all $n$, and

• $\cov[x_j, x_k] = 0$ when $j \neq k$.

If we hold just asset 1, then the payoff is $x_1$, the expected payoff is $\mu$ and the variance is $\sigma^2$. If we diversify by spreading one dollar evenly over $N$ of these assets, our payoff is

The expected payoff is unchanged at

But the variance declines at rate $\frac{1}{N}$ because

The important equality here is the third one, which holds because of the zero covariance between assets. In this step $N^2$ terms become $N$ terms. To summarize,

Now imagine someone is kind enough to sell us an unlimited quantity of such assets, so we can diversify without limit. By taking $N \to \infty$ and combining (6.5) with fact 6.1.2 we obtain a proof of the law of large numbers:

Actually we haven’t fully proved the LLN because we assumed existence of second moments above, while theorem 6.1.1 assumes only existence of the first moment. However, the proof above captures the spirit of the LLN most cleanly. (See theorem 8.3.5 of Dudley (2002) for the general case.)

At first glance, the law of large numbers (6.6) appears to only be a statement about the sample mean but in fact it’s self-improving: We can go from (6.6) to arbitrary functions of random variables, or even random vectors. In particular, if $\boldx$ is any random vector, $\{\boldx_n\}$ are IID copies and $h \colon \RR^N \to \RR$ is any $\bB$-measurable function such that $h(\boldx)$ is integrable, then

This can be confirmed by letting $y_n := h(\boldx_n)$ and then applying theorem 6.1.1. The independence of $\{y_n\}$ is confirmed by fact 5.1.10. That each $y_n$ has the same distribution as $y := h(\boldx)$ follows from

The law of large numbers applies to probabilities as well as expectations. To see this, fix $B \subset \bB(\RR^N)$, and consider the probability $\PP\{\boldx \in B\}$. Letting $h$ be the indicator function $h(\bolds) = \1_B(\bolds) = \1\{\bolds \in B\}$ and using the principle that expectations of indicators equal probabilities of events, we have

Combining this equality with (6.7), we see that if $\{\boldx_n\}$ is IID with distribution $P$, then

In words, the fraction of the sample that falls in $B$ converges to the probability that the distribution assigns to $B$.

6.1.2.1An Illustration¶

To illustrate the law of large numbers, consider flipping a coin until 10 heads have occurred. The coin is not fair: The probability of heads is 0.4. Let $x$ be the number of tails observed in the process. This random variable is known to have the negative binomial distribution, with $\EE x =15$. The LLN predicts that if we simulate a large number of observations of $x$ and take the average, we get a value close to 15. Running the Julia code in listing 1 gives outcomes consistent with this claim.^[1]

num_reps = 10^6
outcomes = Vector{Float64}(undef, num_reps)

for i in 1:num_reps
    num_tails = num_heads = 0
    while num_heads < 10
        b = rand()
        num_heads = num_heads + (b < 0.4)   # +1 with prob 0.4
        num_tails = num_tails + (b >= 0.4)  # +1 with prob 0.6
    end
    outcomes[i] = num_tails
end

println(sum(outcomes) / num_reps)

Figure 6.2 shows what can happen when the finite first moment condition in the LLN is not enforced. The draws are from the standard Cauchy distribution, which fails to have a finite first moment. The top panel shows observations and the bottom shows a running sample mean of observations $\bar x_N$, with $N$ on the horizontal axis. A few extreme observations dominate the average and the sample mean does not converge.^[2]

6.1.3Convergence in Distribution¶

As a prelude to the central limit theorem we need to review convergence in distribution. This is conceptually quite different to convergence of random variables, whether in probability or mean square. For example, the distributions $\nN(0, 1)$ and $\nN(10^{-10}, 1)$ are very close, but independent draws from these respective distributions need not be.

Let $\{P_n\}$ and $P$ be distributions on $\RR^K$ in the sense of Section 5.1.2. To represent the notion that $P_n$ converges to $P$ we could require that $P_n(B) \to P(B)$ for all $B \in \bB(\RR^K)$. However, this turns out to be rather strict and also indifferent to closeness in the sense of Euclidean norm. For example, suppose that $P_n$ is a distribution on $\RR$ that puts all mass on $\frac{1}{n}$, while $P$ puts all mass on $0$. Intuition suggests that $P_n \to P$, but if we take $B = (0, \infty)$, we have $P_n(B) = 1$ for all $n$, while $P(B) = 0$.

For this reason the common notion of convergence of distributions, which is called weak convergence, requires only that $P_n(B) \to P(B)$ for all "continuity sets" in $\RR^K$. There’s an equivalent way to phrase this that’s easier to work with in applications: We say that $\{P_n\}$ converges weakly to $P$ if

and write $P_n \tow P$. For the definition of these integrals see Section 5.1.3.3. Continuity of $h$ enforces respect for the topology on $\RR^K$, while boundedness is imposed only to ensure that the integrals are finite.

Sometimes densities are easier to work with than CDFs. In this connection, the following sufficient condition can be useful.

Let $\{\boldx_n\}$ and $\boldx$ be random vectors. We say that $\boldx_n \to \boldx$ in distribution if their respective distributions converge weakly. This convergence is symbolized by $\boldx_n \tod \boldx$. Thus

In view of fact 5.1.7, this is equivalent to

Part (i) of fact 6.1.6 is called the continuous mapping theorem. Part (ii) is called the Cramér–Wold theorem, or the Cramér–Wold device. The next result is sometimes known as Slutsky’s theorem.

An immediate but useful consequence is that

6.1.4The Central Limit Theorem¶

The central limit theorem is among the most striking and important results in all of mathematics. Relative to the LLN, it requires an additional second moment condition. Here’s a statement of the theorem in the scalar IID case.

The meaning of $\tod$ here is that the distribution of the left-hand side $\tow \nN(0, \sigma^2)$. We can interpret (6.9) as follows: On one hand, $(\bar x_N - \mu) \toprob 0$ by the LLN; on the other, $\sqrt{N} \to \infty$. If we take the product, these two competing terms just balance. Remarkably, the distribution of the product approaches a zero-mean Gaussian as $N \to \infty$, regardless of the distribution of $x$.

We’ll skip the proof of the CLT (which provides little intuition) and turn to simulation. For starters, see figure 6.4, where $Q_N :=$ the distribution of the left-hand side of (6.9) for $N=1,\ldots,5$. The initial distribution $Q=Q_1$ is multi-modal, and was constructed as a convex combination of three beta distributions. The CLT predicts that $Q_N \tow \nN(0, \sigma^2)$, where $\sigma^2 = \int s^2 Q_1(\diff s)$. Note how quickly the bell shape emerges, despite the irregularity of the initial distribution.

Another common statement of the central limit theorem is as follows: If all the conditions of theorem 6.1.2 are satisfied, then

Exercise 6.4.6 asks you to confirm this.

The convergence in (6.10) is illustrated by listing 2, the output of which is given in figure 6.5. The listing generates 5,000 observations of the random variable $z_N$ defined in (6.10), where each $x_n$ is $\chi^2(5)$. (The mean of this distribution is 5, and the variance is $2 \times 5 = 10$.) The observations of $z_N$ are stored in the vector outcomes. The figure histograms this vector and then superimposes the density of the $\nN(0, 1)$ distribution.

import numpy as np
import scipy.stats as st

num_reps = 5000
outcomes = np.empty(num_reps)
N, k = 1000, 5     # k = degrees of freedom
chi = st.chi2(k)

for i in range(num_reps):
    xvec = chi.rvs(N)
    outcomes[i] = np.sqrt(N / (2 * k)) * (xvec.mean() - k)

# code to histogram outcomes and plot st.norm.pdf
# for comparison is omitted here

6.2Extensions¶

In this section we cover some extensions to the classical LLN and CLT.

6.2.1Convergence of Random Matrices¶

The notion of convergence in probability discussed in Section 6.1.1 extends naturally to matrices. Let $\{\boldX_n\}_{n=1}^{\infty}$ be a sequence of random $N \times K$ matrices. We say that $\boldX_n$ converges to a random $N \times K$ matrix $\boldX$ in probability and write $\boldX_n \toprob \boldX$ if

where $\| \cdot \|$ is the matrix norm defined in Section 3.3.5.

In part (iii) of fact 6.2.1, the matrices $\boldA_n$ and $\boldA$ are nonrandom and convergence is in matrix norm. Note that part (v) can be obtained from two applications of part (iii).

In econometrics we often use the vector version of Slutsky’s theorem:

6.2.2Vector-Valued LLNs and CLTs¶

The scalar LLN and CLT that we discussed above extend to the vector case in a natural way. For example,

Here $\frac{1}{N} \sum_{n=1}^N \boldx_n$ should be understood in terms of vector addition and scalar multiplication. Thus $\bar \boldx_N$ is a convex combination of the sample points in $\RR^K$. Figure 6.6 illustrates this in two dimensions. The green dot is $\boldmu$. The black dots are realizations of $\boldx_1,\ldots,\boldx_N$. The red dot is the sample mean $\frac{1}{N} \sum_{n=1}^N \boldx_n$. By (6.11), the red dot converges to the green dot.

The vector LLN in theorem 6.2.1 follows from the scalar LLN. To see this, let $\boldx_n$ be as in theorem 6.2.1, let $\bolda$ be any constant vector in $\RR^K$, let $y_n := \bolda^\T \boldx_n$ and let $y := \bolda^\T \boldx$. The sequence $\{y_n\}$ is IID (see fact 5.1.10) with the same distribution as $y$. By the scalar LLN (theorem 6.1.1), we have

At the same time,

We have shown that

The claim $\bar \boldx_N \toprob \boldmu$ now follows from fact 6.1.1.

The vector CLT in theorem 6.2.1 also follows from the scalar case and the proof is quite similar. See exercise 6.4.10.

These results can be further extended to random matrices. In fact we will need a matrix LLN in our investigation of linear regression. Here’s a suitable result:

The proof is straightforward: By fact 6.2.1, to prove (6.13), it suffices to show that $\frac{1}{N} \sum_{n=1}^N \boldX_n \bolda \toprob \EE [ \boldX] \bolda$ for any conformable vector $\bolda$. Since $\boldX_n \bolda$ is a vector with expectation $\EE [ \boldX ] \bolda$, this is immediate from the vector LLN in theorem 6.2.1.

6.2.3The Delta Method¶

The asymptotic normality result in the central limit theorem is preserved under linear transformations, as follows from fact 6.2.2. It turns out that the same thing is true even for functions that are only locally almost linear—that is, for differentiable functions. This greatly extends the power and reach of the central limit theorem.

Here $\nabla g(\boldtheta)$ is the gradient vector of $g$ at $\boldtheta$, which is defined as

In the scalar case, (6.14) translates to

In statistical settings, the technique of obtaining asymptotic distributions by appealing to theorem 6.2.2 is called the delta method. We will see its importance later on. The proof of theorem 6.2.2 is based on a Taylor expansion of $g$ around the point $\theta$. See theorem 3.1 of Vaart (2000). Exercise 6.4.9 walks you through some of the key ideas.

6.3Further Reading¶

For high quality treatments of the law of large numbers and the central limit theorem see, for example, Dudley (2002), Taylor (1997), Durrett (2010), Pollard (2002), DasGupta (2008), or Çinlar (2011). An advanced but thorough treatment of the delta method can be found in Vaart (2000).

6.4Exercises¶

6.4.1Solutions to Selected Exercises¶