18.05 S22 Class 6: Appendix

Appendix Class 6, 18.05 1 Introduction In this appendix we give more formal mathematical material that is not strictly a part of 18.05. This will not be on homework or tests. We give this material to emphasize that in doing mathematics we should be careful to specify our hypotheses completely and give clear deductive arguments to prove our claims. We hope you find it interesting and illuminating. 2 With high probability the density histogram resembles the graph of the probability density function: We stated that one consequence of the law of large numbers is that as the number of samples increases the density histogram of the samples has an increasing probability of matching the graph of the underlying pdf or pmf. This is a good rule of thumb, but it is rather imprecise. It is possible to make more precise statements. It will take some care to make a sensible and precise statement, which will not be quite so sweeping. Suppose we have an experiment that produces data according to the random variable 𝑋 and suppose we generate 𝑛 independent samples from 𝑋. Call them 𝑥1 , 𝑥 2 , … , 𝑥 𝑛 . By a bin we mean a range of values, i.e. (𝑏1 , 𝑏2 ]. The data point 𝑥𝑘 is in this bin if 𝑏1 < 𝑥𝑘 ≤ 𝑏2 . (For the left-most bin, we would use an interval closed on both sides.) To make a density histogram of the data we divide the range of 𝑋 into 𝑚 bins and calculate the fraction of the data in each bin. Now, let 𝑝𝑘 be the probability a random data point is in the 𝑘th bin. This is this probability for an indicator (Bernoulli) random variable 𝐵𝑘,𝑗 which is 1 if the 𝑗th data point is in the bin and and 0 otherwise. Statement 1. Let 𝑝𝑘̄ be the fraction of the data in bin 𝑘. As the number 𝑛 of data points gets large the probability that 𝑝𝑘̄ is close to 𝑝𝑘 approaches 1. Said differently, given any small number, call it 𝑎 the probability 𝑃 (|𝑝𝑘̄ − 𝑝𝑘 | < 𝑎) depends on 𝑛, and as 𝑛 goes to infinity this probability goes to 1. Proof. Let 𝐵̄ 𝑘 be the average of 𝐵𝑘,𝑗 . Since 𝐸[𝐵𝑘,𝑗 ] = 𝑝𝑘 , the law of large number says exactly that 𝑃 (|𝐵̄ 𝑘 − 𝑝𝑘 | < 𝑎) approaches 1 as 𝑛 goes to infinity. But, since the 𝐵𝑘,𝑗 are indicator variables, their average is exactly 𝑝𝑘̄ , the fraction of the data in bin 𝑘. Replacing 𝐵̄ 𝑘 by 𝑝𝑘̄ in the above equation gives 𝑃 (|𝑝𝑘̄ − 𝑝𝑘 | < 𝑎) approaches 1 as 𝑛 goes to infinity. This is exactly what Statement 1 claimed. 1 18.05 Class 6, Appendix, Spring 2022 2 Statement 2. The same statement holds for a finite number of bins simultaneously. That is, for bins 1 to 𝑚 we have 𝑃 ( (|𝐵̄ 1 −𝑝1 | < 𝑎), (|𝐵̄ 2 −𝑝2 | < 𝑎), … , (|𝐵̄ 𝑚 −𝑝𝑚 | < 𝑎) ) approaches 1 as 𝑛 goes to infinity. Proof. First we note the following probability rule, which is a consequence of the inclusion exclusion principle: If two events 𝐴 and 𝐵 have 𝑃 (𝐴) = 1 − 𝛼1 and 𝑃 (𝐵) = 1 − 𝛼2 then 𝑃 (𝐴 ∩ 𝐵) ≥ 1 − (𝛼1 + 𝛼2 ). Now, Statement 1 says that for any 𝛼 we can find 𝑛 large enough that 𝑃 (|𝐵̄ 𝑘 − 𝑝𝑘 | < 𝑎) > 1 − 𝛼/𝑚 for each bin separately. By the probability rule, the probability of the intersection of all these events is at least 1 − 𝛼. Since we can let 𝛼 be as small as we want by letting 𝑛 go to infinity, in the limit we get probability 1 as claimed. Statement 3. If 𝑓(𝑥) is a continuous probability density with range [𝑎, 𝑏] then by taking enough data and having a small enough bin width we can insure that with high probability the density histogram is as close as we want to the graph of 𝑓(𝑥). Proof. We will only sketch the argument. Assume the bin around 𝑥 has width is Δ𝑥. If Δ𝑥 is small enough then the probability a data point is in the bin is approximately 𝑓(𝑥)Δ𝑥. Statement 2 guarantees that if 𝑛 is large enough then with high probability the fraction of data in the bin is also approximately 𝑓(𝑥)Δ𝑥. Since this is the area of the bin we see that its height will be approximately 𝑓(𝑥). That is, with high probability the height of the histogram over any point 𝑥 is close to 𝑓(𝑥). This is what Statement 3 claimed. Note. If the range is infinite or the density goes to infinity at some point we need to be more careful. There are statements we could make for these cases. 3 The Chebyshev inequality One proof of the LoLN follows from the following key inequality. The Chebyshev inequality. Suppose 𝑌 is a random variable with mean 𝜇 and variance 𝜎2 . Then for any positive value 𝑎, we have 𝑃 (|𝑌 − 𝜇| ≥ 𝑎) ≤ Var(𝑌 ) . 𝑎2 In words, the Chebyshev inequality says that the probability that 𝑌 differs from the mean by more than 𝑎 is bounded by Var(𝑌 )/𝑎2 . Morally, the smaller the variance of 𝑌 , the smaller the probability that 𝑌 is far from its mean. Proof of the LoLN: Since Var(𝑋̄ 𝑛 ) = Var(𝑋)/𝑛, the variance of the average 𝑋̄ 𝑛 goes to zero as 𝑛 goes to infinity. So the Chebyshev inequality for 𝑌 = 𝑋̄ 𝑛 and fixed 𝑎 implies that as 𝑛 grows, the probability that 𝑋̄ 𝑛 is farther than 𝑎 from 𝜇 goes to 0. Hence the probability that 𝑋̄ 𝑛 is within 𝑎 of 𝜇 goes to 1, which is the LoLN. Proof of the Chebyshev inequality: The proof is essentially the same for discrete and continuous 𝑌 . We’ll assume 𝑌 is continuous and also that 𝜇 = 0, since replacing 𝑌 by 𝑌 − 𝜇 18.05 Class 6, Appendix, Spring 2022 3 does not change the variance. So −𝑎 𝑃 (|𝑌 | ≥ 𝑎) = ∫ −∞ ∞ ≤ ∫ −∞ ∞ 𝑓(𝑦) 𝑑𝑦 + ∫ −𝑎 𝑓(𝑦) 𝑑𝑦 ≤ ∫ 𝑎 −∞ 𝑦2 𝑓(𝑦) 𝑑𝑦 + ∫ 𝑎2 𝑎 ∞ 𝑦2 𝑓(𝑦) 𝑑𝑦 𝑎2 𝑦2 Var(𝑌 ) 𝑓(𝑦) 𝑑𝑦 = . 2 𝑎 𝑎2 The first inequality uses that 𝑦2 /𝑎2 ≥ 1 on the intervals of integration. The second inequality follows because including the range [−𝑎, 𝑎] only makes the integral larger, since the integrand is positive. 4 The need for variance We didn’t lie to you, but we did gloss over one technical fact. Throughout we assumed that the underlying distributions had a variance. For example, the proof of the law of large numbers made use of the variance by way of the Chebyshev inequality. But there are distributions which do not have a mean and variance because the sums or integrals for these do not converge to a finite number. For such distributions the law of large numbers may not be true. In 18.05 we won’t have to worry about this, but if you go deeper into statistics this may become important. For those who are interested: a standard example you can look up or play with in R is the Cauchy distribution.