Partial Sums and the Central Limit Theorem

The central limit theorem and the law of large numbers are the two fundamental theorems of probability. Roughly, the central limit theorem states that the distribution of the sum of a large number of independent, identically distributed variables will be approximately normal, regardless of the underlying distribution. The importance of the central limit theorem is hard to overstate; indeed it is the reason that many statistical procedures work.

Partial Sum Processes

Definitions

Note that by convention,

Y 0 0

, since the sum is over an empty index set. The random process

Y Y 0 Y 1 Y 2

is called the partial sum process associated with

X

. Special types of partial sum processes have been studied in many places in this project; in particular see

Recall that in statistical terms, the sequence

X

corresponds to sampling from the underlying distribution. In particular,

X 1 X 2 X n

is a random sample of size

n

from the distribution, and the corresponding sample mean is

Stationary, Independent Increments

Show that if $m n$ then $Y n Y m$ has the same distribution as $Y n m$ . Thus the process $Y$ has stationary increments.

Show that if $n 1 n 2 n 3$ then $Y n 1 Y n 2 Y n 1 Y n 3 Y n 2$ is a sequence of independent random variables. Thus the process $Y$ has independent increments.

Conversely, suppose that $V V 0 V 1$ is a random process with stationary, independent increments, in the sense of Exercise 1 and Exercise 2. Define $U i V i V i 1$ for $i 12$ . Show that $U$ is a sequence of independent, identically distributed variables and that $V$ is the partial sum process associated with $U$ .

Thus, partial sum processes are the only discrete-time random processes that have stationary, independent increments. An interesting, and much harder problem, is to characterize the continuous-time processes that have stationary independent increments. The Poisson counting process has stationary independent increments, as does the Brownian motion process.

Moments

Suppose that $n$ . Use basic properties of expected value and variance to show that

$Y n n μ$
$Y n n σ 2$

Suppose that $n$ and $m$ with $m n$ . Use basic properties of covariance and the stationary and independence properties to verify the following results. Hint: Note that $Y n Y m Y n Y m$ .

$Y m Y n m σ 2$
$Y m Y n m n$
$Y m Y n m σ 2 m n μ$

Suppose that $X$ has moment generating function $G$ . Show that $Y n$ has moment generating function $G n$

Distributions

Suppose that $X$ has either a discrete distribution or a continuous distribution with probability density function $f$ . Recall that the probability density function of $Y n$ is $f n f f f$ , the convolution power of $f$ of order $n$ .

More generally, we can use the stationary and independence properties to find the joint distributions of the partial sum process:

Suppose that $n 1 n 2 n k$ . Show that $Y n 1 Y n 2 Y n k$ has joint probability density function

f n 1 n 2 n k y 1 y 2 y k f n 1 y 1 f n 2 n 1 y 2 y 1 f n k n k 1 y k y k 1, y 1 y 2 y k k

The Central Limit Theorem

We will now make the central limit theorem precise. From Exercise 4, we cannot expect

Y n

itself to have a limiting distribution. Note that

Thus, to obtain a limiting distribution that is not degenerate, we need to consider, not

Y n

itself, but the standard score of

Y n

. Thus, let

Show that

$Z n 0$
$Z n 1$

Show that $Z n$ is also the standard score of the sample mean $M n$ :

Z n M n μ σ n

The central limit theorem states that the distribution of the standard score

Z n

converges to the standard normal distribution as

n

. A special case of the central limit theorem (to Bernoulli trials), dates to Abraham De Moivre. The term central limit theorem was coined by George Pólya in 1920.

Proof of the Central Limit Theorem

We need to show that

F n z Φ z

n

for each

z

, where

F n

is the distribution function of

Z n

and

Φ

the distribution function of the standard normal distribution. Equivalently we will show that

where

χ n

is the characteristic function of

Z n

, and the expression on the right is the characteristic function of the standard normal distribution.

The following exercises sketch the proof of the central limit theorem. Ultimately, the proof hinges on a generalization of a famous limit from calculus.

Suppose that $a n a$ as $n$ . Show that

1 a n n n a as n

Now let

χ

denote the characteristic function of the standard score of a sample variable

X

, and let

χ n

denote the characteristic function of the standard score

Z n

Show that

$χ 0 1$
$χ 0 0$
$2 χ 0 1$

Show that

Z n 1 n i 1 n X i μ σ

Use properties of characteristic functions to show that

χ n t χ t n n, t

Use Taylor's theorem (named after Brook Taylor) to show that

χ t n 1 1 2 2 χ s n t 2 n where s n t n

