Part VII · Chance & data Chapter 48 of 60
Random variables
A laboratory of chance: we throw dice and needles, drop balls onto pegs, count kicks from horses. Each law is first observed in an experiment and then proved, and we see why the average of many random numbers is hardly random at all.
Builds on: 47 · Probability
You will learn
- describe a random variable by its distribution and compute its expectation and variance
- use linearity of expectation even when the variables are dependent
- recognise the binomial, Poisson, geometric and normal distributions
- explain why the average of many observations converges and why sums add up to a bell curve
The last chapter ended with two observations that don’t sit well together. The walker on a line is certain to get home, yet the average waiting time never settles down, however many walks you average over. And the average score of a die over ten thousand rolls almost certainly lies between $3.4$ and $3.6$. To understand which averages are predictable and why, we need to talk not about events but about random numbers.
This chapter is a lab notebook. In each experiment we first watch what happens: we throw dice and needles, drop balls onto pegs, count kicks from horses. Then we write down the law and prove it. The experiments can be repeated as often as you like: the widgets never get tired.
Experiment one: a number that comes up
Roll two dice and write down the total. The outcome of the experiment is a pair of numbers, but we’re interested in one number computed from that pair. A total of $2$ comes up in one way out of $36$, a total of $7$ in six, a total of $12$ again in one. This list of “value – probability” describes the total completely.
A random variable is a number determined by the outcome of an experiment, that is, a function $X \colon \Omega \to \mathbb R$. For a discrete variable (with a finite or countable set of values $x_1, x_2, \ldots$) its distribution is the list of values with probabilities $p_i = P(X = x_i)$; all $p_i \ge 0$, and they add up to $1$.
| Total $S$ | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| $36 \cdot P(S = s)$ | 1 | 2 | 3 | 4 | 5 | 6 | 5 | 4 | 3 | 2 | 1 |
Experiment two: a fair price
A casino offers a game: you roll a die and get as many pounds as the points that come up. What’s a fair entry fee? Play $6000$ times in your head. Each face comes up about $1000$ times, and we get about $(1 + 2 + \ldots + 6) \cdot 1000 = 21{,}000$ pounds, that is, $3.5$ pounds a game on average. That’s the fair price.
The expectation (expected value) of a discrete random variable is the sum of its values weighted by their probabilities. Notation: $\mathbb E X$, also $E X$ or $\mathbb E[X]$ (some textbooks write $MX$). If there are infinitely many values, the expectation exists when the series converges absolutely.
The main property of expectation looks modest and works like magic: the expectation of a sum equals the sum of the expectations, even if the terms depend on each other.
If the random variables $X$ and $Y$ have expectations, then for any numbers $a$ and $b$
$$\mathbb E(aX + bY) = a\,\mathbb E X + b\,\mathbb E Y.$$The trick is to compute the expectation not over values but over outcomes of the experiment: then a sum of variables becomes columns stacked on top of each other. We prove it for a finite $\Omega$; for a countable one everything is the same with absolutely convergent series.
Now the hats problem from the chapter on combinatorics is solved in two lines. How many guests get their own hat on average? Let $I_k = 1$ if the $k$th guest got their own hat, and $I_k = 0$ otherwise. Such a variable is called the indicator of an event; its expectation equals the probability of the event: $\mathbb E I_k = 1 \cdot \frac1n + 0 \cdot \frac{n - 1}{n} = \frac1n$. The number of matches $I_1 + \ldots + I_n$ is $n \cdot \frac1n = 1$ on average, whatever the number of guests. The indicators are strongly dependent (if all but one got their own, so did the last), but that doesn’t hinder linearity.
Pairs with a shared birthday behave the same way. $23$ people form $\binom{23}{2} = 253$ pairs, each matches with probability $\frac1{365}$, and on average there are $\frac{253}{365} \approx 0.69$ matching pairs. That’s the answer promised at the end of the last chapter: half the rooms have no matches, others have one, two or more, and on average it comes to $0.69$.
On the ground floor of a ten-storey building $5$ people get into the lift. Each gets out at one of the nine floors above, chosen at random, independently of the others. How many stops will the lift make on average? Give the answer to two decimal places.
Let $I_k = 1$ if the lift stopped at the $k$th of these floors. It won’t stop there if all five chose other floors: probability $\left(\frac89\right)^5$. So $\mathbb E I_k = 1 - \left(\frac89\right)^5$, and by linearity the average number of stops is $9\left(1 - \frac{32{,}768}{59{,}049}\right) = \frac{26{,}281}{6561} \approx 4.01$.
Experiment three: spread
Two games with the same fair price of $3.5$: in the first you’re always paid $3.5$ pounds, in the second a coin is tossed and you’re paid $0$ or $7$. The expectation is the same, but the games are different: in the second you’re taking a risk. We need a measure of how far the values scatter from the mean.
The variance is the expectation of the squared deviation from the mean: $\operatorname{Var} X = \mathbb E(X - \mathbb E X)^2$ (some books write $\mathbb D X$). Its square root, the standard deviation $\sigma = \sqrt{\operatorname{Var} X}$, measures spread in the same units as the variable itself.
Variance is more easily computed with another formula, and it follows from an identity that has an honest picture.
For any variable $X$ with finite variance and any number $c$: $\mathbb E(X - c)^2 = \operatorname{Var} X + (\mathbb E X - c)^2$. In particular, $\operatorname{Var} X = \mathbb E X^2 - (\mathbb E X)^2$ (at $c = 0$), and the mean squared deviation from a point $c$ is smallest at $c = \mathbb E X$.
The trick is to split the deviation from $c$ into two pieces: from $c$ to the mean and from the mean to the value. The square splits into four parts, and two of them vanish on average. Write $\mu = \mathbb E X$.
For any numbers $a$ and $b$: $\operatorname{Var}(aX + b) = a^2\operatorname{Var} X$.
By linearity $\mathbb E(aX + b) = a\,\mathbb E X + b$, so the deviation from the mean is $aX + b - (a\,\mathbb E X + b) = a(X - \mathbb E X)$. Its square is $a^2(X - \mathbb E X)^2$, and by linearity again $\operatorname{Var}(aX + b) = a^2\,\mathbb E(X - \mathbb E X)^2 = a^2\operatorname{Var} X$.
A shift doesn’t change the spread; stretching by a factor $a$ multiplies it by $a^2$. Addition is harder: variances add only when the terms are unrelated.
Random variables $X$ and $Y$ are independent if $P(X = x,\ Y = y) = P(X = x) \cdot P(Y = y)$ for all values $x$ and $y$: every event about $X$ is independent of every event about $Y$.
If $X$ and $Y$ are independent and have finite variances, then $\mathbb E(XY) = \mathbb E X \cdot \mathbb E Y$ and $\operatorname{Var}(X + Y) = \operatorname{Var} X + \operatorname{Var} Y$.
The first equation is a computation: $\mathbb E(XY) = \sum_{x, y} xy\,P(X = x, Y = y) = \sum_{x, y} x\,P(X = x) \cdot y\,P(Y = y)$, and the double sum of products splits into the product of sums $\sum_x x\,P(X = x) \cdot \sum_y y\,P(Y = y)$. For the second, write $X_0 = X - \mathbb E X$ and $Y_0 = Y - \mathbb E Y$; they’re independent too (they’re just shifts) and have zero expectations. Then $\operatorname{Var}(X + Y) = \mathbb E(X_0 + Y_0)^2 = \mathbb E X_0^2 + 2\,\mathbb E(X_0 Y_0) + \mathbb E Y_0^2$ by linearity, and by the first equation the middle term equals $2\,\mathbb E X_0 \cdot \mathbb E Y_0 = 0$.
Without independence the second equation breaks down: if $Y = X$, then $\operatorname{Var}(X + Y) = \operatorname{Var}(2X) = 4\operatorname{Var} X$, not $2\operatorname{Var} X$. The total of two dice has variance $\frac{35}{12} \cdot 2 = \frac{35}{6}$: expectation $7$, spread about $2.4$.
Experiment four: the Galton board
In the 1870s the English scientist Francis Galton built a board: balls pour from the top onto rows of pegs and at each peg bounce left or right. At the bottom they collect in bins. Each individual ball behaves unpredictably, but the pile in the bins grows the same every time, shaped like a bell.
A series of $n$ independent trials, in each of which “success” occurs with the same probability $p$, is called a sequence of Bernoulli trials. The number of successes in it has the binomial distribution. A ball on a Galton board with $n$ rows goes through Bernoulli trials: “success” is a bounce to the right, and the bin number is the number of successes.
In $n$ Bernoulli trials with probability of success $p$, the number of successes $X$ equals $k$ with probability $P(X = k) = \dbinom{n}{k} p^k (1 - p)^{n - k}$, $k = 0, 1, \ldots, n$.
The trick is to follow not the bin but the ball’s path: the paths into one bin are equally likely, and they’re easy to count.
If $X$ is the number of successes in Bernoulli trials, then $\mathbb E X = np$ and $\operatorname{Var} X = np(1 - p)$.
Direct computation from Bernoulli’s formula is cumbersome; indicators make it mental arithmetic. Let $I_j$ be the indicator of success in the $j$th trial. Then $X = I_1 + \ldots + I_n$, $\mathbb E I_j = p$ and, since $I_j^2 = I_j$, $\operatorname{Var} I_j = \mathbb E I_j^2 - (\mathbb E I_j)^2 = p - p^2 = p(1 - p)$. By linearity $\mathbb E X = np$. The indicators are independent, so by the theorem on sums of independent variables (applied $n - 1$ times) $\operatorname{Var} X = np(1 - p)$.
On a board with $12$ rows and $p = \frac12$ the balls land in bin $6$ on average, and the standard deviation is $\sqrt{12 \cdot \frac14} = \sqrt3 \approx 1.73$ bins. It’s no accident that the bell looks like Gauss’s curve; the central limit theorem will explain why.
Experiment five: kicks from horses
In 1898 the economist and statistician Ladislaus Bortkiewicz published a book, The Law of Small Numbers. Its most famous example is the deaths of soldiers in the Prussian cavalry from being kicked by a horse. The event is rare and happens in each corps at most a few times a year. The best-known sample from his data covers ten corps over twenty years, 1875 to 1894: $200$ “corps-years” in all and $122$ deaths, an average of $0.61$ a year per corps.
| Deaths in a corps in a year | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| Corps-years observed | 109 | 65 | 22 | 3 | 1 |
| Predicted by Poisson’s law | 108.7 | 66.3 | 20.2 | 4.1 | 0.6 |
The agreement is almost perfect. Each of the hundreds of cavalrymen in a corps dies from a kick in a given year with a tiny probability, independently of the others. The number of deaths is a binomial variable with a huge $n$ and a small $p$, and in the limit we get the distribution that Siméon Denis Poisson derived in 1837 in a book on the probability of court verdicts.
A variable $X$ with non-negative integer values has the Poisson distribution with parameter $\lambda > 0$ if $P(X = k) = \dfrac{\lambda^k e^{-\lambda}}{k!}$ for $k = 0, 1, 2, \ldots$ These probabilities add up to $e^{-\lambda} e^{\lambda} = 1$ by the series for the exponential.
In Bernoulli trials let $p = \frac{\lambda}{n}$. Then for each fixed $k$, as $n \to \infty$, the probability $\binom{n}{k} p^k (1 - p)^{n - k}$ tends to $\dfrac{\lambda^k e^{-\lambda}}{k!}$.
Split the binomial probability into factors, each of which has an easy limit:
$$\binom{n}{k}\frac{\lambda^k}{n^k}\left(1 - \frac{\lambda}{n}\right)^{n - k} = \frac{\lambda^k}{k!} \cdot \frac{n(n - 1)\cdots(n - k + 1)}{n^k} \cdot \left(1 - \frac{\lambda}{n}\right)^{n} \cdot \left(1 - \frac{\lambda}{n}\right)^{-k}.$$The second factor equals $\left(1 - \frac1n\right)\left(1 - \frac2n\right)\cdots\left(1 - \frac{k - 1}{n}\right)$: that’s $k - 1$ brackets (the number $k$ is fixed), each tends to $1$, and so does the product. The third tends to $e^{-\lambda}$ by the theorem on continuous compounding from the chapter on the exponential: $\left(1 + \frac xn\right)^n \to e^x$ with $x = -\lambda$. The fourth is a fixed power of a number tending to $1$, and itself tends to $1$. The limit of the product is the product of the limits: $\frac{\lambda^k}{k!} e^{-\lambda}$.
If $X$ has the Poisson distribution with parameter $\lambda$, then $\mathbb E X = \operatorname{Var} X = \lambda$.
In the series for the expectation the term with $k = 0$ is zero, and in the others $k$ cancels with $k!$: $\mathbb E X = \sum_{k \ge 1} k\,\frac{\lambda^k e^{-\lambda}}{k!} = \lambda \sum_{k \ge 1}\frac{\lambda^{k - 1} e^{-\lambda}}{(k - 1)!} = \lambda$, because the last sum is the sum of all the probabilities of the distribution. In the same way, cancelling $k(k - 1)$ with $k!$, we get $\mathbb E\,X(X - 1) = \lambda^2$. Hence $\mathbb E X^2 = \lambda^2 + \lambda$, and by Steiner’s identity $\operatorname{Var} X = \mathbb E X^2 - (\mathbb E X)^2 = \lambda$.
Experiment six: how long to wait
Roll a die until the first six. How many rolls will it take? Sometimes one try, sometimes twenty. The number $T$ of the roll with the first six equals $k$ if the first $k - 1$ rolls fail and the $k$th succeeds.
A variable $T$ with distribution $P(T = k) = (1 - p)^{k - 1} p$, $k = 1, 2, \ldots$, the number of the first success in Bernoulli trials, has the geometric distribution: the probabilities decrease in a geometric progression.
The expectation is conveniently computed through the “tails”, the probabilities of having to wait longer than $k$ steps. For the geometric distribution the tail is very simple: $P(T > k) = (1 - p)^k$, since that means the first $k$ rolls failed.
If $T$ takes the values $1, 2, 3, \ldots$, then $\mathbb E T = \sum_{k \ge 0} P(T > k)$ (both sides are finite or infinite together).
The trick is to cut the same figure in two ways: into columns and into strips.
If $T$ has the geometric distribution with probability of success $p$, then $\mathbb E T = \dfrac1p$ and $P(T > m + n \mid T > m) = P(T > n)$ for any integers $m, n \ge 0$.
By the lemma $\mathbb E T = \sum_{k \ge 0} P(T > k) = \sum_{k \ge 0} (1 - p)^k = \frac{1}{1 - (1 - p)} = \frac1p$ by the formula for the sum of a geometric progression. For the second equation: the event $T > m + n$ is contained in $T > m$, so by the definition of conditional probability $P(T > m + n \mid T > m) = \frac{(1 - p)^{m + n}}{(1 - p)^m} = (1 - p)^n = P(T > n)$.
We wait $6$ rolls on average for a six, and $36$ for a double six with two dice. The geometric distribution has no memory: if there’s been no six for twenty rolls, the remaining wait is still six on average. It’s the gambler’s fallacy from the last chapter written as a formula, and the radioactive atom that doesn’t age from the chapter on the exponential.
Experiment seven: the walker’s debt
The last chapter proved that the walker on a line gets home, and left a debt: the plane and space. There are too many paths there to count by reflections. The average number of returns comes to the rescue. Write $u_n = P(S_{2n} = 0)$ for the probability of being home exactly at step $2n$ (you can’t be home at odd steps).
The walker returns home with probability $1$ if and only if the series $\sum_{n \ge 1} u_n$ diverges.
Let $N$ be the number of returns over the whole infinite walk, and $q$ the probability of at least one return. The number $N$ is the sum of the indicators of the events $\{S_{2n} = 0\}$ over all $n \ge 1$. For non-negative terms linearity extends to infinite sums too (this is proved rigorously in the chapter on measure), so $\mathbb E N = \sum_{n \ge 1} u_n$.
Now compute $\mathbb E N$ another way. Having got home, the walker carries on by the same rules, and their future steps don’t depend on the past ones: from that moment everything starts afresh. So given $N \ge k$, the event $N \ge k + 1$ (returning once more) has the same probability $q$, and by induction $P(N \ge k) = q^k$. If $q < 1$, then by the tails lemma $\mathbb E N = \sum_{k \ge 1} q^k = \frac{q}{1 - q} < \infty$. If $q = 1$, then $P(N \ge k) = 1$ for all $k$, and $\mathbb E N = \infty$. So the series $\sum u_n$ diverges exactly when $q = 1$.
It remains to estimate $u_n$. On a line $u_n = a_n = \frac{1}{2^{2n}}\binom{2n}{n} = \frac{1 \cdot 3 \cdots (2n - 1)}{2 \cdot 4 \cdots 2n}$, and the last chapter bounded this number from above: $a_n < \frac{1}{\sqrt{2n + 1}}$. Now we need a bound from below.
$a_n \ge \dfrac{1}{2\sqrt n}$ for all $n \ge 1$.
The same device as for the upper bound: bound the square, replacing each fraction by a product of two neighbours. For $k \ge 2$ we have $\left(\frac{2k - 1}{2k}\right)^2 \ge \frac{2k - 2}{2k - 1} \cdot \frac{2k - 1}{2k}$: after cancelling $\frac{2k - 1}{2k}$ this is $(2k - 1)^2 \ge 2k(2k - 2)$, that is, $4k^2 - 4k + 1 \ge 4k^2 - 4k$. Multiply these inequalities for $k = 2, \ldots, n$ and add the factor $\left(\frac12\right)^2$ from $k = 1$. The left side becomes $a_n^2$, the right side $\frac14 \cdot \frac24 \cdot \frac46 \cdots \frac{2n - 2}{2n} = \frac14 \cdot \frac{2}{2n} = \frac{1}{4n}$: each numerator cancels with the denominator of the previous fraction. So $a_n^2 \ge \frac{1}{4n}$.
A walker who at each step picks one of the neighbouring directions with equal chances returns home with probability $1$ on a line and in the plane. In three-dimensional space the probability of return is less than $1$.
The trick is to rotate the plane through $45°$: then the walk along the streets splits into two independent walks on a line. In space we’ll argue for a walker who steps along the diagonals of the cubes, and say something about six directions at the end.
Let’s settle the last chapter’s second debt while we’re at it.
Let $T$ be the number of the step at which the walker on a line first gets home. Then $\mathbb E T = \infty$.
The event $T > 2n$ means the walker hasn’t returned in $2n$ steps; the last chapter found its probability, which is $a_n$ (one at $n = 0$). You can’t return at an odd step, so $P(T > 2n + 1) = P(T > 2n)$. By the tails lemma $\mathbb E T = \sum_{k \ge 0} P(T > k) = 2\sum_{n \ge 0} a_n$, and this series diverges, since $a_n \ge \frac{1}{2\sqrt n}$. The walker is certain to return, but on average you’ll wait for ever, like the St Petersburg prize.
Experiment eight: the bell
On a Galton board with many rows the bins merge, and the histogram turns into a smooth curve. For variables that can take any value on a line (height, the wait for a bus, a measurement error), the probability of any single value is zero, and the distribution is described differently.
A variable $X$ has probability density $f$ if $f \ge 0$ and $P(a \le X \le b) = \int_a^b f(x)\,dx$ for all $a \le b$: a probability is an area under the graph of the density. Its expectation $\mathbb E X = \int x f(x)\,dx$ is the centre of gravity of that area, and its variance is $\operatorname{Var} X = \int (x - \mathbb E X)^2 f(x)\,dx$.
A variable with this density has the normal distribution $N(\mu, \sigma^2)$; when $\mu = 0$, $\sigma = 1$ it’s called standard, and its density is written $\varphi(z) = \frac{1}{\sqrt{2\pi}}e^{-z^2/2}$.
If $X$ has the distribution $N(\mu, \sigma^2)$, then $\mathbb E X = \mu$ and $\operatorname{Var} X = \sigma^2$.
The substitution $x = \mu + \sigma z$ reduces the integrals for $X$ to integrals for the standard variable $Z$: $X = \mu + \sigma Z$, so it’s enough to prove $\mathbb E Z = 0$ and $\operatorname{Var} Z = 1$ (then $\mathbb E X = \mu$ and $\operatorname{Var} X = \sigma^2\operatorname{Var} Z$). The density $\varphi$ is even, while $z\varphi(z)$ is odd and decays fast, so $\int z\varphi(z)\,dz = 0$. Next, $\varphi'(z) = -z\varphi(z)$, and integration by parts gives $\int z^2\varphi(z)\,dz = \int z \cdot \bigl(-\varphi'(z)\bigr)\,dz = \bigl[-z\varphi(z)\bigr]_{-\infty}^{+\infty} + \int \varphi(z)\,dz = 0 + 1$.
The normal law was discovered by Abraham de Moivre in 1733 as an approximation to the binomial one at $p = \frac12$; Laplace extended it to any $p$ in 1812. Gauss in 1809 derived the same curve as the law of errors of astronomical measurements, and in the end it was named after him.
Experiment nine: the running mean
Toss a coin and after each toss write down the share of heads. At first it darts about, then it settles near $\frac12$. The average score of a die settles near $3.5$ in the same way. But there are variables whose average never settles down.
Why does the mean converge? The first step is a simple inequality: a non-negative variable is rarely much bigger than its mean.
If $X \ge 0$ and $a > 0$, then $P(X \ge a) \le \dfrac{\mathbb E X}{a}$.
The trick is the staircase from the tails lemma: the area under the graph of $P(X > t)$ equals $\mathbb E X$.
If $X$ has finite variance, then for any $\varepsilon > 0$: $P\bigl(|X - \mathbb E X| \ge \varepsilon\bigr) \le \dfrac{\operatorname{Var} X}{\varepsilon^2}$.
Apply Markov’s inequality to the non-negative variable $(X - \mathbb E X)^2$ with threshold $a = \varepsilon^2$. The events $|X - \mathbb E X| \ge \varepsilon$ and $(X - \mathbb E X)^2 \ge \varepsilon^2$ coincide, and the expectation of the squared deviation is the variance: $P \le \frac{\operatorname{Var} X}{\varepsilon^2}$.
Let $X_1, X_2, \ldots$ be independent and identically distributed, $\mathbb E X_i = \mu$, $\operatorname{Var} X_i = \sigma^2 < \infty$, and $\bar X_n = \frac{X_1 + \ldots + X_n}{n}$. Then for any $\varepsilon > 0$ the probability $P\bigl(|\bar X_n - \mu| \ge \varepsilon\bigr)$ is at most $\frac{\sigma^2}{n\varepsilon^2}$ and tends to zero as $n \to \infty$.
By linearity $\mathbb E \bar X_n = \frac{n\mu}{n} = \mu$. The terms are independent, so the variance of the sum is $n\sigma^2$, and dividing by $n$ divides the variance by $n^2$: $\operatorname{Var} \bar X_n = \frac{\sigma^2}{n}$. Chebyshev’s inequality for $\bar X_n$ gives $P\bigl(|\bar X_n - \mu| \ge \varepsilon\bigr) \le \frac{\sigma^2}{n\varepsilon^2}$, and this tends to zero.
The condition “the variance is finite” can be weakened to “the expectation exists” (Khinchin, 1929), but it can’t be dropped altogether. The “lighthouse” in the widget has the density $\frac{1}{\pi(1 + x^2)}$, which decays so slowly that $\int |x|\,f(x)\,dx = \infty$: there’s no expectation, and the mean of $n$ observations has exactly the same distribution as a single observation. However much you average, nothing gets more precise.
Experiment ten: sums of dice
The law of large numbers says where the mean converges to, and that the deviations are of order $\frac{\sigma}{\sqrt n}$. But what shape is the cloud of deviations? Experiment gives a surprising answer: always the same one.
Let $X_1, X_2, \ldots$ be independent and identically distributed, $\mathbb E X_i = \mu$, $0 < \operatorname{Var} X_i = \sigma^2 < \infty$, and $S_n = X_1 + \ldots + X_n$. Then for every $x$
$$P\left(\frac{S_n - n\mu}{\sigma\sqrt n} \le x\right) \xrightarrow[n \to \infty]{} \frac{1}{\sqrt{2\pi}}\int_{-\infty}^{x} e^{-z^2/2}\,dz.$$The idea of the proof, and why the full one doesn’t fit in the course
There won’t be a full proof in this course: it needs machinery we don’t have. The idea is this. The distribution of a variable $Y$ can be encoded by the function $\varphi_Y(t) = \mathbb E\,e^{itY}$, the Fourier transform of the distribution. For a sum of independent variables these functions multiply, as expectations of products did. Let $Y_i = \frac{X_i - \mu}{\sigma}$: $\mathbb E Y_i = 0$, $\mathbb E Y_i^2 = 1$, and by Taylor’s formula $\varphi_Y(s) = 1 - \frac{s^2}{2} + o(s^2)$. For the normalised sum $Z_n = \frac{Y_1 + \ldots + Y_n}{\sqrt n}$ we get $\varphi_{Z_n}(t) = \left(1 - \frac{t^2}{2n} + o\!\left(\frac1n\right)\right)^n \to e^{-t^2/2}$, and that’s the function of the standard normal distribution. The missing brick is Lévy’s continuity theorem: convergence of such functions implies convergence of the distributions themselves. It’s proved in a probability course in the second or third year.
An example. The total of $100$ rolls of a die is $350$ on average, with standard deviation $\sqrt{100 \cdot \frac{35}{12}} \approx 17.08$. By the theorem the probability of scoring at least $380$ is roughly $1 - \Phi\!\left(\frac{379.5 - 350}{17.08}\right) \approx 0.042$, where $\Phi$ is the area under the standard bell to the left of a point. An exact count from the distribution of the total, as in the widget, gives $0.0420$. The half-unit in the numerator accounts for the total being a whole number: its column at $380$ stretches from $379.5$.
Experiment eleven: Buffon’s needle
A floor is ruled with parallel lines a distance $d$ apart. A needle of length $l \le d$ is dropped on it. What’s the probability that the needle crosses a line? The problem was posed by the naturalist Georges-Louis Leclerc, Comte de Buffon, in 1733, and he published the solution in 1777. The answer contains the number $\pi$, though there are no circles in the problem.
If a needle of length $l \le d$ falls at a random place at a random angle, it crosses a line with probability $\dfrac{2l}{\pi d}$.
The trick, found by Joseph-Émile Barbier in 1860: instead of the probability, compute the average number of crossings, and bend the needle into a circle. Linearity of expectation does the rest.
In 1901 the Italian mathematician Mario Lazzarini reported that he had dropped a needle $3408$ times with $l = \frac56 d$ and counted $1808$ crossings. That gives $\pi \approx \frac{2 \cdot 5 \cdot 3408}{6 \cdot 1808} = \frac{355}{113} = 3.141\,592\,9\ldots$: six correct decimal places. Too good. The honest error for $3408$ throws is about $0.05$. Later it was noticed that $3408 = 16 \cdot 213$: the number of throws was chosen so that the estimate could come out as $\frac{355}{113}$ at all, and if you throw in batches and stop at a lucky moment, such a “result” comes without any miracle. The lesson will come in handy in the next chapter.
Monte Carlo
Buffon’s needle is the first example of the Monte Carlo method: find a number by setting up an experiment in which that number is a probability or an expectation, and repeating the experiment many times. The method was devised by Stanisław Ulam in 1946. By his own recollection, while recovering from an illness he was playing patience and wondered how often it comes out; working it out was hopeless, but playing many times and counting the share was easy. Together with John von Neumann he applied the idea to computing the motion of neutrons at Los Alamos, and the name, after the casino, was suggested by their colleague Nicholas Metropolis.
The central limit theorem tells you what this costs: the error decreases like $\frac{1}{\sqrt n}$. For Buffon’s estimate with $l = d$ the standard deviation is about $\frac{2.37}{\sqrt n}$, and to be within $0.001$ with probability $95\,\%$ you need more than twenty million throws. For the number $\pi$ that’s dreadfully slow, but the method has a trump card: the rate $\frac{1}{\sqrt n}$ doesn’t depend on the dimension of the problem. The volume of a body in a hundred-dimensional space can’t be computed with a grid, but it can with random points. That’s why Monte Carlo is used today to price options, to trace light in computer graphics and in particle physics.
Where next
In every experiment of this chapter we knew the distribution in advance: the die is fair, the coin symmetric, the needle falls any which way. In life it’s the other way round. A poll of a thousand people found $52\,\%$ in favour: what does that mean for the whole country? A drug helped $60$ patients out of $100$, and a placebo $45$: is that a difference or chance? The sample mean is close to the mean of the whole, but how close and with what confidence, and how do you avoid fooling yourself like Lazzarini? Judging the whole from a sample is what the next chapter teaches.