⚖️ Expectation, inequalities & limits

The toolkit behind almost every "what's the expected…" or "bound the probability that…" question: what an average really is, how spread is measured, how to bound tails when you can't compute them, how to update beliefs with evidence, and why averages always end up Gaussian.

Expectation & variance

Expectation: the balance point

The expectation $\E[X]$ is the probability-weighted average of the values $X$ can take. Physically, if you place a mass $P(X=x)$ at each point $x$ on a ruler, $\E[X]$ is where the ruler balances. It is also what the average of many independent draws settles down to (that is the law of large numbers).

$$\E[X]=\sum_x x\,P(X=x)\qquad\text{or}\qquad \E[X]=\int_{-\infty}^{\infty}x\,f(x)\,dx$$

The original notes wrote $\sum_x x\,P(X=k)$. The index must match: it is $\sum_x x\,P(X=x)$.

Expectation of a function (sometimes called LOTUS, the "law of the unconscious statistician"). To get $\E[g(X)]$ you do not need the distribution of $g(X)$. Just average $g$ over the distribution of $X$:

$$\E[g(X)]=\sum_x g(x)\,P(X=x)\qquad\text{or}\qquad \int_{-\infty}^{\infty}g(x)\,f(x)\,dx$$

Worked example. A fair die $X$: $\E[X]=\frac{1+2+\dots+6}{6}=3.5$ and $\E[X^2]=\frac{1+4+9+16+25+36}{6}=\frac{91}{6}$. Note that $\E[X^2]\neq(\E[X])^2=12.25$. The gap between them is exactly the variance (next).

The tail formula

For a non-negative random variable you can skip the density entirely and integrate the survival function $P(X>x)=1-F(x)$:

$$\E[X]=\int_0^\infty P(X>x)\,dx=\int_0^\infty \big(1-F(x)\big)\,dx \qquad\qquad \E[X]=\sum_{k=0}^{\infty}P(X>k)\ \ \text{(non-negative integers)}$$

Think of $X$ as a length. A length is the sum of all the little $dx$ slices you pass on the way from $0$ to $X$. Each slice at height $x$ is "counted" exactly when $X>x$, which happens with probability $P(X>x)$. Adding up those probabilities over all slices gives the average length.

Proof (one line with indicators)

Write $X=\int_0^\infty \1[X>x]\,dx$ (the indicator is 1 for $x\in[0,X)$, so the integral is exactly $X$). Take expectations and swap $\E$ with $\int$ (fine for non-negative integrands):

$$\E[X]=\int_0^\infty \E\big[\1[X>x]\big]\,dx=\int_0^\infty P(X>x)\,dx.$$

The discrete version is the same with $X=\sum_{k=0}^{\infty}\1[X>k]$.

$\E[X]$ is the area under the survival curve
The curve is $P(X>x)$. The shaded area under it equals the mean (dashed line). Drag the parameter and watch the area and the mean move together. Use the strip slider to highlight one slice: its height is $P(X>t)$.

Where it shines: maxima and minima. For a min, $P(\min>x)=\prod_i P(X_i>x)$ is easy, so the tail formula gives $\E[\min]$ immediately. Example: $n$ iid $\Unif(0,1)$ have $\E[\min]=\int_0^1(1-x)^n\,dx=\frac{1}{n+1}$. See max/min of n RVs. For a geometric, $\E[X]=\sum_{k\ge0}(1-p)^k=1/p$ in one line.

Variance: average squared distance from the mean

Variance measures spread: how far, on average, $X$ lands from its mean, where "far" is measured by the squared distance. The standard deviation $\sigma=\sqrt{\Var(X)}$ brings it back to the original units.

$$\Var(X)=\E\big[(X-\E[X])^2\big]=\E[X^2]-(\E[X])^2$$

The first form is the definition ("mean of squares of deviations"). The second form ("mean of square minus square of mean") is almost always easier to compute.

Proof that the two forms agree

Let $\mu=\E[X]$, a constant. Expand and use linearity:

$$\E[(X-\mu)^2]=\E[X^2]-2\mu\,\E[X]+\mu^2=\E[X^2]-2\mu^2+\mu^2=\E[X^2]-\mu^2.$$

Since the left side is an average of squares, it is $\ge0$, which proves $\E[X^2]\ge(\E[X])^2$ for free.