In the context of previous exercise, show that $s n 0$ and hence $2 χ s n 1$ as $n$ .

Finally, show that

χ n t 1 1 2 2 χ s n t 2 n n 1 2 t 2 as n

Normal Approximations

The central limit theorem implies that if the sample size

n

is large then the distribution of the partial sum

Y n

is approximately normal with mean

n μ

and variance

n σ 2

. Equivalently the sample mean

M n

is approximately normal with mean

μ

and variance

σ 2 n

. The central limit theorem is of fundamental importance, because it means that we can approximate the distribution of certain statistics, even if we know very little about the underlying sampling distribution.

Of course, the term large is relative. Roughly, the more abnormal the basic distribution, the larger

n

must be for normal approximations to work well. The rule of thumb is that a sample size

n

of at least 30 will usually suffice; although for many distributions smaller

n

will do.

Let $Y$ denote the sum of the variables in a random sample of size 30 from the uniform distribution on $01$ . Find normal approximations to each of the following:

$13 Y 18$
The 90th percentile of $Y$ .

Let $M$ denote the sample mean of a random sample of size 50 from the distribution with probability density function $f x 3 x 4, x 1$ . This is a Pareto distribution, named for Vilfredo Pareto. Find normal approximations to each of the following:

$M 1.6$
The 60th percentile of $M$ .

The Continuity Correction

A slight technical problem arises when the sampling distribution is discrete. In this case, the partial sum also has a discrete distribution, and hence we are approximating a discrete distribution with a continuous one.

Suppose that $X$ takes integer values and hence so does the partial sum $Y n$ . Show that for any $h 01$ and $k$ , the event $k h Y n k h$ is equivalent to the event $Y n k$ .

In the context of the previous exercise, different values of

h

lead to different normal approximations, even though the events are equivalent. The smallest approximation would be 0 when

h 0

, and the approximations increase as

h

increases. It is customary to split the difference by using

h 0.5

for the normal approximation. This is sometimes called the continuity correction. The continuity correction is extended to other events in the natural way, using the additivity of probability.

Let $Y$ denote the sum of the scores of 20 fair dice. Compute the normal approximation to $60 Y 75$ .

In the dice experiment, set the die distribution to fair, select the sum random variable $Y$ , and set $n 20$ . Run the simulation 1000 times, updating every 10 runs. Compute the following and compare with the result in the previous exercise:

$60 Y 75$
The relative frequency of the event $60 Y 75$

Normal Approximation to the Gamma Distribution

Y k

has the gamma distribution with shape parameter

k

and scale parameter

b 0

then

where

X 1 X 2 X k

is a sequence of independent variables, each having the exponential distribution with scale parameter

b

. Since

X i b

and

X i b 2

, it follows that if

k

is large, the gamma distribution can be approximated by the normal distribution with mean

k b

and variance

k b 2

. The same statement actually holds when

k

is not an integer; more precisely, the distribution of the standardized variable below converges to the standard normal distribution as

k

In the gamma experiment, vary $k$ and $b$ and note the shape of the probability density function. With $k 10$ and $b 2$ , run the experiment 1000 times with an update frequency of 10 and note the apparent convergence of the empirical density function to the true density function.

Suppose that $Y$ has the gamma distribution with shape parameter $k 10$ and scale parameter $b 2$ . Find normal approximations to each of the following:

$18 Y 23$
The 80th percentile of $Y$ .

Normal Approximation to the Chi-Square Distribution

The chi-square distribution with degrees of freedom

n

is the gamma distribution with shape parameter

k n 2

and scale parameter

b 2

. From the previous subsection, it follows that if

n

is large the chi-square distribution can be approximated by the normal distribution with mean

n

and variance

2 n

. More precisely, if

Y n

has the chi-square distribution with

n

degrees of freedom, then the distribution of the standardized variable below converges to the standard normal distribution as

n

In the chi-square experiment, vary $n$ and note the shape of the density function. With $n 20$ , run the experiment 1000 times with an update frequency of 10 and note the apparent convergence of the empirical density function to the probability density function.

Suppose that $Y$ has the chi-square distribution with $n 20$ . Find normal approximations to each of the following:

$18 Y 25$
The 75th percentile of $Y$ .

Normal Approximation to the Binomial Distribution

Y n

has the binomial distribution with trial parameter

n

and success parameter

p 01

, then

where

X 1 X 2 X n

is a Bernoulli trails sequence with success parameter

p

, that is, a sequence of independent indicator variables with

X i 1 p

for each

i

. It follows that if

n

is large, the binomial distribution with parameters

n

and

