Ch.5: Gaussian approximations

Chapter 5 of the book "Probability for the Enthusiastic Beginner" by David Morin (2016) Binomial and Gaussian The law of large numbers Poisson and Gaussian Binomial, Poisson, and Gaussian The central limit theorem Problems

72 flashcards · Mathematics · by lakesare

Part of Textbooks › Probability for the Enthusiastic Beginner (David Morin) · 7 courses

1. [Gaussian approximations] Which four results describe what happens to the binomial and Poisson distributions, and to repeated trials, when the numbers involved are large?

   Binomial to Gaussian A binomial distribution with a large number of trials is approximately a Gaussian distribution. Example: the number of Heads in 20 coin flips is already very close to Gaussian. Law of large numbers In a very large number of trials, the observed fraction of times an event occurs is very close to the theoretical probability. Example: in 100,000 coin flips, the fraction of Heads lies between 49% and 51% with probability 99.999999975%. Poisson to Gaussian A Poisson distribution…

2. [Binomial and Gaussian] Is the binomial distribution of the number of Heads in nnn coin flips a Gaussian distribution?

   Not exactly, but for large nnn it is approximately Gaussian, and the larger nnn , the closer it is. For 2 flips the binomial points lie far from the Gaussian curve, for 6 flips reasonably close, for 20 flips very close. Dots: exact binomial probabilities. Curves: Gaussian approximation. xxx = number of Heads minus the expected number.

3. [Binomial and Gaussian] Which two approximations does the derivation of the Gaussian approximation to the binomial distribution use?

   Stirling's formula For large nnn : n!≈nne−n2πnn! \approx n^n e^{-n} \sqrt{2\pi n}n!≈nne−n2πn​ . Example: 1010e−1020π≈3,598,70010^{10} e^{-10} \sqrt{20\pi} \approx 3{,}598{,}7001010e−1020π​≈3,598,700 , while 10!=3,628,80010! = 3{,}628{,}80010!=3,628,800 . Exponential approximation For small aaa : (1+a)m≈emae−ma2/2(1 + a)^m \approx e^{ma} e^{-ma^2/2}(1+a)m≈emae−ma2/2 . Example: a=0.1a = 0.1a=0.1 , m=30m = 30m=30 : 1.130≈17.451.1^{30} \approx 17.451.130≈17.45 , and e3e−0.15≈17.29e^{3} e^{-0.15} \a…

4. [Binomial and Gaussian] 2n2n2n coins are flipped, and xxx is the number of Heads minus the expected number nnn . What is the exact probability PB(x)P_B(x)PB​(x) ?

   PB(x)=122n(2nn+x)\boldsymbol{P_B(x) = \frac{1}{2^{2n}} \binom{2n}{n + x}}PB​(x)=22n1​(n+x2n​) Using 2n2n2n flips avoids factors of 1/21/21/2 , and writing the number of Heads as n+xn + xn+x makes the calculation much simpler than working with the number kkk of Heads.Example: 2n=42n = 42n=4 flips, x=1x = 1x=1 (3 Heads): 116(43)=416=14\frac{1}{16} \binom{4}{3} = \frac{4}{16} = \frac{1}{4}161​(34​)=164​=41​ .

5. [Binomial and Gaussian] 2n2n2n coins are flipped, nnn is large, and xxx is the number of Heads minus nnn . Which Gaussian PG(x)P_G(x)PG​(x) approximates the probability PB(x)P_B(x)PB​(x) of n+xn + xn+x Heads?

   PB(x)≈e−x2/nπn≡PG(x)\boldsymbol{P_B(x) \approx \dfrac{e^{-x^2/n}}{\sqrt{\pi n}} \equiv P_G(x)}PB​(x)≈πn​e−x2/n​≡PG​(x) Example: 100 flips ( n=50n = 50n=50 ), 55 Heads ( x=5x = 5x=5 ): e−1/250π≈0.0484\frac{e^{-1/2}}{\sqrt{50\pi}} \approx 0.048450π​e−1/2​≈0.0484 , and the exact value is (10055)/2100≈0.0485\binom{100}{55}/2^{100} \approx 0.0485(55100​)/2100≈0.0485 .

6. [Binomial and Gaussian] Goal: show 122n(2nn+x)≈e−x2/nπn\frac{1}{2^{2n}}\binom{2n}{n+x} \approx \frac{e^{-x^2/n}}{\sqrt{\pi n}}22n1​(n+x2n​)≈πn​e−x2/n​ for large nnn (the probability of n+xn + xn+x Heads in 2n2n2n coin flips).What is the first step, and what does it give?

   Apply Stirling's formula m!≈mme−m2πmm! \approx m^m e^{-m}\sqrt{2\pi m}m!≈mme−m2πm​ to (2n)!(2n)!(2n)! , (n+x)!(n+x)!(n+x)! and (n−x)!(n-x)!(n−x)! ; all the eee 's cancel: (2nn+x)≈(2n)2nn(n+x)n+x(n−x)n−xπn2−x2\displaystyle\binom{2n}{n+x} \approx \frac{(2n)^{2n} \sqrt{n}}{(n+x)^{n+x} (n-x)^{n-x} \sqrt{\pi} \sqrt{n^2 - x^2}}(n+x2n​)≈(n+x)n+x(n−x)n−xπ​n2−x2​(2n)2nn​​ The exponentials give e−2n/(e−(n+x)e−(n−x))=1e^{-2n} / (e^{-(n+x)} e^{-(n-x)}) = 1e−2n/(e−(n+x)e−(n−x))=1 .