Variance as the average area of squares
Each dot is an equally likely value of $X$. Drag the dots left and right. The triangle is the mean (the balance point). Each colored square has side $|x_i-\mu|$, so its area is the squared deviation. The variance is the average square area, drawn as the dashed square of side $\sigma$.

Why squares and not absolute distances? Squares make the algebra beautiful: variances of independent pieces add, and $\E[X^2]-(\E X)^2$ falls out. Squares also punish big deviations heavily, which is why one outlier can blow up the variance (try dragging one dot far away).

Shifting and scaling. Adding a constant moves every value and the mean together, so the spread is unchanged. Scaling by $a$ scales every deviation by $a$ and every squared deviation by $a^2$:

Shift & scale (mean)
$\E[aX+b]=a\E[X]+b$
Shift & scale (variance)
$\Var(aX+b)=a^2\Var(X)$
Std dev
$\sigma_{aX+b}=|a|\,\sigma_X$

Linearity of expectation

$$\E[aX+bY+c]=a\,\E[X]+b\,\E[Y]+c \qquad\text{always, even if $X$ and $Y$ are dependent}$$

This is the single most useful fact in probability interviews. The trick is to write a complicated count as a sum of simple indicators and add up their expectations, completely ignoring how they depend on one another.

Classic: $n$ people throw their hats in a pile and each picks one at random. Expected number who get their own hat? Let $X_i=\1[\text{person } i \text{ gets own hat}]$. By symmetry $P(X_i=1)=1/n$, so $\E[\sum X_i]=n\cdot\frac1n=1$, for every $n$. The $X_i$ are dependent, and it doesn't matter. More in counting in expectation.

Proof (discrete case) $$\E[X+Y]=\sum_{x,y}(x+y)P(X=x,Y=y)=\sum_x x\underbrace{\sum_y P(x,y)}_{P(X=x)}+\sum_y y\underbrace{\sum_x P(x,y)}_{P(Y=y)}=\E[X]+\E[Y].$$

Only marginals appear, so no independence is needed.

Products, sums of variances & covariance

Products and variances are where dependence starts to matter. Covariance measures how $X$ and $Y$ move together:

$$\Cov(X,Y)=\E\big[(X-\E X)(Y-\E Y)\big]=\E[XY]-\E[X]\,\E[Y],\qquad \rho=\frac{\Cov(X,Y)}{\sigma_X\sigma_Y}\in[-1,1].$$
Independent ⇒
$\E[XY]=\E[X]\,\E[Y]$
Always
$\Var(X+Y)=\Var X+\Var Y+2\Cov(X,Y)$
Uncorrelated ⇒
$\Var(X+Y)=\Var X+\Var Y$
Proof of the variance-of-a-sum formula

Let $\tilde X=X-\E X$ and $\tilde Y=Y-\E Y$. Then

$$\Var(X+Y)=\E[(\tilde X+\tilde Y)^2]=\E[\tilde X^2]+\E[\tilde Y^2]+2\E[\tilde X\tilde Y]=\Var X+\Var Y+2\Cov(X,Y).$$

More generally $\Var\big(\sum_i X_i\big)=\sum_i\Var X_i+2\sum_{i<j}\Cov(X_i,X_j)$.

The original notes say $\Var(X+Y)=\Var X+\Var Y$ "if independent". That is true, but stronger than needed: it holds whenever $X$ and $Y$ are uncorrelated ($\Cov=0$). Independence implies uncorrelated, but not the other way round.

Two classic traps. (1) $\Var(X-Y)=\Var X+\Var Y$ for independent $X,Y$. The variances still add, because $(-1)^2=1$. (2) Uncorrelated does not mean independent: take $X$ uniform on $\{-1,0,1\}$ and $Y=X^2$. Then $\Cov(X,Y)=\E[X^3]-\E[X]\E[X^2]=0$, yet $Y$ is a function of $X$.

$X$ and $Y$ are independent with $\Var X=4$ and $\Var Y=1$. What is $\Var(2X-3Y+7)$?
  • $5$
  • $-1$
  • $25$
  • $32$
Constants vanish, coefficients get squared, and variances add even with a minus sign: $2^2\cdot4+3^2\cdot1=16+9=25$.

The zoo of functions: PMF, PDF, CDF

