Limit Theorems: Law of Large Numbers and the Central Limit Theorem

9.07 Introduction to Statistics for Brain and Cognitive Sciences Emery N. Brown Lecture 7 Limit Theorems: Law of Large Numbers and the Central Limit Theorem I. Objectives Understand the logic behind the Law of Large Numbers and its relation to the frequency interpretation of probability theory Understand how to prove the Weak Law of Large Numbers Understand the logic behind the Central Limit Theorem Understand how to prove a version of the Central Limit Theorem Understand how to construct approximations to the distribution of the sums of random variables using the Central Limit Theorem Understand the conditions under which the Gaussian distribution can be used to approximate binomial and Poisson probabilities II. Law of Large Numbers To motivate our study of the Law of Large Numbers we begin with an example. Example 7.1. An Opinion Poll. An election is to be conducted for President of the Society for Neuroscience and there are two candidates for the office: Candidate A and Candidate B. If we poll n voters and we assume that each individual polled reports truthfully his/her voting intention then how sure can we be that the fraction of people who report that they will vote for Candidate A is a good “guess” (estimate) of the number who will actually vote for Candidate A? Our intuition is that the fraction of people who say they are going to vote for Candidate A should be a good “guess” of the proportion of votes that Candidate A will get in the election. Furthermore, the more people we poll, the better our “guess” should be. With what we know already, we can formalize our intuition. If we let p denote the fraction of people who will vote for Candidate A, we can define X i to be the Bernoulli random variable which is 1 if person i is going to vote for Candidate A and 0 otherwise. Let X  n1 n  Xi . X is the fraction of people i 1 polled who vote for Candidate A. Our intuition is that X is a good guess for p. This intuition is what we colloquially call the “Law of Averages.” To begin thinking formally about this problem we recall that a statistic is any function of a set of data. Because experimental data are random and the statistic is a function of the data, the statistic is also a random variable. It therefore, has a probability density or probability mass function. If we observe random variables X1, X 2 ,..., X n such that the X i 's are independent and all have the same probability distribution, then the collection X1, X 2 ,..., X n is called a random sample or simply a sample. The sample mean is one of the most basic statistics and we recall that it is defined as X  n1 n  Xi . (7.1) i 1 Remark 7.1. If the mean and variance of the X i 's are respectively  and variance  2 , then by Propositions 6.1 and 6.2 we have E ( X )  n1 n  E( X i )   (7.2) i 1 Var ( X )  n Var ( X i )  2  X  1 n2 (7.3) n i 1 (7.4) . The Law of Large Numbers tells us that as the sample size increases the probability that X  n1 n  X i is close to the mean  approaches 1. To prove this, we establish first two i 1 technical results. A. Some Technical Results Proposition 7.1 (Markov Inequality). If X is a random variable that takes on only nonnegative values, then for any a  0 Pr( X  a)  Proof: To see this note that E[ X ]     0   a xf ( x)dx   xf ( x)dx  a a 0  (7.5) xf ( x)dx   a E[ X ] . a   a xf ( x)dx (7.6) f ( x)dx  a Pr( x  a ). Proposition 7.2 (Chebyshev’s Inequality). If X is a random variable with mean  and variance  2 and k  0 , then Pr{| X   | k}  2 k2 (7.7) . Proof: Let Y | X   | then Y  0 and by the Markov Inequality Pr{| X   | k}  Pr{Y  k}  Pr{Y 2  k 2 }  E (Y 2 ) k2  2 k2 Having established Chebyshev’s Inequality we can prove the Weak Law of Large Numbers. 2 (7.8) B. The Law of Large Numbers Proposition 7.3 Law of Large Numbers (Weak). Let X1, X 2 ,..., X n be an independent, identically distributed (i.i.d.) sample from a population with mean  and variance  2 . Then the probability that the difference between the sample mean and true mean remains greater than any finite amount goes to zero as the sample size n goes to infinity. Proof: If we pick   0, then we can Pr(| X   |  )  1  Pr(| X   |  ). (7.9) Using Chebyshev’s Inequality, for   0, Pr(| X   |  )  Var ( X ) 2  2  2n  0 (7.10) as n goes to infinity. Hence, Pr(| X   |  )  1  Pr(| X   |  )  1. Example 7.2 The Law of Large Numbers and the Behavior of the Sample Mean. To gain intuition about what is occurring with the Law of Large Numbers, we consider (Figure 7A) the mean of n observations from a gamma distribution with   2 and   1 (Figure 7A ,column 1) and an arbitrary distribution (Figure 7A, column 2) for n  1, 2, 4,16 and 400. We can see that in the case of the gamma distribution (Figure 7A, column 1) as n grows, the distribution of the sample mean gets more and more tightly clustered around the true mean. Similarly, for the arbitrary distribution an analogous phenomenon is observed (Figure 7A, column 2). 3 Figure 7A. Illustration of the Law of Large Number by averaging n observations from a gamma distribution with   2 and   1 (column 1) and a bimodal distribution (column 2) for n  1, 2, 4,16 and 400. Reproduced from Dekking et al. (2002). Example 7.1 (continued). Can we use Chebyshev’s Inequality to figure out how large n should be such that we are 95% certain that the difference between X and  is less than 0.005? We will answer this question in Homework Assignment 6. Remark 7.2. From the result in Proposition 7.3, we say that X converges in probability to  . The best result known is the Strong Law of Large Numbers. It states that Pr(| X   | 0)  1. (7.11) as long as  exists. This means X is guaranteed to converge to  in the usual numerical sense. Therefore, we are correct in thinking that an observed X is close to the true mean. This is not guaranteed by convergence in probability. The statement, “the sample mean is close to the true mean” does not apply to a particular realization. In contrast, the Strong Law of Large Numbers addresses what occurs to the result of a single realization of the data (Pawitan, 2001, pp. 231-232). Remark 7.3. What is apparent from Figure 7A is that the sample mean is getting closer to the true mean. This is a first-order effect because it involves the mean (first moment). As the number of samples became large in Figure 7A, the shape of the distribution became more symmetric or “Gaussian-like”. We might think of this effect as a second-order effect because it tells us something about the variability (second moment) of the statistic or the shape of its distribution. The second-order effect addresses the question of what is the behavior of the random variable X as it approaches its mean? That is, can we characterize its probability density? The Central Limit Theorem allows us to answer these questions. III. The Central Limit Theorem A. Motivation The Central Limit Theorem is the most important theorem in probability theory and concerns the behavior of the sample mean as n grows indefinitely large. Before stating the Central Limit Theorem, we give an example to motivate its derivation along with some technical results we will need to prove it. Example 7.3 A Fast Spiking Neuron. Consider a neuron with a constant rate  that obeys a Poisson probability law. Assume that  = 40 Hz. In a 1-second interval how likely are we to observe 40, 41, or 42 spikes? We first develop a Gaussian approximation to compute this result then we compare it with the exact result computed directly from the Poisson probability mass function with  = 40 Hz. To construct a Gaussian approximation we study the behavior of a sequence of Poisson random variables such that X n Poisson(n ) . and n  . We have that  E( X n ) Var ( X n ) n , and hence, E ( X n ) and Var ( X n )  . Therefore, we must standardize X n to get a limiting distribution. Let 4 Zn  X n  E( X n ) Zn  We have E(Zn )  0 and (7.12) 1 [Var ( X n )] 2 X n  n (7.13) 1 n2 t2 Var (Zn )  1. We show that M zn (t )  e 2 which by the Continuity Theorem (Proposition 7.4, stated below) means that Fzn ( zn )  F ( z)  ( z). Recall from Lecture 6 (Result 6.7 and Remark 6.10) that if X has mgf M x (t ) and Y  a  bX , then M y (t )  eat M x (bt ). t We have M xn (t )  en (e 1) and hence, Zn  n 2 X n  n2 , 1 1 a  n2 and b  n 2 1 1 1 2 M zn (t )  en t M xn (n 2 t ) 1 (7.14) 1 2 n  et en (e 1 t n 2 1) . We have that 1 2 log M zn (t )  t n2  n (etn  1). 1 (7.15) Recall that ex    k 0 xk x 2 x3  1 x    ...  ... k! 2! 3! (7.16) so that Eq. 7.15 can be written as 1 log M zn (t )  t n2  n (1  1 1  t n2  t n2   t 1 2 n  t2 t3   ...  ...  1) 3 2n 3! 2 n t2 t3   ...  ... 1 2 3!n2 t2 t3  1  ...  ... 2 6n2 5 (7.17) t2 t2 As n  , log M zn (t )  and thus M zn (t )  e 2 . By the Continuity Theorem stated below, we 2 conclude that Fzn ( zn )  Fz ( z)  ( z). In Homework Assignment 6, we present an alternative derivation of this result by showing directly that as n   the Poisson pmf Pzn ( zn )   ( z) the pdf of a standard Gaussian random variable. Applying this result to our fast spiking neuron in Example 7.3 we have Gaussian Approximation  39.5   X   42.5    Pr(40  X  42)  Pr          42.5  40   39.5  40  Pr  z  40 40   (7.18)   (0.395)   (0.079)  0.6537  0.4685  0.1852, where we have used the continuity correction defined below in section III E. Exact Poisson Solution Pr( X  40, 41 or 42)   40k e40  0.1828. k  40 k! 42 (7.19) We see that in this case, the approximation is very reasonable. B. Proof of the Central Limit Theorem To prove the Central Limit Theorem, we need to state first a definition, a theorem and a technical result. Definition 7.1. If X1,..., X n is a sequence of random variables with cumulative distribution functions F1, F2 ,... and let X be a random variable with distribution function F . The sequence X n converges in distribution to X if lim Fn ( x)  lim Pr( X n  x)  Pr( X  x)  F ( x). n n 6 (7.20) Proposition 7.4 (Continuity Theorem). Let Fn be a sequence of cumulative distribution functions with corresponding moment generating functions M n (t ). Let F ( X ) be a cumulative distribution function with moment generating function M (t ). If M n (t )  M (t ) for all t in an open interval containing zero, then Fn ( X )  F ( X ) at all continuity points of F ( X ). Result 7.1. If an  a, then a lim (1  n )n  ea . n (7.21) n This limit is established in advanced calculus courses. Proposition 7.5. Central Limit Theorem: Let X1, X 2 ,..., X n be a sequence of independent random variables having mean  and variance  2 , common distribution function F ( x) and moment generating function M (t ) defined in a neighborhood of zero. Let X  n1 n  X i as n   i 1 1 Pr( n 2 ( X  )   x)  ( x). (7.22) Proof: To simplify the calculations, we assume   0. Let n  Xi Sn  i 1 and Zn  Sn 1  n2 (7.23) . Because the X1,..., X n are independent, the mgf of Sn is and by Result 6.7 and Remark 6.10 M sn (t )  [M (t )]n M zn (t )  [ M ( t n 1 2 )]n . (7.24) The Taylor series expansion of M (s) about 0 is 1 s3 M '''(0) M ( s)  M (0)  sM '(0)  s 2 M ''(0)   ...  ... 2 3 Now M (0)  1, E( X )  0, M '(0)  0 and M ''(0)   2 . We have 7 (7.25) M( 1 t t3 )  [1  ( 1 )2  2   ...  ... 1 2  n2 n 3( n 2 )3 t 1 2 (7.26)  1 2 3 t t   ...  ... 3 2n 3 3 n 2 Note that t3 3 3 n 2  2t  0 1 t2 3 3 n 2 2n 3 (7.27) as n  . The same is true for any term larger than t 3 . Hence, M zn (t )  [1  t2 n ] 2n (7.28) for n large. By Result 7.1 and Proposition 7.4 M zn t2 (t )  e 2 (7.29) which is the mgf of a standard Gaussian random variable. C. Applications of the Central Limit Theorem Example 7.3 (continued). The Gaussian Approximation to the Poisson Distribution. In the case of the Poisson distribution with parameter  we take the Gaussian mean and standard 1 deviation to be    and    2 respectively. This approximation is considered to be quite accurate according to Port (1994, p. 685) for   25. That is, we must have on average 25 events per unit time for the Gaussian distribution to be a good approximation to the Poisson distribution. Kass (2006) says the approximation is good for   15. We will investigate which is correct in Homework Assignment 6. Hence consider a one second time interval and a neuron whose spike rate is on the order of 25 Hz. If its spiking activity obeys a Poisson process, then the distribution of the spiking activity on the one second interval could be approximated by the Gaussian distribution. We see already that the approximation is good for   40. What are the implications of these observations for the recent paper by Wu et al. Neural Computation (2006) where Gaussian distributions are used to model the probability distributions of MI spiking activity? Example 7.4 The Gaussian Approximation to the Binomial. If n is large and p is not too close to either 0 or 1, then we can approximate the cumulative distribution function for the Binomial pmf as 8 Pr( X  k )  ( k   ) (7.30) 1 where   np and   [np(1  p)] 2 . A commonly used rule of thumb that is somewhat conservative at least for 0.2  p  0.8 is that it is reasonably accurate provided np  5 and n(1  p)  5. How does this compare to the rule for the Poisson approximation to the binomial? Example 2.1 (continued). Let us return to the Graybiel example to illustrate the effect of the CLT in the case of Bernoulli trials (which ultimately provides the Gaussian approximation to the binomial distribution). For n  40 trials we have 40 values of 0 (incorrect responses) and 1 (correct responses). Suppose p  0.55 then we would expect in today’s experiment there would be 22 correct responses. However, when we examined the distribution of the sample mean (the proportion of correct responses) it turned out to appear very close to Gaussian. See Figure 2D. We can study the central limit theorem by simulation using the binomial distribution. Let us pick p  0.2, since for p  0.55, the binomial pmf in Figure 2D looked very Gaussian. From Example 2.1, this distribution could be motivated by the observation that on the first day of the experiment, the animal had 8 correct out of 40. Therefore, we might assume that on the second day, the probability of a correct response is 0.2 for any trial. We begin with X i ' s being equal to either 0 or 1. For example, with n  40, we would have 40 values of 0 or 1. Suppose that p  0.2, so that we would expect, on average, 8 of the 40 values to be 1’s. Imagine a histogram of these 0’s and 1’s. Certainly with only two bins, these 40 values would not look Gaussian. However, when we look at the distribution of the sample mean, it turns out to look very close to Gaussian. Here, from our initial 40 0’s and 1’s, we would obtain one value of the sample mean, which would be the proportion of 1’s in the sample. Now we have to imagine having a large number of such samples, say 100 of them. That is, we take 100 samples of size 40 and for each sample we compute the mean of the 40 observations. If we made a histogram of those 100 sample means we would get something nicely approximating a Gaussian distribution. We can study the theoretical distribution of the sample mean. For instance, for n  4 the possible values of X are 0, 0.25. 0.5, 0.75 and 1 and can be plot p( X  0), p( X  0.25),..., p( X  1) versus 0, 0.25. 0.5, 0.75 and 1. This is shown in the first plot in Figure 7B. This plot essentially tells us what the heights of the histogram bar would be if we did have a histogram of the 100 sample means for a sample size of n  4. The distribution of X does not look very close to Gaussian. However, as the rest of Figure 7B shows, as n increases, the distribution of X looks more and more Gaussian. What we have just done is study the distribution of X for Bernoulli trials for several values of n with p  0.20. The distribution of Sn  n  xi is Binomial and the picture of its i 1 distributions would look just like the pictures we had for the distribution of X except the x-axis would be multiplied by n. In particular, as n gets large, we see the distribution looks Gaussian. This effect of the CLT may be considered as an explanation for the Gaussian approximation to the binomial. 9 These results have allowed us to obtain an approximate distribution for one of our most important statistics, namely the sample mean. Can we use the CLT to predict a reasonable (most probable) range for the number of correct responses we can expect to see in today’s experiment if the animal does not learn? Alternatively, can we combine the CLT with the 2  0.95 rule to construct a predictive confidence interval for p in today’s experiment? How well 3 does the rule for assessing the accuracy of the Gaussian approximation to the binomial apply? That is, based on the rule for application of the Gaussian approximation to the binomial, would we have predicted that the Gaussian approximation would have worked well for p  0.55 and n  40? How good is the approximation? Can we quantify the degree of agreement or goodnessof-fit? We will answer these questions over the course of the next couple of weeks. Figure 7B. Central Limit Theorem illustrated for the binomial n  4,10, 25,100 and p  0.2. D. Normalization in the Central Limit Theorem 1 The normalization for the sum of the random variables in the central limit theorem is n 2 . To illustrate the importance of the choice of normalization, we consider (Figure 7C) sums of 1 n random variables from a gamma distribution with   2 and   1, and a normalization of n 4 1 (column 1), of n 2 (column 2) and of n (column 3) for n  1, 2, 4,16 and 100 . When the 1 normalization is n 4 (Figure 7C, column 1), we see that while the distribution is fairly symmetric by the time n  16 the value of the distribution at the mode is tending to infinity. At the other extreme when the normalization is n (Figure 7C, column 3), the random behavior in the 1 process is completely squashed by the time n  16. In contrast, when the normalization is n 2 (Figure 7C, column 2), we see that the behavior of the process continues to become 1 symmetric and it remains random as n  , suggesting that n 2 is the correct normalization. 10 Figure 7C. Rate of Convergence for the average of n random draws from a gamma distribution with   2 1 1 and   1 and a normalization of n 4 (column 1), of n 2 Dekking et al. (2002). (column 2) and of n (column 3). Reproduced from E. Continuity Correction Suppose that X is a discrete random variable taking on only integer values and that the pmf of X is approximated as a Gaussian random variable with mean  and variance  2 . Then if a and b are integers, the correction of continuity to use the Gaussian distribution is Pr( X  b)  ([b  1/ 2   ] /  ) Pr(a  X )  1  ([a  1/ 2   ] /  ) (7.31) Pr(a  X  b)  ([b  1/ 2   ] /  )  ([a  1/ 2   ] /  ). instead of Pr( X  b)  ([b   ]/  ) Pr(a  X )  1  ([a   ]/  ) Pr(a  X  b)  ([b   ]/  )  ([a   ]/  ). 11 (7.32) respectively. We applied the continuity correction in the Gaussian approximation to the Poisson distribution in Example 7.3. F. A More General Central Limit Theorem and an Example of Central Limit Behavior in a Physical System We can state a more general version of the Central Limit Theorem. Proposition 7.6. Central Limit Theorem (General). If X1, X 2 ,..., X n are independent random variables, possibly having different distributions but with no individual X i making a dominant contribution to the mean X , then for n sufficiently large, the distribution of X is approximately 1 Gaussian with mean X and standard deviation Var ( X ) 2 . This version of the Central Limit Theorem helps to explain why the Gaussian distribution arises so often in statistical theory, and also why it seems to fit, at least roughly, so many observed phenomena. It says that whenever we average a large number of small independent effects, the result will be distributed as a Gaussian random variable. While the Central Limit Theorem involves the sample mean, it drives the large-sample behavior of most statistics: a statistic derived from a sample may usually be written, approximately, as some function (possibly a complicated function) of the sample mean, and that usually produces approximate Gaussian nature of the statistic itself. An important example is the maximum likelihood estimator, which is very widely used, and which we will discuss in Lecture 9. Example 3.2 Magnetoencephalography (continued). Why should the MEG measurements in Figure 3E be distributed as a Gaussian random variable? It is an empirical observation that when the magnetic field inside the shielded environment is measured at a given SQUID sensor the distribution of the background measurements is Gaussian. The central limit theorem offers a theoretical reason for this observation. To see this, we note that MEG measures the magnetic fields in a given location. Anywhere there are current dipoles magnetic fields are generated. The current dipoles that we are interested in are those emanating from the brain. Remember that magnetic fields or forces are a byproduct of electric currents or moving charged particles. In any environment there are always electric currents flowing around. The SQUID sensors are exquisitely sensitive. The fields they detect are on the order of 1015 Tesla (femtotesla). Therefore, if you imagine the local magnetic fields being recorded near a given SQUID sensor in a room designed to have a homogeneous magnetic field, there are a lot of local current fluctuations giving rise to local magnetic field fluctuations. If the environment is homogeneous, then no one local fluctuation will dominate (Lindeberg-Feller condition) and the local magnetic field is simply the vector sum of the local fluctuations. This later point gives the linear superposition. Hence, Gaussian structure is not surprising. Moreover, note that the observations are not independent (See Homework Assignment 6). IV. Summary The Law of Large Numbers states that as the number of observations in a sample of data increases the sample mean converges to the population mean whereas the Central Limit Theorem tells us that sums of random variables properly normalized can be approximated as a Gaussian distribution. This completes our section on probability theory. In the next half of the course we will study statistical theory and its application to several problems in brain and cognitive sciences making uses of the several results in probability theory we have developed. 12 Acknowledgments I am grateful to Paymon Hosseini for making Figures 7A and 7C and to Uri Eden for making Figure 7B, to Julie Scott and Riccardo Barbieri for technical assistance in preparing this lecture and to Jim Mutch for very helpful proofreading and comments. Sections of this lecture have been taken with permission from the class notes for Statistical Methods in Neuroscience and Psychology written by Robert Kass in the Department of Statistics at Carnegie Mellon University. Figures 7A and 7C are reproduced from Dekking et al. (2002). References DeGroot MH, Schervish MJ. Probability and Statistics, 3rd edition. Boston, MA: Addison Wesley, 2002. Dekking FM, Kraaikamp C, Lopuhaa HP, Meester LE. A Modern Introduction to Probability and Statistics. London: Springer-Verlag, 2002. Pawitan Y. In All Likelihood: Statistical Modeling and Inference Using Likelihood. London: Oxford, 2001. Port SC. Theoretical Probability for Applications. New York: John Wiley & Sons, 1994. Rice JA. Mathematical Statistics and Data Analysis, 3rd edition. Boston, MA, 2007. Literature Reference Wu W, Gao Y, Bienenstock E, Donoghue JP, Black MJ. Bayesian population decoding of motor cortical activity using a Kalman filter. Neural Computation 18(1):80-118, 2006. Website Reference Kass RE, Chapter 2: Probability and Random Variables 13