7. [Binomial and Gaussian] Deriving the Gaussian approximation to the binomial: Stirling's formula gave (2nn+x)≈(2n)2nn(n+x)n+x(n−x)n−xπn2−x2\displaystyle\binom{2n}{n+x} \approx \frac{(2n)^{2n} \sqrt{n}}{(n+x)^{n+x} (n-x)^{n-x} \sqrt{\pi} \sqrt{n^2 - x^2}}(n+x2n​)≈(n+x)n+x(n−x)n−xπ​n2−x2​(2n)2nn​​ .What is the next step, and what does it give?

   Divide numerator and denominator by n2nn^{2n}n2n (the two denominator factors by nn+xn^{n+x}nn+x and nn−xn^{n-x}nn−x ): (2nn+x)≈22nn(1+xn)n+x(1−xn)n−xπn2−x2\displaystyle\binom{2n}{n+x} \approx \frac{2^{2n} \sqrt{n}}{\left(1 + \frac{x}{n}\right)^{n+x} \left(1 - \frac{x}{n}\right)^{n-x} \sqrt{\pi} \sqrt{n^2 - x^2}}(n+x2n​)≈(1+nx​)n+x(1−nx​)n−xπ​n2−x2​22nn​​

8. [Binomial and Gaussian] Deriving the Gaussian approximation to the binomial (with x≪nx \ll nx≪n ), the factors (1+xn)n+x\left(1 + \frac{x}{n}\right)^{n+x}(1+nx​)n+x and (1−xn)n−x\left(1 - \frac{x}{n}\right)^{n-x}(1−nx​)n−x appear.How are they approximated?

   With (1+a)m≈emae−ma2/2(1 + a)^m \approx e^{ma} e^{-ma^2/2}(1+a)m≈emae−ma2/2 , a=±xna = \pm\frac{x}{n}a=±nx​ : (1+xn)n+x≈ex+x2/2n\left(1 + \frac{x}{n}\right)^{n+x} \approx e^{x + x^2/2n}(1+nx​)n+x≈ex+x2/2n and (1−xn)n−x≈e−x+x2/2n\left(1 - \frac{x}{n}\right)^{n-x} \approx e^{-x + x^2/2n}(1−nx​)n−x≈e−x+x2/2n (n+x)xn−12(n+x)x2n2=x+x2n−x22n−x32n2(n + x)\frac{x}{n} - \frac{1}{2}(n + x)\frac{x^2}{n^2} = x + \frac{x^2}{n} - \frac{x^2}{2n} - \frac{x^3}{2n^2}(n+x)nx​−21​(n+x)n2x2​=x+nx2​−2nx2​−2n2x3​ , a…

9. [Binomial and Gaussian] Deriving the Gaussian approximation to the binomial: (2nn+x)≈22nnex+x2/2n e−x+x2/2nπn2−x2\displaystyle\binom{2n}{n+x} \approx \frac{2^{2n} \sqrt{n}}{e^{x + x^2/2n} \, e^{-x + x^2/2n} \sqrt{\pi} \sqrt{n^2 - x^2}}(n+x2n​)≈ex+x2/2ne−x+x2/2nπ​n2−x2​22nn​​ , with x≪nx \ll nx≪n .How does the derivation finish?

   The xxx and −x-x−x in the exponents cancel and n2−x2≈n\sqrt{n^2 - x^2} \approx nn2−x2​≈n , so (2nn+x)≈22nex2/nπn\binom{2n}{n+x} \approx \frac{2^{2n}}{e^{x^2/n}\sqrt{\pi n}}(n+x2n​)≈ex2/nπn​22n​ ; dividing by 22n2^{2n}22n gives e−x2/nπn\frac{e^{-x^2/n}}{\sqrt{\pi n}}πn​e−x2/n​ . Example: n=10,000n = 10{,}000n=10,000 , x=100x = 100x=100 : n2−x2≈9999.5\sqrt{n^2 - x^2} \approx 9999.5n2−x2​≈9999.5 , very close to nnn .

10. [Binomial and Gaussian] Deriving the Gaussian approximation to the binomial, (1+xn)n+x\left(1 + \frac{x}{n}\right)^{n+x}(1+nx​)n+x is approximated by ex+x2/2ne^{x + x^2/2n}ex+x2/2n .Why keep the x22n\frac{x^2}{2n}2nx2​ term, although it is much smaller than xxx (for x≪nx \ll nx≪n )?

    Because the xxx terms cancel against the −x-x−x from (1−xn)n−x≈e−x+x2/2n\left(1 - \frac{x}{n}\right)^{n-x} \approx e^{-x + x^2/2n}(1−nx​)n−x≈e−x+x2/2n , so the x22n\frac{x^2}{2n}2nx2​ terms are what remains. The −x32n2-\frac{x^3}{2n^2}−2n2x3​ terms would cancel too, for the same reason; they are dropped because they are much smaller than x22n\frac{x^2}{2n}2nx2​ .

11. [Binomial and Gaussian] Deriving the Gaussian approximation to the binomial uses (1+a)m≈emae−ma2/2(1 + a)^m \approx e^{ma} e^{-ma^2/2}(1+a)m≈emae−ma2/2 .Why is the less accurate (1+a)m≈ema(1 + a)^m \approx e^{ma}(1+a)m≈ema not good enough?

    It gives wrong x2n\frac{x^2}{n}nx2​ terms instead of the correct x22n\frac{x^2}{2n}2nx2​ terms, so the result would be the wrong function e−2x2/nπn\frac{e^{-2x^2/n}}{\sqrt{\pi n}}πn​e−2x2/n​ . With emae^{ma}ema alone: (n+x)xn=x+x2n(n + x)\frac{x}{n} = x + \frac{x^2}{n}(n+x)nx​=x+nx2​ . The wrong function has total area 12\frac{1}{\sqrt 2}2​1​ instead of 1.

12. [Binomial and Gaussian] nnn coins are flipped ( nnn large), and xxx is the number of Heads minus n/2n/2n/2 . What Gaussian approximates the probability of n/2+xn/2 + xn/2+x Heads?

    PG(x)=e−2x2/nπn/2\boldsymbol{P_G(x) = \dfrac{e^{-2x^2/n}}{\sqrt{\pi n/2}}}PG​(x)=πn/2​e−2x2/n​ Replace nnn by n/2n/2n/2 in e−x2/nπn\frac{e^{-x^2/n}}{\sqrt{\pi n}}πn​e−x2/n​ (the version for 2n2n2n flips). In both versions, the coefficient of π\piπ and the inverse of the coefficient of x2x^2x2 equal half the number of flips.Example: 20 flips: PG(x)=e−x2/1010πP_G(x) = \frac{e^{-x^2/10}}{\sqrt{10\pi}}PG​(x)=10π​e−x2/10​ , with maximum 110π≈0.18\frac{1}{\sqrt{10\pi}} \approx 0.1810π​1​≈0.18 .