Three ways to describe a distribution. Know which one you are holding, and how to convert between them.

What it givesProperties
PMF (discrete)
$p(k)=P(X=k)$		an actual probability for each value$p(k)\ge0$, $\ \sum_k p(k)=1$
PDF (continuous)
$f(x)$		a probability density: $P(a\le X\le b)=\int_a^b f(x)\,dx$$f(x)\ge0$, $\ \int f=1$, $\ f=F'$. Can exceed 1!
CDF (both)
$F(x)=P(X\le x)$		probability of landing at or below $x$non-decreasing, from 0 to 1, right-continuous
$$F(x)=\sum_{k\le x}p(k)\quad\text{(discrete)}\qquad\qquad F(x)=\int_{-\infty}^{x}f(t)\,dt\quad\text{(continuous)}$$ $$f(x)=F'(x)\qquad\qquad P(a<X\le b)=F(b)-F(a)$$

A PDF is like mass per unit length on a rod. A single point has zero mass ($P(X=x)=0$ for continuous $X$), but a short interval of width $dx$ has mass $\approx f(x)\,dx$. The CDF is the running total of mass as you walk from left to right, so its slope is the density.

PDF ↔ CDF: area on the left equals height on the right
Move $a$ and $b$. The shaded area under the PDF/PMF (left) equals the vertical jump $F(b)-F(a)$ on the CDF (right). Push $a$ all the way left to see $F(b)$ itself as an area. For the discrete case notice which endpoint is included.

Two small fixes to the original. (1) It wrote $F(x)=\int_{-\infty}^x f(x)\,dx$, reusing $x$ as both the limit and the integration variable. Use a dummy variable: $\int_{-\infty}^x f(t)\,dt$. (2) "$P(a\le X\le b)=F(b)-F(a)$" is only right for continuous $X$, where single points have probability zero. In general $F(b)-F(a)=P(a<X\le b)$. For an integer-valued $X$, $P(a\le X\le b)=F(b)-F(a-1)$.

$X\sim\Unif(0,\tfrac14)$. What is $f(0.1)$?
  • It can't be more than 1, so the question is ill-posed
  • $4$
  • $0.25$
  • $0$, because $P(X=0.1)=0$
The density is $1/(b-a)=4$ on $[0,\tfrac14]$. Densities can exceed 1; only areas under them are probabilities. And yes, $P(X=0.1)=0$, but that is a probability, not the density.

Inequalities

When you can't compute a probability exactly (or don't know the distribution), you can still bound it using only a mean or a variance. These bounds are loose, but they are universal, and they power the proofs of the limit theorems.

Markov's inequality

For any non-negative random variable $X$ and any $a>0$:

$$P(X\ge a)\le\frac{\E[X]}{a}$$

If the average income is 50k, at most 1 in 10 people can earn 500k or more. Otherwise those people alone would push the average above 50k. Non-negativity matters: no one can have negative income to "cancel out" the rich.

Proof