p

can be approximated by the normal distribution with mean

n p

and variance

n p 1 p

. The rule of thumb is that

n

should be large enough for

n p 5

and

n 1 p 5

. More precisely, the distribution of the standardized variable

Z n

given below converges to the standard normal distribution as

n

In the binomial timeline experiment, vary $n$ and $p$ and note the shape of the probability density function. With $n 50$ and $p 0.3$ , run the simulation 1000 times, updating every 10 runs. Compute the following:

$12 Y 16$
The relative frequency of the event $12 Y 16$

Suppose that $X$ has the binomial distribution with parameters $n 50$ and $p 0.3$ . Compute the normal approximation to $12 Y 16$ (don't forget the continuity correction) and compare with the results of the previous exercise.

Normal Approximation to the Poisson Distribution

where

X 1 X 2 X n

is a sequence of independent variables, each with the Poisson distribution with parameter 1. Since

X i X i 1

, it follows from the central limit theorem that if

n

is large, the Poisson distribution with parameter

n

can be approximated by the normal distribution with mean

n

and variance

n

. The same statement holds when

n

is not an integer; more precisely, the distribution of the standardized variable below converges to the standard normal distribution as

n

Suppose that $Y$ has the Poisson distribution with mean 20.

Compute the true value of $16 Y 23$ .
Compute the normal approximation to $16 Y 23$ .

In the Poisson experiment, vary the time and rate parameters $t$ and $r$ (the parameter of the Poisson distribution in the experiment is the product $r t$ ). Note the shape of the density function. With $r 5$ and $t 4$ , run the experiment 1000 times with an update frequency of 10 and note the apparent convergence of the empirical density function to the probability density function.

Normal Approximation to the Negative Binomial Distribution

where

X 1 X 2 X k

is a sequence of independent variables, each having the geometric distribution on

with success parameter

p

. Since

X i 1 p

and

X i 1 p p 2

, it follows that if

k

is large, the negative binomial distribution can be approximated by the normal distribution with mean

k p

and variance

k 1 p p 2

. More precisely, the distribution of the standardized variable below converges to the standard normal distribution as

k

In the negative binomial experiment, vary $k$ and $p$ and note the shape of the probability density function. With $k 5$ and $p 0.4$ , run the experiment 1000 times with an update frequency of 10 and note the apparent convergence of the empirical density function to the true density function.

Suppose that $Y$ has the negative binomial distribution with trial parameter $k 10$ and success parameter $p 0.4$ . Find normal approximations to each of the following:

$20 Y 30$
The 80th percentile of $Y$ .

Partial Sums with a Random Number of Terms

Suppose now that

N

is a random variable taking values in

, with finite mean and variance. Then

is a random sum of the independent, identically distributed variables. That is, the terms are random of course, but so also is the number of terms

N

. We are primarily interested in the moments of

Y N

Independent Number of Terms

Suppose first that

N

, the number of terms, is independent of

X

, the sequence of terms. Computing the moments of

Y N

is a good exercise in conditional expectation.

Show that

$Y N N N μ$
$Y N N μ$

Show that

$Y N N N σ 2$
$Y N N σ 2 N μ 2$

Let $H$ denote the probability generating function of $N$ . Show that the moment generating function of $Y N$ is $H G$

$t Y N N G t N$
$t Y N H G t$

Wald's Equation

Some of these results generalize to the case where the random number of terms

N

is a stopping time for the sequence

X

. This means that the event

N n

depends only on (technically, is measurable with respect to)

X 1 X 2 X n

for each

n

Prove Wald's equation named after Abraham Wald: $Y N N μ$ .

Show that $Y N i 1 X i i N$
Show that $X i$ and $i N$ are independent for each $i$ .
Conclude that $X i i N μ N i$
Suppose that $X i 0$ for each $i$ . Take expected values term by term in (a) to establish Wald's equation in this special case. The interchange of sum and expected value is justified by the monotone convergence theorem.
Now establish Wald's equation in general by using the dominated convergence theorem

4. Partial Sums and the Central Limit Theorem

Partial Sum Processes

Definitions

Stationary, Independent Increments

Moments

Distributions

The Central Limit Theorem

Proof of the Central Limit Theorem

Normal Approximations

The Continuity Correction

Normal Approximation to the Gamma Distribution

Normal Approximation to the Chi-Square Distribution

Normal Approximation to the Binomial Distribution

Normal Approximation to the Poisson Distribution

Normal Approximation to the Negative Binomial Distribution

Partial Sums with a Random Number of Terms

Independent Number of Terms

Wald's Equation