13. [Binomial and Gaussian] For 2n2n2n coin flips, PG(x)=e−x2/nπnP_G(x) = \frac{e^{-x^2/n}}{\sqrt{\pi n}}PG​(x)=πn​e−x2/n​ approximates the probability of n+xn + xn+x Heads. The derivation assumed x≪nx \ll nx≪n .Why is that assumption harmless?

    The values of xxx that are not much smaller than nnn have negligible probability, so it does not matter that the formula may fail for them. Example: x=10nx = 10\sqrt{n}x=10n​ (still ≪n\ll n≪n for large nnn ) gives the factor e−100≈4⋅10−44e^{-100} \approx 4 \cdot 10^{-44}e−100≈4⋅10−44 ; even x=2nx = 2\sqrt{n}x=2n​ gives e−4≈0.02e^{-4} \approx 0.02e−4≈0.02 . Larger xxx give even smaller probabilities, since (2nn+x)\binom{2n}{n+x}(n+x2n​) decreases as xxx moves away from 0.

14. [Binomial and Gaussian] Why is the Gaussian approximation PG(x)=e−x2/nπnP_G(x) = \frac{e^{-x^2/n}}{\sqrt{\pi n}}PG​(x)=πn​e−x2/n​ to the coin-flip distribution symmetric around x=0x = 0x=0 ?

    xxx appears only through x2x^2x2 , so xxx and −x-x−x give the same value. This matches intuition: getting four Heads above the average is as likely as getting four Heads below it.

15. [Binomial and Gaussian] What does the Gaussian approximation PG(x)=e−x2/nπnP_G(x) = \frac{e^{-x^2/n}}{\sqrt{\pi n}}PG​(x)=πn​e−x2/n​ give at x=0x = 0x=0 (for 2n2n2n coin flips)?

    1πn\boldsymbol{\frac{1}{\sqrt{\pi n}}}πn​1​ , the probability that exactly half of the 2n2n2n flips are Heads. This agrees with the result obtained earlier from Stirling's formula.Example: 100 flips: 150π≈0.08\frac{1}{\sqrt{50\pi}} \approx 0.0850π​1​≈0.08 , so exactly 50 Heads has probability about 8%.

16. [Binomial and Gaussian] A Gaussian with mean μ\muμ and standard deviation σ\sigmaσ is 12πσ2e−(x−μ)2/2σ2\frac{1}{\sqrt{2\pi\sigma^2}} e^{-(x-\mu)^2/2\sigma^2}2πσ2​1​e−(x−μ)2/2σ2 .What is the standard deviation of the coin-flip approximation PG(x)=e−2x2/nπn/2P_G(x) = \frac{e^{-2x^2/n}}{\sqrt{\pi n/2}}PG​(x)=πn/2​e−2x2/n​ ( nnn flips)?

    σ=n/4\boldsymbol{\sigma = \sqrt{n/4}}σ=n/4​ , the same as the exact binomial standard deviation. 2σ2=n/22\sigma^2 = n/22σ2=n/2 makes both the prefactor and the coefficient of x2x^2x2 agree.Example: 100 flips: σ=5\sigma = 5σ=5 .

17. [Binomial and Gaussian] Suppose you know only that the binomial coin-flip distribution ( nnn flips) is close to some Gaussian. Why must that Gaussian be e−2x2/nπn/2\frac{e^{-2x^2/n}}{\sqrt{\pi n/2}}πn/2​e−2x2/n​ ?

    Its standard deviation must equal the binomial standard deviation n/4\sqrt{n/4}n/4​ , and σ\sigmaσ determines both the prefactor and the coefficient of x2x^2x2 . So the derivation is needed only to show that the binomial reduces to a Gaussian at all; that was not obvious beforehand.

18. [Binomial and Gaussian] Why is the total area under the coin-flip approximation e−2x2/nπn/2\frac{e^{-2x^2/n}}{\sqrt{\pi n/2}}πn/2​e−2x2/n​ equal to 1?

    It is a Gaussian of the standard form, and every such Gaussian has area 1. Also expected: it approximates the binomial distribution, whose total probability is 1.

19. [Binomial and Gaussian] nnn trials each succeed with probability ppp , nnn is large, and xxx is the number of successes minus pnpnpn . Which Gaussian approximates the probability of pn+xpn + xpn+x successes?

    PG(x)≈e−x2/[2np(1−p)]2πnp(1−p)\boldsymbol{P_G(x) \approx \dfrac{e^{-x^2/[2np(1-p)]}}{\sqrt{2\pi np(1-p)}}}PG​(x)≈2πnp(1−p)​e−x2/[2np(1−p)]​ , a Gaussian with σ=np(1−p)=npq\sigma = \sqrt{np(1-p)} = \sqrt{npq}σ=np(1−p)​=npq​ . σ\sigmaσ agrees with the exact binomial standard deviation. For p=12p = \frac{1}{2}p=21​ the formula reduces to the coin-flip version e−2x2/nπn/2\frac{e^{-2x^2/n}}{\sqrt{\pi n/2}}πn/2​e−2x2/n​ .Example: number of 5's in 60 dice rolls: p=16p = \frac{1}{6}p=61​ , centered at…

20. [Binomial and Gaussian] A binomial distribution has p≠12p \neq \frac{1}{2}p=21​ , so its peak is not at n/2n/2n/2 . For large nnn , is the shape of the distribution lopsided?

    No, it is essentially symmetric around pnpnpn , because the Gaussian approximation is symmetric. The tail extends farther on one side, but there the probabilities are essentially zero. Number of 5's in 60 dice rolls; xxx = deviation from the expected number 10.

21. [The law of large numbers] What does the law of large numbers say?

    If you repeat a random process a very large number of times, the observed fraction of times an event occurs will be very close to the theoretical probability. Example: in 100,000 coin flips the fraction of Heads is between 49% and 51% with probability 99.999999975%.

