6.041 / 6.431 19. Weak Law of Large Numbers

LECTURE 19 Limit theorems – I • Readings: Sections 5.1-5.3; start Section 5.4 • X1, . . . , Xn i.i.d. Mn = X1 + ···+ Xn n What happens as n !"? • Why bother? • A tool: Chebyshev’s inequality • Convergence “in probability” • Convergence of Mn (weak law of large numbers) Chebyshev’s inequality • Random variable X (with finite mean µ and variance !2) !2 = ! (x − µ)2fX(x) dx $ ! −c −" (x − µ)2fX(x) dx + ! " c (x − µ)2fX(x) dx $ c 2 ·P(|X − µ| $ c) P(|X − µ| $ c) % !2 c2 P(|X − µ| $ k!) % 1 k2 Deterministic limits • Sequence an Number a • an converges to a lim n!" an = a “an eventually gets and stays (arbitrarily) close to a” • For every " > 0, there exists n0, such that for every n $ n0, we have |an − a| % ". Convergence “in probability” • Sequence of random variables Yn • converges in probability to a number a: “(almost all) of the PMF/PDF of Yn , eventually gets concentrated (arbitrarily) close to a” • For every " > 0, lim n!" P(|Yn − a| $ ")=0 n0 1/n 1 -1/n pmf of Yn Does Yn converge? Convergence of the sample mean (Weak law of large numbers) • X1,X2,... i.i.d. finite mean µ and variance !2 Mn = X1 + ···+ Xn n • E[Mn]= • Var(Mn)= P(|Mn − µ| $ ") % Var(Mn) "2 = !2 n"2 • Mn converges in probability to µ The pollster’s problem • f: fraction of population that “. . . ” • ith (randomly selected) person polled: Xi = "# $ 1, if yes, 0, if no. • Mn =(X1 + ···+ Xn)/n fraction of “yes” in our sample • Goal: 95% confidence of %1% error P(|Mn − f| $ .01) % .05 • Use Chebyshev’s inequality: P(|Mn − f| $ .01) % !2 Mn (0.01)2 = !2 x n(0.01)2 % 1 4n(0.01)2 • If n = 50,000, then P(|Mn − f| $ .01) % .05 (conservative) Different scalings of Mn • X1,...,Xn i.i.d. finite variance !2 • Look at three variants of their sum: • Sn = X1 + ···+ Xn variance n!2 • Mn = Sn n variance !2/n converges “in probability” to E[X] (WLLN) • Sn &n constant variance !2 – Asymptotic shape? The central limit theorem • “Standardized” Sn = X1 + ···+ Xn: Zn = Sn − E[Sn] !Sn = Sn − nE[X] &n! – zero mean – unit variance • Let Z be a standard normal r.v. (zero mean, unit variance) • Theorem: For every c: P(Zn % c) ! P(Z % c) • P(Z % c) is the standard normal CDF, !(c), available from the normal tables MIT OpenCourseWarehttp://ocw.mit.edu 6.041 /6.431 Probabilistic Systems Analysis and Applied ProbabilityFall 2010 For information about citing these materials or our Terms of Use, visit: http://ocw.mit.edu/terms.