Drop the part of the sum below $a$ (it's non-negative), then replace each remaining $x$ by the smaller value $a$:

$$\E[X]\ge\sum_{x\ge a}x\,P(X=x)\ge a\sum_{x\ge a}P(X=x)=a\,P(X\ge a).$$

Slicker version for any $X\ge0$: pointwise $a\,\1[X\ge a]\le X$. Take expectations to get $a\,P(X\ge a)\le\E[X]$.

Chebyshev's inequality

For any random variable with mean $\mu$ and variance $\sigma^2$ (no non-negativity needed):

$$P(|X-\mu|\ge k\sigma)\le\frac{1}{k^2}\qquad\Longleftrightarrow\qquad P(|X-\mu|\ge\epsilon)\le\frac{\sigma^2}{\epsilon^2}$$

The right form substitutes $\epsilon=k\sigma$. Equivalently, at least $1-1/k^2$ of the probability lies within $k$ standard deviations of the mean. For example, at least 75% lies within 2 sd and at least 89% within 3 sd, for any distribution. Compare with the normal's 95% and 99.7%.

Proof: apply Markov to $(X-\mu)^2$ $$P(|X-\mu|\ge k\sigma)=P\big((X-\mu)^2\ge k^2\sigma^2\big)\le\frac{\E[(X-\mu)^2]}{k^2\sigma^2}=\frac{\sigma^2}{k^2\sigma^2}=\frac1{k^2}.$$

The square makes the variable non-negative, which is exactly what Markov needs.

How loose are Markov and Chebyshev?
Solid curves are the true tail probabilities, and dashed curves are the bounds. The bound is always above the truth, often far above. Pick "worst case" to see a distribution where each bound is hit exactly (so they can't be improved without more information).

In an interview, if you are asked to "bound" a probability with only a mean, reach for Markov. With a variance, reach for Chebyshev. If you have independence and want an exponentially small bound, mention Chernoff/Hoeffding bounds (apply Markov to $e^{tX}$).

A non-negative random variable has mean 2 and variance 1. What is the best bound you can give on $P(X\ge 5)$ from Markov and Chebyshev?
  • $2/5$ (Markov)
  • $1/25$
  • $1/4$
  • $1/9$ (Chebyshev)
Markov gives $2/5=0.4$. Chebyshev: $X\ge5$ means $|X-2|\ge3=3\sigma$, so $P\le1/9\approx0.11$. Take the better (smaller) one: $1/9$. (A one-sided version, Cantelli's inequality, gives the slightly better $1/10$.)

Jensen's inequality

Jensen tells you how expectations interact with curved functions:

$$\varphi\text{ convex}\implies\varphi(\E[X])\le\E[\varphi(X)]\qquad\qquad\varphi\text{ concave}\implies\varphi(\E[X])\ge\E[\varphi(X)]$$

A convex function curves upward like a bowl. Every chord between two points on the curve lies above the curve. $\E[\varphi(X)]$ is a point on such a chord (an average of the endpoint heights), while $\varphi(\E X)$ is on the curve directly below it. To remember the direction, use $\varphi(x)=x^2$ with $X=\pm1$: $\varphi(\E X)=\varphi(0)=0$ but $\E[\varphi(X)]=1$. This is just $\Var X\ge0$.

Chord above, curve below
$X$ takes value $x_1$ with probability $1-p$ and $x_2$ with probability $p$. The orange point $(\E X,\E\varphi(X))$ slides along the chord, and the blue point $(\E X,\varphi(\E X))$ sits on the curve. The pink gap is the "Jensen gap". It flips sign for concave functions and vanishes for linear ones.

Convex ($\varphi''\ge0$, slope increasing):

  • $x^2,\ x^4,\dots$ ($x^n$ for even $n$)
  • $|x|$
  • $a^x$ for $a>1$ (e.g. $e^x$)
  • $1/x$ for $x>0$
  • $\max(x_1,x_2,\dots)$

Concave ($\varphi''\le0$, slope decreasing):

  • $\sqrt x$
  • $\log x$
  • $x^p$ for $0<p<1$
  • $\min(x_1,x_2,\dots)$

Linear functions are both convex and concave, so Jensen holds with equality: that is linearity of expectation. ($|x|$ and $\max$ aren't twice differentiable, but they are convex by the chord definition.)

Worth memorizing: $\log\E[X]\ge\E[\log X]$, and $\E[1/X]\ge1/\E[X]$ for positive $X$.

You drive 60 km at a speed chosen uniformly from $\{30, 90\}$ km/h. Is the expected travel time more or less than 60/(expected speed) = 1 hour?
  • More, since $t=60/v$ is convex in $v$
  • Less, since $t=60/v$ is concave in $v$
  • Exactly 1 hour, by linearity
$\E[60/V]=\tfrac12(2+\tfrac23)=\tfrac43$ hours $>1$. Since $1/v$ is convex, $\E[1/V]\ge1/\E[V]$. This is why "average speed" puzzles trip people up.

AM–GM inequality

For non-negative numbers, the arithmetic mean is at least the geometric mean, with equality iff all $a_i$ are equal:

$$\frac{a_1+\cdots+a_n}{n}\ \ge\ \sqrt[n]{a_1\cdots a_n}$$

The original notes wrote the inequality sign backwards ($\le$), contradicting their own sentence "arithmetic mean always ≥ geometric mean". Sanity check: $a=(1,4)$ gives AM $=2.5\ge$ GM $=2$.

Proof via Jensen

Let $X$ be uniform on $\{a_1,\dots,a_n\}$ (all $a_i>0$; if some $a_i=0$ the GM is 0 and there's nothing to prove). Since $\log$ is concave, $\log\E[X]\ge\E[\log X]$:

$$\log\frac{a_1+\dots+a_n}{n}\ \ge\ \frac1n\sum_i\log a_i=\log\sqrt[n]{a_1\cdots a_n}.$$

Exponentiate both sides ($e^x$ is increasing, so the inequality is preserved).

Cauchy–Schwarz inequality

$$\big(\E[XY]\big)^2\le\E[X^2]\,\E[Y^2]\qquad\qquad\Big(\sum_{i=1}^n x_iy_i\Big)^2\le\Big(\sum_{i=1}^n x_i^2\Big)\Big(\sum_{i=1}^n y_i^2\Big)$$

Geometrically, it is $|\langle x,y\rangle|\le\|x\|\,\|y\|$: a dot product can't exceed the product of the lengths. Applied to the centered variables $X-\E X$ and $Y-\E Y$, it says $|\Cov(X,Y)|\le\sigma_X\sigma_Y$, i.e. correlation is always between −1 and 1.

Proof (the discriminant trick)

For every real $t$, $0\le\E[(X-tY)^2]=\E[X^2]-2t\,\E[XY]+t^2\,\E[Y^2]$. A quadratic in $t$ that is never negative has at most one root, so its discriminant is $\le0$:

$$4\,\E[XY]^2-4\,\E[X^2]\,\E[Y^2]\le0.$$

Union bound

$$P(A_1\cup A_2\cup\cdots\cup A_n)\le P(A_1)+P(A_2)+\cdots+P(A_n)$$

Adding the probabilities double-counts the overlaps, so the sum can only overshoot. It needs no independence at all, and it is tight when the events are disjoint. Proof in one line: $\1[\cup A_i]\le\sum_i\1[A_i]$ pointwise, then take expectations.

Typical use: "show that with high probability none of $n$ bad things happen". If each has probability $\le\delta/n$, the union bound gives $P(\text{any})\le\delta$.

Conditional probability

Conditioning on $B$ means: throw away every outcome where $B$ didn't happen, and renormalize what's left so it sums to 1.

$$P(A\mid B)=\frac{P(A\cap B)}{P(B)}$$

With two random variables $X$ and $Y$ there are three related distributions. Here is a small example joint table:

$Y=0$$Y=1$marginal $P(X=x)$
$X=0$0.300.100.40
$X=1$0.200.400.60
marginal $P(Y=y)$0.500.501

Bayes' rule

$$P(A\mid B)=\frac{P(B\mid A)\,P(A)}{P(B)},\qquad P(B)=P(B\mid A)P(A)+P(B\mid A^c)P(A^c)$$
Proof

Write the joint probability two ways: $P(A\cap B)=P(A\mid B)P(B)=P(B\mid A)P(A)$. Divide by $P(B)$.

The medical test, as 1,000 people
Each dot is a person. Sick people are pink, and those who test positive are drawn solid. Among everyone who tests positive (all the solid dots), what fraction is actually sick? With a rare disease, the false positives (solid orange) from the huge healthy group swamp the true positives.

Natural frequencies beat formulas. Disease prevalence 1%, test sensitivity 90%, false-positive rate 9%. In 1,000 people: 10 sick, of whom 9 test positive. 990 healthy, of whom about 89 test positive. So only $9/(9+89)\approx9\%$ of positives are sick. The prior matters enormously.

Odds form (fast mental math): posterior odds = prior odds × likelihood ratio.

$$\frac{P(A\mid B)}{P(A^c\mid B)}=\frac{P(A)}{P(A^c)}\cdot\frac{P(B\mid A)}{P(B\mid A^c)}$$

Above: prior odds $1:99$, likelihood ratio $0.9/0.09=10$, posterior odds $10:99$, so $P\approx 10/109\approx9\%$. For repeated independent tests, just multiply in another likelihood ratio.

One of 100 coins is double-headed; the rest are fair. You pick a coin at random and flip it 5 times: all heads. Probability it's the double-headed coin?
  • $1/100$
  • $32/131$
  • $31/32$
  • $1/2$
Prior odds $1:99$. The likelihood ratio is $1/(1/2)^5=32$. Posterior odds are $32:99$, so $P=32/131\approx0.24$.

Law of total probability

Split the world into disjoint cases $Y=y$ (a partition), compute the probability in each case, and average using how likely each case is:

$$P(A)=\sum_yP(A\mid Y=y)\,P(Y=y)$$

This is the "branching tree" picture: multiply along each branch, then add over the branches. It is how you compute the denominator in Bayes' rule.

Law of total expectation (tower property)

The same idea for averages. The overall average is the weighted average of the case-by-case averages:

$$\E[X]=\sum_y\E[X\mid Y=y]\,P(Y=y)\qquad\text{or}\qquad\int_{-\infty}^{\infty}\E[X\mid Y=y]\,f_Y(y)\,dy$$ $$\text{compactly:}\qquad \E[X]=\E_Y\big[\E[X\mid Y]\big]$$

In the compact form, $\E[X\mid Y]$ is itself a random variable: a function of $Y$ that takes the value $\E[X\mid Y=y]$ when $Y=y$. This is the engine behind first-step analysis, where you condition on the first step.

Proof (discrete) $$\sum_y\E[X\mid Y=y]P(Y=y)=\sum_y\sum_x x\,\frac{P(X=x,Y=y)}{P(Y=y)}P(Y=y)=\sum_x x\sum_yP(X=x,Y=y)=\sum_x x\,P(X=x)=\E[X].$$
Conditioning as a tree: roll a die, then flip that many coins
$Y$ is a die roll. Then flip $Y$ coins with heads-probability $p$, and let $X$ be the number of heads. Given $Y=y$, $X\sim\Bin(y,p)$, so $\E[X\mid Y=y]=yp$. Each branch contributes (branch probability) × (branch average). Try a loaded die, then simulate to check.
You flip a fair coin. On heads you roll one die, and on tails you roll two dice and add them. What is the expected total?
  • $3.5$
  • $7$
  • $5.25$
  • $4.5$
$\E[X]=\tfrac12\cdot3.5+\tfrac12\cdot7=5.25$. Condition on the coin, then average the conditional means.
Bonus: law of total variance ("Eve's law") $$\Var(X)=\underbrace{\E\big[\Var(X\mid Y)\big]}_{\text{average spread within groups}}+\underbrace{\Var\big(\E[X\mid Y]\big)}_{\text{spread between group means}}$$

In the die-and-coins example with a fair die and fair coins: $\Var(X\mid Y)=Y/4$ and $\E[X\mid Y]=Y/2$, so $\Var X=\E[Y]/4+\Var(Y)/4=\tfrac{3.5}{4}+\tfrac{35/12}{4}\approx1.604$.

Limit theorems

Two theorems about the sample mean $\bar X_n=\frac1n\sum_{i=1}^nX_i$ of $n$ iid draws with mean $\mu$ and variance $\sigma^2$. The LLN says where $\bar X_n$ goes (to $\mu$). The CLT says how it fluctuates on the way (Gaussian, with width $\sigma/\sqrt n$).

Law of large numbers

$$P\big(|\bar X_n-\mu|>\epsilon\big)\ \to\ 0\qquad\text{as }n\to\infty,\ \text{for any }\epsilon>0$$

In words, the running average of many independent draws gets arbitrarily close to the true mean with probability approaching 1. This is why casinos always win in the long run, and why "expected value" is the right thing to optimize for repeated bets.

Proof from Chebyshev (when $\sigma^2<\infty$)

$\E[\bar X_n]=\mu$ and $\Var(\bar X_n)=\sigma^2/n$ (derived below). Apply Chebyshev in its $\epsilon$-form:

$$P\big(|\bar X_n-\mu|>\epsilon\big)\le\frac{\Var(\bar X_n)}{\epsilon^2}=\frac{\sigma^2}{n\epsilon^2}\ \to\ 0.$$
Running averages settle into the ε-band
Each line is one person's running average of fair die rolls (true mean 3.5). The x-axis is logarithmic. The green band is $\mu\pm\epsilon$. The dashed orange curves are $\mu\pm2\sigma/\sqrt n$ (two standard errors), which is the funnel the paths squeeze through.

The gambler's fallacy is not the LLN. After 10 heads in a row the next flip is still 50/50. The average converges not because the coin "compensates", but because the early streak is diluted by an ever larger number of ordinary flips.

Central limit theorem

Whatever the shape of the distribution of each $X_i$ (skewed, bimodal, discrete…), as long as it has finite variance, the sample mean is approximately Gaussian for large $n$:

$$\bar X_n=\frac1n\sum_{i=1}^nX_i\ \approx\ \N\!\left(\mu,\ \frac{\sigma^2}{n}\right)\qquad\Longleftrightarrow\qquad\frac{\bar X_n-\mu}{\sigma/\sqrt n}\ \xrightarrow{d}\ \N(0,1)$$

Adding many independent random pieces washes out the individual quirks: lumps in one draw get averaged against dips in others, and only the mean and the variance survive. You already saw a preview with sums of uniforms.

CLT: any shape → bell curve
Pick a strange source distribution and the number $n$ of draws to average. The histogram shows 4,000 sample means and the curve is the CLT prediction $\N(\mu,\sigma^2/n)$. At $n=1$ you see the source itself. Use "standardized" view to zoom in on the shape as it narrows.

Where $\sigma^2/n$ comes from (this part is exact, no approximation):

$$\Var(\bar X_n)=\Var\!\Big(\frac1n\sum_{i=1}^nX_i\Big)=\frac1{n^2}\Var\!\Big(\sum_{i=1}^nX_i\Big)=\frac1{n^2}\sum_{i=1}^n\Var(X_i)=\frac{n\sigma^2}{n^2}=\frac{\sigma^2}{n}$$

Step 2 uses $\Var(aX)=a^2\Var X$. Step 3 uses independence (uncorrelated is enough).

The standard error is the standard deviation of $\bar X_n$:

$$\text{SE}=\frac{\sigma}{\sqrt n}$$

The error shrinks like $1/\sqrt n$. To make the error 10× smaller you need 100× more samples. Halving it costs 4×.

The original notes said "error shrinks like $\sqrt n$". It shrinks like $1/\sqrt n$ (equivalently, precision grows like $\sqrt n$). The "100× samples for 10× less error" conclusion was right.

A $(1-\alpha)$ confidence interval for $\mu$ (with known $\sigma$) is

$$\bar X_n\pm z_{1-\alpha/2}\cdot\frac{\sigma}{\sqrt n},$$

for example $\bar X_n\pm1.96\,\sigma/\sqrt n$ for 95%. See the z-table.

Fine print. The CLT is an approximation for large $n$, not an exact statement (unless the $X_i$ are themselves Gaussian). It needs finite variance: averages of Cauchy variables never converge to anything. Convergence is slower for very skewed sources (try Bernoulli(0.05) above with small $n$). The original notes' "is Gaussian" should be read as "is approximately Gaussian".

Typical question: "A fair coin is flipped 10,000 times. Roughly what is the probability of more than 5,100 heads?" The count of heads has mean 5,000 and sd $\sqrt{10000\cdot\tfrac14}=50$. 5,100 is 2 sd above the mean, so the answer is about $P(Z>2)\approx2.3\%$.

A poll of 400 people has a margin of error of ±5%. Roughly how many people do you need for ±1%?
  • 2,000
  • 800
  • 4,000
  • 10,000
Error $\propto1/\sqrt n$. Making it 5× smaller needs $5^2=25$× more samples: $400\times25=10{,}000$.

Cheat sheet

FactFormulaNeeds
Linearity$\E[aX+bY+c]=a\E X+b\E Y+c$nothing
Tail formula$\E X=\int_0^\infty P(X>x)\,dx$$X\ge0$
Variance$\E[X^2]-(\E X)^2$; $\ \Var(aX+b)=a^2\Var X$nothing
Sum of variances$\Var(X+Y)=\Var X+\Var Y$uncorrelated
Product$\E[XY]=\E X\,\E Y$independent (or uncorrelated)
Markov$P(X\ge a)\le\E X/a$$X\ge0$
Chebyshev$P(|X-\mu|\ge k\sigma)\le1/k^2$finite variance
Jensen$\varphi(\E X)\le\E\varphi(X)$$\varphi$ convex
Bayes$P(A\mid B)=P(B\mid A)P(A)/P(B)$$P(B)>0$
Tower$\E X=\E[\E[X\mid Y]]$nothing
LLN$\bar X_n\to\mu$iid, finite mean
CLT$\bar X_n\approx\N(\mu,\sigma^2/n)$iid, finite variance, large $n$