22. [The law of large numbers] How is the law of large numbers stated precisely, using the probability pdp_dpd​ and a small number δ\deltaδ ?

    pdp_dpd​ is the probability that the observed fraction differs from the theoretical probability by more than δ\deltaδ ; pd→0p_d \to 0pd​→0 as the number of trials becomes large. "d" stands for "differ". Example: δ=0.01\delta = 0.01δ=0.01 and 100,000 coin flips: pd≈2.5⋅10−10p_d \approx 2.5 \cdot 10^{-10}pd​≈2.5⋅10−10 .

23. [The law of large numbers] pdp_dpd​ = probability that the observed fraction in n1n_1n1​ trials differs from the theoretical probability by more than δ\deltaδ .How would you measure pdp_dpd​ experimentally?

    Perform a large number n2n_2n2​ of sets of n1n_1n1​ trials; pdp_dpd​ is about the fraction of sets whose observed fraction is off by more than δ\deltaδ . The larger n2n_2n2​ , the closer this is to the true pdp_dpd​ .Example: n1=10,000n_1 = 10{,}000n1​=10,000 coin flips, δ=1%\delta = 1\%δ=1% : the fraction of sets with under 49% or over 51% Heads is about 5% (the true pdp_dpd​ ).

24. [The law of large numbers] Why is "a very large number of times" essential in the law of large numbers?

    For few trials the observed fraction is often far from the probability. Example: in 10 coin flips, exactly 5 Heads has probability only (105)/210=252/1024≈25%\binom{10}{5}/2^{10} = 252/1024 \approx 25\%(510​)/210=252/1024≈25% .

25. [The law of large numbers] The law of large numbers looks the same as the definition of probability as a long-run fraction. Is it a theorem or a definition?

    It can be stated as: the observed fraction approaches a definite value. That value is then defined to be the probability. So the law of large numbers is what allows probability to be well defined. This only partly removes the circularity.

26. [The law of large numbers] For 2n2n2n coin flips, PG(x)=e−x2/nπnP_G(x) = \frac{e^{-x^2/n}}{\sqrt{\pi n}}PG​(x)=πn​e−x2/n​ approximates the probability of n+xn + xn+x Heads.As nnn grows, how do the height and the width of PGP_GPG​ change?

    Height ∝1/n\propto 1/\sqrt{n}∝1/n​ , width ∝n\propto \sqrt{n}∝n​ (the standard deviation is σ=n/2\sigma = \sqrt{n/2}σ=n/2​ ). The two factors are reciprocals, so the area stays 1.Example: 200 flips ( n=100n = 100n=100 ): σ≈7.1\sigma \approx 7.1σ≈7.1 ; 2000 flips: σ≈22.4\sigma \approx 22.4σ≈22.4 .

27. [The law of large numbers] The width of the coin-flip distribution grows like n\sqrt{n}n​ . Why does this make the percentage of Heads converge?

    n\sqrt{n}n​ grows more slowly than nnn : relative to the number of flips, the width decreases by a factor 1/n1/\sqrt{n}1/n​ . Plotted from −n-n−n to nnn and scaled to height 1, each tenfold increase of nnn makes the curve thinner by 1/101/\sqrt{10}1/10​ :

28. [The law of large numbers] Although the width of the coin-flip distribution grows in an additive (or absolute) sense, it decreases in a multiplicative sense, relative to the number of flips.

    Percentages depend on the multiplicative sense. Example: σ=n/2\sigma = \sqrt{n/2}σ=n/2​ for 2n2n2n flips: 2n=1002n = 1002n=100 gives σ=5\sigma = 5σ=5 (5% of the flips), 2n=100,0002n = 100{,}0002n=100,000 gives σ≈158\sigma \approx 158σ≈158 (0.16%).

29. [The law of large numbers] In 100 coin flips, why is the probability of 49, 50 or 51 Heads about 24%?

    Each of the three counts has probability about 8%, and 3⋅8%=24%3 \cdot 8\% = 24\%3⋅8%=24% . P(50)=150π≈8%P(50) = \frac{1}{\sqrt{50\pi}} \approx 8\%P(50)=50π​1​≈8% , and 49 and 51 are almost as likely. As a histogram this is the area from 48.5 to 51.5 (the bin of 49 runs from 48.5 to 49.5). Left: 100 flips; most of the area lies outside 49% to 51%. Right: 100,000 flips; essentially all area lies inside.

30. [The law of large numbers] Why is the probability of 49% to 51% Heads in 100,000 coin flips as large as 99.999999975%?

    51% is 1000 Heads above the mean, about 6σ6\sigma6σ , since σ=n/2=25,000≈158\sigma = \sqrt{n/2} = \sqrt{25{,}000} \approx 158σ=n/2​=25,000​≈158 ( 2n=100,0002n = 100{,}0002n=100,000 ). A result more than 6σ6\sigma6σ from the mean has virtually no chance. For 100 flips, σ=5\sigma = 5σ=5 , and 49% to 51% is only x=±1x = \pm 1x=±1 .

31. [The law of large numbers] Why is the law of large numbers for coin flips the same observation as the decrease of the standard deviation of the mean?

    The percentage of Heads is the average number of Heads per flip, whose standard deviation decreases like 1/n1/\sqrt{n}1/n​ . Example: average of nnn flips (Heads = 1): σ=12n\sigma = \frac{1}{2\sqrt{n}}σ=2n​1​ , so 0.05 for 100 flips and 0.0016 for 100,000.

32. [The law of large numbers] Which everyday facts follow from the law of large numbers?

    Polls are more accurate when more people are interviewed; casinos nearly always come out ahead. Also: all the air molecules in a room ending up on one side is prohibitively unlikely, and a piece of paper does not spontaneously combust.

33. [Poisson and Gaussian] For the Gaussian approximation to the Poisson distribution, why take the limit of large aaa (expected number of successes), not of a large number of trials?

    The Poisson distribution has no number of trials: its only parameter is aaa . In the binomial case a large number nnn of trials means a large expected number pnpnpn , so large aaa corresponds to large nnn .

