EECS 126 - Probability and Random Processes - J. Walrand

LAW OF LARGE NUMBERS & CENTRAL LIMIT THEOREM

·         Key Ideas

·         Weak Law of Large Numbers

·         Strong Law of Large Numbers

·         Central Limit Theorem

·         Approximate Central Limit Theorem

·         Confidence Interval

Key Ideas

 

We started the course by saying that, in the long term, about half of the flips of a fair coin yield tail.  This is our intuitive understanding of probability.  The law of large number explains that our model of uncertain events conforms to that property.  The central limit theorem tells us how fast this convergence happens. 

Weak Law of Large Numbers

 

Let {Xn, n ³ 1} be i.i.d. random variables with mean m and finite variance s2.  Let also Yn = (X1 + … + Xn)/n be the sample mean of the first n random variables Then

 

P(|Yn - m| > e) ® 0 as n ® ¥, for all e > 0.

 

This result says that if n is large, then the random variable (X1 + … + Xn)/n is likely to be close to the mean m of the Xn.

 

Proof: Chebychev’s inequality.

 

Strong Law of Large Numbers

 

Under the same assumptions as stated for the weak law, we have

 

Yn ® a.s. m as n ® ¥, as n ® ¥.

This result is stronger than the weak law:

·        Mathematically because almost sure C implies convergence in probability;

·        In applications because it states that Yn becomes a better and better estimate of m as n increases (always, you cannot be unlucky!).

 

Proof: See EE226A or STAT205A.

Central Limit Theorem

                    

Under the same assumptions,

Zn = [Yn – m]n½  ® D  N(0, s2) as n ® ¥.

 

This result says (roughly) that the error Yn – m is of order s/ n½.  Thus, if one makes four times more observations, the error on the mean estimate is reduced by a factor of 2.

 

Equivalently,

[Yn – m]n½/s  ® D  N(0, 1) as n ® ¥.

Approximate Central Limit Theorem

                    

Under slightly stronger assumptions,

[Yn – m]n½/sn  ® D  N(0, 1) as n ® ¥

where

(sn)2 = [(X1 – Yn)2 + … + (Xn – Yn) 2]/n.

 

This result is useful because it says we can use an estimate of the variance. 

Confidence Intervals

                    

Using the approximate CLT, we can construct a confidence interval about our sample mean estimate.  Indeed, we can say that when n gets large,

P(|[Yn – m]n½/sn| > 2) » 5%,

so that

P(m Î [Yn – 2sn/n½, Yn + 2sn/n½ ]) » 95%.

We say that

[Yn – 2sn/n½, Yn + 2sn/n½ ] is a 95%-confidence interval for the mean.

Similarly,

 

[Yn – 2.6sn/n½, Yn + 2.6sn/n½ ] is a 99%-confidence interval for the mean.

 

 

[Recall that if X = N(0, 1), then P(|X| > 2.6) = 1%, P(|X| > 2) = 5%, and P(|X| > 1.7) = 10%.]

 

Jean Walrand – November 2003  --- INDEX