34. [Poisson and Gaussian] The Poisson distribution is PP(k)=ake−ak!P_P(k) = \frac{a^k e^{-a}}{k!}PP​(k)=k!ake−a​ . For large aaa , which Gaussian approximates it?

    PP(k)≈e−(k−a)2/2a2πa\boldsymbol{P_P(k) \approx \dfrac{e^{-(k-a)^2/2a}}{\sqrt{2\pi a}}}PP​(k)≈2πa​e−(k−a)2/2a​ , a Gaussian with μ=a\mu = aμ=a and σ=a\sigma = \sqrt{a}σ=a​ . With x=k−ax = k - ax=k−a : PP(x)≈e−x2/2a2πaP_P(x) \approx \frac{e^{-x^2/2a}}{\sqrt{2\pi a}}PP​(x)≈2πa​e−x2/2a​ .Example: a=100a = 100a=100 , k=110k = 110k=110 : e−1/2200π≈0.0242\frac{e^{-1/2}}{\sqrt{200\pi}} \approx 0.0242200π​e−1/2​≈0.0242 ; the exact Poisson value is 0.02340.02340.0234 .

35. [Poisson and Gaussian] In deriving the Gaussian approximation to the Poisson distribution PP(k)=ake−ak!P_P(k) = \frac{a^k e^{-a}}{k!}PP​(k)=k!ake−a​ , why write k=a+xk = a + xk=a+x ?

    PP(k)P_P(k)PP​(k) has its maximum at k=ak = ak=a , so the approximation looks at PPP_PPP​ near aaa . Technically the maximum is between a−1a - 1a−1 and aaa , which makes no difference for large aaa . The same idea as writing n+xn + xn+x Heads in 2n2n2n coin flips.

36. [Poisson and Gaussian] Goal: show ake−ak!≈e−x2/2a2πa\frac{a^k e^{-a}}{k!} \approx \frac{e^{-x^2/2a}}{\sqrt{2\pi a}}k!ake−a​≈2πa​e−x2/2a​ for large aaa , with k=a+xk = a + xk=a+x and x≪ax \ll ax≪a .What does Stirling's formula, followed by simplification, give?

    PP(x)≈1(1+xa)a+xe−x2πa\boldsymbol{P_P(x) \approx \dfrac{1}{\left(1 + \frac{x}{a}\right)^{a+x} e^{-x} \sqrt{2\pi a}}}PP​(x)≈(1+ax​)a+xe−x2πa​1​ Stirling gives aa+xe−a(a+x)a+xe−a−x2π(a+x)\frac{a^{a+x} e^{-a}}{(a+x)^{a+x} e^{-a-x} \sqrt{2\pi(a+x)}}(a+x)a+xe−a−x2π(a+x)​aa+xe−a​ . Then cancel e−ae^{-a}e−a , divide numerator and denominator by aa+xa^{a+x}aa+x , and drop the xxx in the square root because x≪ax \ll ax≪a .

37. [Poisson and Gaussian] Deriving the Gaussian approximation to the Poisson distribution: PP(x)≈1(1+xa)a+xe−x2πaP_P(x) \approx \frac{1}{\left(1 + \frac{x}{a}\right)^{a+x} e^{-x} \sqrt{2\pi a}}PP​(x)≈(1+ax​)a+xe−x2πa​1​ with x≪ax \ll ax≪a .How does the derivation finish?

    (1+a′)m≈ema′e−ma′2/2(1 + a')^m \approx e^{ma'} e^{-ma'^2/2}(1+a′)m≈ema′e−ma′2/2 with a′=xaa' = \frac{x}{a}a′=ax​ , m=a+xm = a + xm=a+x gives (1+xa)a+x≈ex+x2/2a\left(1 + \frac{x}{a}\right)^{a+x} \approx e^{x + x^2/2a}(1+ax​)a+x≈ex+x2/2a ; the exe^xex cancels e−xe^{-x}e−x , leaving e−x2/2a2πa\frac{e^{-x^2/2a}}{\sqrt{2\pi a}}2πa​e−x2/2a​ . The small −x32a2-\frac{x^3}{2a^2}−2a2x3​ term is dropped. This is the same computation as in the coin-flip case, with nnn replaced by aaa .

38. [Poisson and Gaussian] How well does the Gaussian e−(k−a)2/2a2πa\frac{e^{-(k-a)^2/2a}}{\sqrt{2\pi a}}2πa​e−(k−a)2/2a​ approximate the Poisson distribution for a=5a = 5a=5 , 202020 , 100100100 ?

    Roughly for a=5a = 5a=5 , quite well for a=20a = 20a=20 , extremely well for a=100a = 100a=100 . Dots: exact Poisson. Curves: Gaussian approximation.

39. [Poisson and Gaussian] The Poisson distribution depends only on aaa . Why must its Gaussian approximation have exactly σ=a\sigma = \sqrt{a}σ=a​ ?

    The Gaussian's σ\sigmaσ must equal the Poisson standard deviation, which is known to be a\sqrt{a}a​ . That σ\sigmaσ is a function of aaa alone is clear from the one parameter; that it equals a\sqrt{a}a​ takes a calculation.

40. [Poisson and Gaussian] As aaa grows, how does the width of the Poisson distribution compare with the distance aaa from 0 to its peak?

    The width a\sqrt{a}a​ grows more slowly than aaa , so relative to aaa the peak becomes thinner. Example: a=100a = 100a=100 : σ=10\sigma = 10σ=10 , 10% of aaa . a=1000a = 1000a=1000 : σ≈31.6\sigma \approx 31.6σ≈31.6 , about 3.2% of aaa .

41. [Poisson and Gaussian] The Gaussian approximation to the Poisson distribution assumed x≪ax \ll ax≪a (with k=a+xk = a + xk=a+x ). Why is that harmless?

    For large aaa , values of xxx not much smaller than aaa have negligible probability. aaa appears in e−x2/2a2πa\frac{e^{-x^2/2a}}{\sqrt{2\pi a}}2πa​e−x2/2a​ in the same way as nnn in the coin-flip formula. Example: x=10ax = 10\sqrt{a}x=10a​ gives the factor e−50≈2⋅10−22e^{-50} \approx 2 \cdot 10^{-22}e−50≈2⋅10−22 .

42. [Binomial, Poisson, and Gaussian] Which limits connect the binomial, Poisson and Gaussian distributions?

    Binomial to Poisson Continuum limit: n→∞n \to \inftyn→∞ and p→0p \to 0p→0 with pnpnpn fixed. Example: p=0.001p = 0.001p=0.001 , n=3000n = 3000n=3000 is close to Poisson with a=3a = 3a=3 . Binomial to Gaussian Large- nnn limit; precisely, both pnpnpn and (1−p)n(1 - p)n(1−p)n large. Example: 20 coin flips are already close to Gaussian. Poisson to Gaussian Large- aaa limit, aaa the expected number of events. Example: a=100a = 100a=100 .

43. [Binomial, Poisson, and Gaussian] The Poisson distribution is obtained from the binomial distribution by taking the continuum limit.

    n0n_0n0​ trials per time ttt with success probability p0p_0p0​ are replaced by 10n010n_010n0​ trials with probability p0/10p_0/10p0​/10 , then 100n0100n_0100n0​ with p0/100p_0/100p0​/100 , and so on. The average a=p0n0a = p_0n_0a=p0​n0​ successes per time ttt stays the same, and the distribution of successes per time ttt approaches the Poisson distribution with parameter aaa .

44. [Binomial, Poisson, and Gaussian] For a binomial distribution with general ppp , what is the condition for it to be approximately Gaussian?

    Both pnpnpn and (1−p)n(1 - p)n(1−p)n are large: the expected numbers of successes and of failures. If neither ppp nor 1−p1 - p1−p is very small, this reduces to nnn being large.Example: p=10−3p = 10^{-3}p=10−3 , n=103n = 10^3n=103 gives pn=1pn = 1pn=1 , not large; nnn must be about 10510^5105 or 10610^6106 .

45. [Binomial, Poisson, and Gaussian] For a binomial distribution with probability ppp and nnn trials: does large pnpnpn imply large nnn , and does large nnn imply large pnpnpn ?

    Large pnpnpn implies large nnn (since p≤1p \le 1p≤1 ); large nnn does not imply large pnpnpn . Example: p=10−3p = 10^{-3}p=10−3 , n=103n = 10^3n=103 : nnn is large but pn=1pn = 1pn=1 .

46. [Binomial, Poisson, and Gaussian] Why is the large- aaa condition (Poisson to Gaussian) consistent with the large- pnpnpn condition (binomial to Gaussian)?

    aaa and pnpnpn are both the expected number of successes.

47. [The central limit theorem] What does the central limit theorem say (in its most common form)?

    If you perform a large number of trials of a random process, the probability distribution of the sum (or average) of the outcomes is approximately Gaussian. The greater the number of trials, the better the approximation. It holds under a reasonable set of assumptions, for any underlying distribution.Example: the sum of 100 dice rolls is approximately Gaussian, centered at 350.

48. [The central limit theorem] The Gaussian distribution is also called the normal distribution.

49. [The central limit theorem] Which two paths lead from the binomial distribution to the Gaussian distribution?

    Directly, by large pnpnpn and (1−p)n(1 - p)n(1−p)n ; or to the Poisson distribution by the continuum limit, then to the Gaussian by large aaa . That every path ends at the Gaussian, and none leads away from it, is consistent with the central limit theorem.

50. [The central limit theorem] The central limit theorem needs trials with numerical outcomes. How do coin flips fit it?

    Assign Heads the value 1 and Tails 0; the sum of the outcomes is the number of Heads. So the binomial distribution being approximately Gaussian for large nnn is the central limit theorem for this Bernoulli process.

51. [The central limit theorem] How does the distribution of the sum of ntn_tnt​ dice rolls change for nt=1,2,3,10n_t = 1, 2, 3, 10nt​=1,2,3,10 ?

    It approaches a Gaussian as ntn_tnt​ grows, although one roll has a flat distribution. 1 die: six equal values. 2 dice: a triangle peaked at 7. 3 dice: a curved shape peaked at 10.5. 10 dice: essentially Gaussian, centered at 35. Histograms of 10610^6106 sets of ntn_tnt​ rolls each.

52. [The central limit theorem] How large must the number of trials be for the central limit theorem to give an essentially Gaussian distribution?

    Usually 10 or 20 trials are plenty. What counts as large depends on the process. Example: the sum of 10 dice is Gaussian for all practical purposes.

53. [The central limit theorem] Why does the central limit theorem hold for the average of the outcomes, not only for their sum?

    The average is the sum divided by the fixed number ntn_tnt​ of trials, so its histogram has the same shape, with the xxx values divided by ntn_tnt​ . Example: the average of 10 dice rolls is approximately Gaussian, centered at 3.5.

54. [The central limit theorem] When measuring the distribution of a sum experimentally, what are the numbers ntn_tnt​ and nsn_sns​ ?

    ntn_tnt​ The number of trials whose sum (or average) is one data point. For large ntn_tnt​ that sum is approximately Gaussian; usually nt≈20n_t \approx 20nt​≈20 is enough. Example: 10 dice rolls, or 50 coin flips. nsn_sns​ The number of sets of ntn_tnt​ trials, each giving one data point. For small nsn_sns​ the measured histogram is choppy. Example: ns=106n_s = 10^6ns​=106 sets for each histogram of dice sums.

55. [The central limit theorem] ntn_tnt​ = number of trials summed into one data point; nsn_sns​ = number of such sets of trials, i.e. the number of data points.Which of ntn_tnt​ and nsn_sns​ does the true probability distribution of the sum depend on?

    Only on ntn_tnt​ (and on what each trial is); not on nsn_sns​ . nsn_sns​ is just how many sets you consider when trying to determine the distribution experimentally; the true distribution exists regardless.

56. [The central limit theorem] nsn_sns​ sets of 10 dice rolls are made, and the sums are plotted as histograms for ns=100n_s = 100ns​=100 , 1000, 10,000, 100,000. What do you see?

    For ns=100n_s = 100ns​=100 the histogram is choppy and hardly Gaussian; it becomes smooth and Gaussian as nsn_sns​ grows. So ntn_tnt​ need only be "at least medium-ish" (10 here), while nsn_sns​ must be large.

57. [The central limit theorem] ntn_tnt​ = number of trials summed into one data point; nsn_sns​ = number of data points.Histograms become more Gaussian as ntn_tnt​ grows, and also as nsn_sns​ grows. Which progression illustrates the central limit theorem?

    The progression in ntn_tnt​ . The progression in nsn_sns​ only shows that many data points are needed for a histogram close to the true distribution. In the dice example, the true distribution for nt=10n_t = 10nt​=10 happens to be Gaussian because of the central limit theorem and the reasonably large ntn_tnt​ .

58. [The central limit theorem] A number takes the values 2, 3.2, 7 with probabilities 0.6, 0.1, 0.3. What is the distribution of the average of 100 such numbers?

    Approximately Gaussian, centered at the expectation value 3.623.623.62 . 0.6⋅2+0.1⋅3.2+0.3⋅7=3.620.6 \cdot 2 + 0.1 \cdot 3.2 + 0.3 \cdot 7 = 3.620.6⋅2+0.1⋅3.2+0.3⋅7=3.62 . The central limit theorem holds for any underlying distribution, even an irregular one. 10510^5105 averages of 100 numbers each. Its standard deviation: 5.02/100≈0.22\sqrt{5.02}/\sqrt{100} \approx 0.225.02​/100​≈0.22 .

59. [The central limit theorem] What is the distribution of the average of 50 numbers drawn from the uniform distribution on [0,1][0, 1][0,1] ?

    Approximately Gaussian, centered at 0.5. The central limit theorem holds for continuous distributions too.Example: its standard deviation is 1/1250≈0.041\frac{1/\sqrt{12}}{\sqrt{50}} \approx 0.04150​1/12​​≈0.041 .

60. [Problems] Without computing either value, why is the probability of getting between 49% and 51% Heads in 10510^5105 fair coin flips equal to the probability of getting between 49.99% and 50.01% Heads in 10910^9109 flips?

    Both ranges reach the same number of standard deviations, about 6.3σ6.3\sigma6.3σ , on each side of the mean. The number of Heads in nnn flips has σ=n/4\sigma = \sqrt{n/4}σ=n/4​ : 105/4=158\sqrt{10^5/4} = 158105/4​=158 and 109/4=15,800\sqrt{10^9/4} = 15{,}800109/4​=15,800 . The half-widths are 105/102=10310^5/10^2 = 10^3105/102=103 and 109/104=10510^9/10^4 = 10^5109/104=105 Heads, and 103/158=105/15,800=6.310^3/158 = 10^5/15{,}800 = 6.3103/158=105/15,800=6.3 .Both cases are Gaussian, and a Gaus…

61. [Problems] 6n6n6n dice are rolled. Why does the probability of getting at least nnn 6's approach 1/21/21/2 as n→∞n \to \inftyn→∞ ?

    The number of 6's is approximately Gaussian with mean nnn , and a Gaussian is symmetric about its mean. Exactly: P(at least n)=12+12P(exactly n)P(\text{at least } n) = \frac{1}{2} + \frac{1}{2} P(\text{exactly } n)P(at least n)=21​+21​P(exactly n) , and P(exactly n)P(\text{exactly } n)P(exactly n) becomes small for large nnn . So the probability is slightly above 1/21/21/2 .For small nnn it is noticeably above 1/21/21/2 : P(exactly n)P(\text{exactly } n)P(exactly n) is not small, and the Gaussi…

62. [Problems] You flip 10410^4104 fair coins. How surprised should you be if the percentage of Heads differs from 50% by more than 1%?

    Only mildly: the probability is about 5%. σ=n/4=104/4=50\sigma = \sqrt{n/4} = \sqrt{10^4/4} = 50σ=n/4​=104/4​=50 , and 1% of 10410^4104 is 100=2σ100 = 2\sigma100=2σ . A Gaussian outcome lies within 2σ2\sigma2σ of the mean with probability about 95%.

63. [Problems] You flip 10610^6106 fair coins. What is the probability that the percentage of Heads differs from 50% by more than 1%?

    Zero for all practical purposes: below 10−8710^{-87}10−87 . σ=106/4=500\sigma = \sqrt{10^6/4} = 500σ=106/4​=500 , and 1% of 10610^6106 is 104=20σ10^4 = 20\sigma104=20σ . The exact binomial value is 5.5⋅10−895.5 \cdot 10^{-89}5.5⋅10−89 .Example: for 10510^5105 coins (between 10410^4104 and 10610^6106 ), the same probability is 2.5⋅10−102.5 \cdot 10^{-10}2.5⋅10−10 , compared with about 5% for 10410^4104 coins.

64. [Problems] f(x)=12πσ2e−x2/2σ2f(x) = \dfrac{1}{\sqrt{2\pi\sigma^2}} e^{-x^2/2\sigma^2}f(x)=2πσ2​1​e−x2/2σ2 is a Gaussian density centered at 0. How do you get a quick upper bound on the probability of an outcome more than 20σ20\sigma20σ from the mean?

    Replace fff by its value f(20σ)f(20\sigma)f(20σ) on the strip from 20σ20\sigma20σ to 21σ21\sigma21σ (and from −21σ-21\sigma−21σ to −20σ-20\sigma−20σ ), and ignore everything beyond 21σ21\sigma21σ . fff decreases beyond 20σ20\sigma20σ , so this overestimates the area there. The area is 2σf(20σ)=2/π e−200≈10−872\sigma f(20\sigma) = \sqrt{2/\pi}\, e^{-200} \approx 10^{-87}2σf(20σ)=2/π​e−200≈10−87 .Beyond 21σ21\sigma21σ the factor is e−212/2≈10−96e^{-21^2/2} \approx 10^{-96}e−212/2≈10−96 , negligib…

65. [Problems] A common wrong intuition: in nnn coin flips, a reasonable deviation of the number of Heads from n/2n/2n/2 is a fixed fraction of nnn , such as n/100n/100n/100 . What is the right scale?

    The standard deviation n/2\sqrt{n}/2n​/2 , proportional to n\sqrt{n}n​ . So a fixed fraction of nnn becomes more and more standard deviations as nnn grows.Example: n=106n = 10^6n=106 : n/100=104=20σn/100 = 10^4 = 20\sigman/100=104=20σ , a deviation with probability below 10−8710^{-87}10−87 .

66. [Problems] 1000 dice are rolled. The number of 6's, relative to its expected value 167, has this distribution: How many fair coins must be flipped so that the number of Heads, relative to its expected value, has the same distribution (in the Gaussian approximation)?

    556 coins, from nc⋅12⋅12=1000⋅16⋅56\boldsymbol{n_c \cdot \frac{1}{2} \cdot \frac{1}{2} = 1000 \cdot \frac{1}{6} \cdot \frac{5}{6}}nc​⋅21​⋅21​=1000⋅61​⋅65​ . Relative to the mean, the Gaussian approximation of a binomial distribution is P(x)=12πnp(1−p) e−x2/2np(1−p)P(x) = \dfrac{1}{\sqrt{2\pi np(1-p)}}\, e^{-x^2/2np(1-p)}P(x)=2πnp(1−p)​1​e−x2/2np(1−p) , so it is determined by np(1−p)np(1-p)np(1−p) alone (the variance).Both have np(1−p)=139np(1-p) = 139np(1−p)=139 , so σ=139≈12\sigma = \sqrt{139}…

67. [Problems] 1000 dice and 556 fair coins give the same distribution for (number of 6's) and (number of Heads) relative to the expected values, since both have np(1−p)=139np(1-p) = 139np(1−p)=139 . Why can't the expected values (167 and 278) also agree?

    Equal np(1−p)np(1-p)np(1−p) and equal npnpnp would force equal 1−p1 - p1−p , but ppp is 1/61/61/6 for the dice and 1/21/21/2 for the coins.

68. [Problems] After 20 coin flips you have only 5 Heads. The law of large numbers says the fraction of Heads approaches 50%. Should you expect more Heads than Tails in future flips?

    No: each flip is independent of all past flips. Expecting future flips to make up for past ones is the gambler's fallacy.

69. [Problems] In nnn fair coin flips, does the difference between the numbers of Heads and Tails tend to 0 as nnn grows? Then why do the fractions of Heads and Tails both approach 1/21/21/2 ?

    No: the difference is typically of the order of n\sqrt{n}n​ and grows; but n/n→0\sqrt{n}/n \to 0n​/n→0 , so the fractions approach 1/21/21/2 . The law of large numbers is about the fraction of Heads (a relative difference), not the number of Heads (an absolute difference).Example: 5 Heads below average after 20 flips stays 5 below on average, but after 10610^6106 flips σ=106/4=500\sigma = \sqrt{10^6/4} = 500σ=106/4​=500 , so those 5 Heads are negligible.

70. [Problems] 10 dice are rolled and their sum SSS is recorded; this is repeated 100,000 times. Which Gaussian function f(x)f(x)f(x) matches the histogram of the sums (one bin per value of SSS )?

    f(x)=100,000⋅12π(5.4)2 e−(x−35)2/2(5.4)2\boldsymbol{f(x) = 100{,}000 \cdot \dfrac{1}{\sqrt{2\pi (5.4)^2}}\, e^{-(x-35)^2/2(5.4)^2}}f(x)=100,000⋅2π(5.4)2​1​e−(x−35)2/2(5.4)2 μ=10⋅3.5=35\mu = 10 \cdot 3.5 = 35μ=10⋅3.5=35 . One die has variance 2.922.922.92 and σ=2.92=1.71\sigma = \sqrt{2.92} = 1.71σ=2.92​=1.71 , so the sum of 10 dice has σ=10⋅1.71=5.4\sigma = \sqrt{10} \cdot 1.71 = 5.4σ=10​⋅1.71=5.4 .The factor 100,000: the histogram counts outcomes, so the probability density is multiplied by th…

71. [Problems] A random variable takes the values 2, 3.2 and 7 with probabilities 0.6, 0.1 and 0.3. What is the standard deviation of the average of 100 independent values of it?

    σavg=2.24/100=0.224\boldsymbol{\sigma_{\text{avg}} = 2.24/\sqrt{100} = 0.224}σavg​=2.24/100​=0.224 Mean: (0.6)(2)+(0.1)(3.2)+(0.3)(7)=3.62(0.6)(2) + (0.1)(3.2) + (0.3)(7) = 3.62(0.6)(2)+(0.1)(3.2)+(0.3)(7)=3.62 . σ=(0.6)(1.62)2+(0.1)(0.42)2+(0.3)(3.38)2=2.24\ \sigma = \sqrt{(0.6)(1.62)^2 + (0.1)(0.42)^2 + (0.3)(3.38)^2} = 2.24 σ=(0.6)(1.62)2+(0.1)(0.42)2+(0.3)(3.38)2​=2.24 . The average of nnn values has σavg=σ/n\sigma_{\text{avg}} = \sigma/\sqrt{n}σavg​=σ/n​ . 100,000 such averages. At 3.62±0.…

72. [Problems] What is the standard deviation of the average of 50 independent numbers, each uniformly distributed between 0 and 1?

    σavg=0.29/50=0.041\boldsymbol{\sigma_{\text{avg}} = 0.29/\sqrt{50} = 0.041}σavg​=0.29/50​=0.041 The uniform distribution on [0,1][0, 1][0,1] has σ=1/12=0.29\sigma = 1/\sqrt{12} = 0.29σ=1/12​=0.29 , and the average of nnn values has σavg=σ/n\sigma_{\text{avg}} = \sigma/\sqrt{n}σavg​=σ/n​ . 100,000 such averages: a Gaussian centered at 0.5 (central limit theorem) with σ≈0.04\sigma \approx 0.04σ≈0.04 .