Probability & statistics — the working engineer’s course

Think of a coin with bias p. If someone hands you p = 0.7 and asks "what's the chance of 8+ heads in 10 flips?" — that is a probability question. You know the model; you predict data.

If instead someone hands you the sequence H H T H H H T H H H and asks "is this coin fair?" — that is a statistics question. You have data; you infer the model.

After surveying hundreds of ML interview reports, the questions cluster into four archetypes. Know the archetype and you know the playbook.

These five moves cover the vast majority of probability puzzles and estimation questions. Internalize them as a mental checklist, not as a linear recipe — sometimes you'll use 1, 3, and 5; sometimes just 4.

The chapters are ordered so each one builds on the previous. Here is where you are headed and why the sequence is the way it is.

Concrete first. You pick an outfit: 3 shirts and 4 pants. How many outfits? Draw a tree: for each of the 3 shirts you have 4 pant choices, giving 3 × 4 = 12 outfits. You never need to list them all.

Now generalize. If task 1 has n₁ outcomes and, regardless of what happened in task 1, task 2 has n₂ outcomes, then the two-step process has n₁ · n₂ outcomes. The "regardless" is key — outcomes of different steps must be independent of each other for simple multiplication to work.

Three books on a shelf — your running example. Call the books A, B, C. How many ways to arrange all three? You have 3 choices for position 1, then 2 remaining for position 2, then 1 for position 3: 3 × 2 × 1 = 6. The six arrangements: ABC, ACB, BAC, BCA, CAB, CBA. We'll revisit this throughout.

Concrete first. From the 3 books A, B, C, choose 2 and arrange them in a row. Your choices: AB, BA, AC, CA, BC, CB — that's 6 ordered pairs. Using the multiplication rule: 3 choices for spot 1, 2 remaining choices for spot 2 → 3 × 2 = 6.

General formula. Picking k items in order from n distinct items without replacement:

For our example: P(3,2) = 3!/1! = 6. Full arrangement of all 3: P(3,3) = 3! = 6 (confirming the earlier count).

Concrete first. From books A, B, C, choose 2 to put in a bag (order doesn't matter). The choices: {A,B}, {A,C}, {B,C} — just 3. Compare to the 6 ordered pairs above: we've divided by 2! = 2 because each unordered pair was counted twice (AB and BA are the same bag).

General formula. Choosing k items from n without replacement, order not mattering:

For our example: C(3,2) = 3!/(2!·1!) = 3. Confirm: {A,B}, {A,C}, {B,C}. ✓

Key symmetry: C(n,k) = C(n, n−k). Choosing which k to include is the same as choosing which n−k to exclude. C(10,3) = C(10,7) = 120.

Poker hands warm-up. A 52-card deck, 5-card hand, order doesn't matter: C(52,5) = 52!/(5!·47!) = 2,598,960 possible hands. That's the denominator for every poker probability.

Counting problems come in exactly four flavors based on two binary questions: Is selection ordered? Is replacement allowed? The grid below maps each case to its formula and a canonical example.

The donut problem. You walk into a shop with 4 flavors (glazed, chocolate, jelly, plain). You want to pick 3 donuts; you can pick any flavor more than once; the bag is unordered. How many distinct bags?

Represent each selection as 3 stars placed among 4 bins separated by 3 bars. Example: ★ | ★★ | | means 1 glazed, 2 chocolate, 0 jelly, 0 plain. The number of ways to arrange 3 stars and 3 bars among 6 positions is:

You can verify the small case: with 2 flavors and 2 donuts, C(3,2) = 3 bags: {GG, GC, CC}. ✓

The problem with "or." How many integers from 1 to 30 are divisible by 2 or by 3? Naively: 15 divisible by 2, 10 divisible by 3. Adding gives 25 — but that double-counts the 5 numbers divisible by 6. Correct answer: 15 + 10 − 5 = 20.

This is inclusion-exclusion for two sets: |A ∪ B| = |A| + |B| − |A ∩ B|. For three sets:

Derangements — the classic application. A derangement is a permutation where no item is in its original position (think: a secret Santa where no one draws themselves). Let D(n) be the count. For n=3 books: total permutations = 6; the derangements of [A,B,C] are [B,C,A] and [C,A,B] — only 2.

Using inclusion-exclusion, the general formula is:

For n=3: D(3) = 3!(1 − 1 + 1/2 − 1/6) = 6 · (1/3) = 2. ✓

Fix a running example we'll use throughout: roll two fair six-sided dice. Call them die 1 and die 2.

The sample space Ω is the set of all outcomes the experiment can produce. Here:

An event is any subset of Ω — a collection of outcomes you want to lump together and ask "what is the chance of this?"

Probability is a function P that assigns a number to each event. Kolmogorov (1933) gave three rules that pin down every valid probability measure. Memorise the plain-words version; the formal version will follow naturally.

From just these three axioms you can derive everything: the complement rule, inclusion-exclusion, the union bound, conditional probability. They are not arbitrary — they are the minimal rules that make probability coherent.

Two dice — quick sanity checks:

• P(sum = 7) = 6/36 = 1/6. Six favourable outcomes, 36 equally likely total.
• P(sum ≠ 7) = 1 − 1/6 = 5/6. Complement rule.
• P(A ∪ C) where A = {sum=7} and C = {doubles}: A ∩ C = ∅ (no double sums to 7), so P(A ∪ C) = 6/36 + 6/36 = 12/36 = 1/3.

You roll the two dice behind a screen. A friend peeks and tells you "die 1 is a 3." Knowing this, what is the probability the sum is 7?

Before the hint, 36 outcomes were possible. After the hint, only 6 outcomes survive — those where die 1 = 3: (3,1),(3,2),(3,3),(3,4),(3,5),(3,6). Of these six, exactly one has sum 7: (3,4). So the answer is 1/6.

That reasoning is the entire mechanism of conditional probability. The hint shrinks the universe from 36 outcomes to 6, and you re-do your calculation inside the smaller universe.

Dice example formally: A = {sum = 7}, B = {die 1 = 3}.

• P(A ∩ B) = P({(3,4)}) = 1/36
• P(B) = 6/36 = 1/6
• P(A | B) = (1/36) / (1/6) = 1/6. Matches the counting argument.

Rearranging the conditional probability formula gives the chain rule (also called the multiplication rule):

This extends to any number of events:

Dice example: P(die 1 = 3 AND sum = 7) = P(sum = 7 | die 1 = 3) · P(die 1 = 3) = (1/6)(1/6) = 1/36. ✓

The chain rule is the backbone of probabilistic graphical models and language model factorisation. GPT-style models generate text by computing P(token_t | token₁, …, token_t-1) for each position — that is literally the chain rule applied left-to-right.

After two dice are rolled, does knowing die 1 = 3 tell you anything about whether die 2 = 5? No — the dice don't talk to each other. Formally:

Check with dice: A = {die 1 = 3}, B = {die 2 = 5}.

• P(A) = 1/6, P(B) = 1/6.
• P(A ∩ B) = P({(3,5)}) = 1/36 = (1/6)(1/6). ✓ Independent.

Contrast: A = {sum = 7}, B = {die 1 = 3}.

• P(A) = 1/6, P(B) = 1/6.
• P(A ∩ B) = 1/36 = (1/6)(1/6). Equal — so sum = 7 and die 1 = 3 are independent!
• Sanity check: P(sum = 7 | die 1 = 3) = 1/6 = P(sum = 7). Knowing die 1 doesn't change the probability of sum 7? Yes — because die 2 is equally likely to be any of {1,…,6}, and exactly one of those completes a sum of 7.

Non-independent events: A = {sum = 7}, D = {die 1 = 1}.

• P(D) = 1/6, P(A) = 1/6, P(A ∩ D) = P({(1,6)}) = 1/36.
• P(A | D) = (1/36)/(1/6) = 1/6 = P(A). Still independent! (Every specific value of die 1 leaves the same 1-in-6 chance of sum 7.)

Try: A = {sum = 7}, E = {sum = 8}. P(A) = 6/36, P(E) = 5/36, P(A ∩ E) = 0 (a roll can't sum to both 7 and 8). Product = 6/36 · 5/36 ≠ 0. Not independent. They are, however, mutually exclusive — which leads directly to the big confusion.

A and B are conditionally independent given C when:

Naive Bayes classifiers assume that all features are conditionally independent given the class label. This is almost certainly false in reality, yet the model often works well in practice — understanding why requires conditional independence.

Dice micro-example: Let A = {die 1 is odd}, B = {die 2 is odd}, C = {sum is even}. Given that the sum is even, die 1 and die 2 must both be odd or both be even — knowing die 1 is odd forces die 2 to be odd. So A and B are not conditionally independent given C, even though they are marginally independent.

Suppose you want P(some event A) but it's hard to compute directly. The trick: find a partition of Ω — a set of mutually exclusive, exhaustive events B₁, B₂, …, B_k that cover everything — then compute P(A | B_i) separately for each case and average.

Dice worked example: A = {sum is prime}. Primes in range 2–12: {2, 3, 5, 7, 11}. Partition on die 1 value (B_i = {die 1 = i}):

• Die 1 = 1: need die 2 ∈ {1,2,4,6} (sum ∈ {2,3,5,7}). Count: 4. P(A|die1=1) = 4/6.
• Die 1 = 2: need die 2 ∈ {1,3,5} (sum ∈ {3,5,7}). Count: 3. P(A|die1=2) = 3/6.
• Die 1 = 3: need die 2 ∈ {2,4} (sum ∈ {5,7}). Count: 2. P(A|die1=3) = 2/6.
• Die 1 = 4: need die 2 ∈ {1,3} (sum ∈ {5,7}). Count: 2. P(A|die1=4) = 2/6.
• Die 1 = 5: need die 2 ∈ {2,6} (sum ∈ {7,11}). Count: 2. P(A|die1=5) = 2/6.
• Die 1 = 6: need die 2 ∈ {1,5} (sum ∈ {7,11}). Count: 2. P(A|die1=6) = 2/6.

P(A) = (1/6)(4+3+2+2+2+2)/6 = 15/36 = 5/12. (We can verify by counting directly: 15 prime-sum pairs out of 36.)

Direct counting of "at least one six" is error-prone — you'd have to subtract overlaps. The complement approach is the standard tool.

Complement rule: P(at least one 6 in 4 rolls) = 1 − P(no 6 in 4 rolls).

Each roll is independent. P(no 6 on one roll) = 5/6. So:

The Chevalier de Méré story (3 sentences): In 1654, the French gambler Antoine Gombaud (Chevalier de Méré) bet that he'd see at least one double-six in 24 rolls of two dice, reasoning it should be as likely as one six in four rolls of one die. He was losing money and asked Blaise Pascal why. Pascal showed him that P(at least one double-six in 24 rolls) = 1 − (35/36)²⁴ ≈ 0.491 — just under 50% — while the analogous single-die game had probability ≈ 0.518, and the two events are not equivalent because the probability of a double-six (1/36) differs from the probability of a six (1/6) in a way that doesn't scale linearly with the number of rolls.

This correspondence between Pascal and Fermat founded modern probability theory. The lesson for interviews: when you see "at least one," flip to the complement. The complement is almost always one clean product.

From Chapter 3, we know that for any two events A and B:

Set the two right-hand sides equal and divide both sides by P(B):

There is no magic here — it is literally just rearranging the chain rule. The insight is in what you choose to call A and B.

A disease affects 1% of the population. A test for this disease has:

• Sensitivity (true positive rate): 99% — if you have the disease, the test is positive 99% of the time.
• Specificity (true negative rate): 95% — if you don't have the disease, the test is negative 95% of the time. Equivalently, the false positive rate is 5%.

You test positive. What is the probability you have the disease?

Most people, including many physicians in studies, say "about 99%" — because the test is "99% accurate." The actual answer is about 17%. Here is why.

Instead of manipulating fractions, imagine 10,000 people drawn randomly from the population and trace them through the test.

How to read the table:

• 100 people have the disease. The test catches 99% of them → 99 true positives, 1 false negative.
• 9,900 people don't have the disease. The test wrongly flags 5% of them → 495 false positives, 9,405 true negatives.
• Total positive tests: 99 + 495 = 594.
• Of these 594 positive tests, only 99 are real disease cases.

The base-rate punchline: The 495 false positives swamp the 99 true positives because the disease is rare. A positive test shifts your probability from 1% (the prior) to ~17% (the posterior) — a 17× increase, but still well short of certainty. If the disease had 10% prevalence, the posterior would be ~69%. The prior matters enormously.

There is a cleaner version of Bayes' rule that makes mental updating instant. Define the odds of an event A as:

Now write Bayes' rule for A vs A^c both conditioned on evidence B:

Medical test in odds form:

• Prior odds = P(disease)/P(no disease) = 0.01/0.99 ≈ 1:99.
• Likelihood ratio = P(+|disease)/P(+|no disease) = 0.99/0.05 = 19.8.
• Posterior odds = 19.8 × (1/99) ≈ 0.2 = 1:5.
• Posterior probability = 1/(1+5) ≈ 0.167. ✓ Matches the table.

The odds form is the fast mental tool: the likelihood ratio is a single number that tells you how strongly the evidence shifts your belief. A likelihood ratio of 1 means the evidence is neutral. Greater than 1 means evidence supports A. Less than 1 means evidence supports A^c.

Suppose you run a second, independent test on the same patient (a different biomarker with LR = 25 for a second positive). You don't need to redo the full Bayes calculation from scratch. The posterior odds after the first test become the new prior odds, and you multiply by the second likelihood ratio.

After test 1 (LR₁ = 19.8): odds ≈ 1:5, probability ≈ 17%.

After test 2 (LR₂ = 25): odds = 25 × (1/5) = 5:1, probability ≈ 5/6 ≈ 83%.

Two positive tests on a rare disease go from 17% to 83% — still not certainty, but now you'd treat.

Spam filter as sequential Bayes: A Naive Bayes spam classifier does exactly this. Each word in an email is a "test." The prior P(spam) is the base rate of spam in your inbox. Each word w updates the odds by a likelihood ratio P(w|spam)/P(w|not spam). Words like "Viagra" have very high LR (much more common in spam); words like "meeting" have LR ≈ 1 (equally common in both). The model multiplies all these likelihood ratios together, which in log space is a sum — and that's why Naive Bayes classifiers produce a linear function of log word counts.

Bayes' rule is not just a medical-testing curiosity — it is the backbone of three major ML concepts that appear in nearly every interview at a top lab.

Naive Bayes classifiers. Given a document with words w₁, …, w_n, the classifier computes:

Training: count word frequencies per class. Inference: multiply the prior by each word's likelihood. Add-one (Laplace) smoothing prevents zero probabilities for unseen words. In log space the product becomes a sum — making Naive Bayes a linear classifier in log word counts.

MAP estimation. Maximum A Posteriori estimation picks the parameter θ that maximises the posterior:

Concrete example: logistic regression with L2 regularisation is MAP estimation under a Gaussian prior on the weights. The strength λ of regularisation equals 1/σ² where σ² is the prior variance. Stronger prior (smaller σ) → higher λ → more regularisation → weights shrunk harder toward zero.

Bayesian A/B testing. Instead of a p-value, compute P(variant B is better than variant A | observed data) directly. Start with a prior over conversion rates (e.g., Beta(1,1) for ignorance), observe conversions, update to a Beta posterior, and compute the probability that the posterior draw from B exceeds the draw from A. There is no fixed sample size, no peeking problem in the classical sense — you just read off posterior probabilities. Chapter 14 covers this in full; the Bayes machinery here is the foundation.

Roll a fair six-sided die. The sample space is Ω = {1,2,3,4,5,6}. Define X(ω) = ω. That's it — X is a function from outcomes to real numbers. Nothing mysterious.

Now define Y = 1 if X is even, 0 otherwise. Y is a different random variable on the same experiment. One experiment, infinitely many possible RVs.

Toy example first. Let Z be the net gain from a game: you win \$2 with prob 1/4, win \$0 with prob 1/2, lose \$1 with prob 1/4.

That table is the PMF. Two rules it must satisfy:

Check: 1/4 + 1/2 + 1/4 = 1. ✓

For a continuous RV X, we cannot list P(X=x) — it is always zero. Instead, probability lives in intervals:

Two rules for a valid PDF:

Both discrete and continuous RVs have a CDF:

Properties every CDF must have:

• Non-decreasing: if a ≤ b then F(a) ≤ F(b).
• Right-continuous: F(x) = lim_{t→x⁺} F(t).
• Limits: F(−∞) = 0, F(+∞) = 1.

Discrete CDF example. For the game above (Z ∈ {−1, 0, 2}):

The CDF jumps at each mass point; the jump size equals the PMF value there.

Going back: PDF = dF/dx (where it exists); PMF = jump size at each point.

The p-th quantile (or p-th percentile) of X is the smallest value q such that F(q) ≥ p:

Key quantiles to know: Q(0.5) = median; Q(0.25) = first quartile; Q(0.75) = third quartile. For a standard Normal, Q(0.975) ≈ 1.96 — the famous "1.96σ" CI boundary comes straight from this.

Given X with known distribution, define Y = g(X). What is Y's distribution?

CDF method (always works): F_Y(y) = P(Y ≤ y) = P(g(X) ≤ y). Invert g, find the x-region, integrate f_X.

Jacobian formula (differentiable, monotone g):

Tiny example. X ~ Uniform(0,1); Y = −log X. Then g⁻¹(y) = e⁻ʸ and |d/dy e⁻ʸ| = e⁻ʸ. So f_Y(y) = 1 · e⁻ʸ = e⁻ʸ for y > 0 — that is the Exponential(1) density. This is how you transform a Uniform into an Exponential.

The inverse-transform method: if U ~ Uniform(0,1) and F is any CDF, then X = F⁻¹(U) has distribution F. This is the foundation of all basic random-number generation.

import numpy as np

# Sample from Exponential(lambda=2) using inverse-CDF
rng = np.random.default_rng(42)
U = rng.uniform(0, 1, size=10_000)   # Step 1: uniform samples
lam = 2.0
X = -np.log(U) / lam                 # Step 2: apply F_inv(u) = -log(u)/lambda
# X now has distribution Exponential(2)
print(X.mean(), X.var())             # Should be ~0.5, ~0.25

Why it works: P(F⁻¹(U) ≤ x) = P(U ≤ F(x)) = F(x) since U is Uniform(0,1). The CDF of F⁻¹(U) is exactly F. ✓

Bernoulli(p) — Story: one coin flip with heads probability p.

Mean = p. Var = p(1−p). ML cameo: the output of a logistic classifier; every binary cross-entropy loss assumes Bernoulli noise.

Binomial(n, p) — Story: count the number of heads in n independent coin flips.

Mean = np. Var = np(1−p). Note: Binomial(1,p) = Bernoulli(p). Sum of independent Bernoullis is Binomial.

Poisson(λ) — Story: count rare events in a fixed time window (λ = expected count).

Mean = λ. Var = λ. The hallmark: mean equals variance. ML cameo: click counts, word counts in text (bag-of-words), arrival queues.

Geometric(p) — Story: number of trials until the first success (inclusive).

Mean = 1/p. Var = (1−p)/p². Caution: some textbooks define Geometric as the number of failures before success (starting at 0) — always check the support.

Memoryless property of the Geometric: P(X > m+k | X > m) = P(X > k). Past failures give no information about future success. The Geometric is the only discrete memoryless distribution.

Negative Binomial(r, p) — Story: number of trials until the r-th success. Geometric is the special case r=1.

Mean = r/p. Var = r(1−p)/p². ML cameo: over-dispersed count data where Var > Mean (unlike Poisson where they're equal); used for word frequency models in NLP.

Uniform(a, b) — Story: every value in [a,b] equally likely.

Mean = (a+b)/2. Var = (b−a)²/12. Foundation of inverse-CDF sampling; Uniform(0,1) is the source of all pseudo-random numbers.

Exponential(λ) — Story: waiting time until first event in a Poisson process with rate λ.

Mean = 1/λ. Var = 1/λ². The only continuous memoryless distribution. CDF: F(x) = 1 − e^{−λx}. ML cameo: inter-arrival times in queuing models; lifetime distributions in reliability; the base distribution in many Bayesian priors.

Poisson process plain words: Events arrive randomly over time such that (1) the number of arrivals in any interval depends only on its length, not location; (2) arrivals in disjoint intervals are independent; (3) at most one arrival per infinitesimal instant. Then: counts are Poisson(λt); inter-arrival times are Exponential(λ).

Gamma(α, β) — Story: sum of α independent Exponential(β) waiting times.

Mean = α/β. Var = α/β². Special cases: Gamma(1, β) = Exponential(β); Gamma(n/2, 1/2) = Chi-squared(n). ML cameo: conjugate prior for the Poisson rate and Gaussian precision.

Normal(μ, σ²) — Story: the limiting distribution of sums of many small independent effects (Central Limit Theorem).

Mean = μ. Var = σ². Standard Normal: μ=0, σ=1, written Z ~ N(0,1). Any Normal can be standardized: Z = (X−μ)/σ.

ML cameos everywhere: linear regression assumes Gaussian noise (MLE → OLS); neural network weights often initialized as Normal; CLT justifies using Normal approximations for sums/averages; the Gaussian kernel in SVMs and GPs; the reparameterization trick in VAEs samples X = μ + σ·ε with ε ~ N(0,1).

Log-Normal(μ, σ²) — If log X ~ Normal(μ, σ²), then X ~ LogNormal. Story: product of many small positive multiplicative effects. Mean = e^{μ+σ²/2}. ML cameo: income distributions, stock prices, file sizes — any quantity that is bounded below by 0 and right-skewed.

Beta(α, β) — Story: a probability on [0,1] with α−1 pseudo-successes and β−1 pseudo-failures as prior evidence.

ML cameo: conjugate prior for a Bernoulli/Binomial proportion; Bayesian A/B testing; Thompson sampling for bandits.

If you run an experiment many times and average the outcomes, the number you converge to is the expectation. Formally, for a discrete random variable $X$:

Tiny example. A fair die: values 1–6, each with probability $\tfrac{1}{6}$.

For a continuous RV, the sum becomes an integral: $E[X] = \int_{-\infty}^{\infty} x\, f(x)\, dx$, where $f$ is the PDF.

Center of mass picture. Imagine the probability mass function as a physical bar chart. The expectation is the balance point. Shifting all mass right shifts $E[X]$ right by the same amount — that's linearity in action.

For ANY random variables $X$ and $Y$ (dependent or not) and constants $a, b$:

An indicator random variable $I_A$ for event $A$ is the simplest possible RV: it equals 1 if $A$ occurs, 0 otherwise. Its expectation is just the probability of the event:

The strategy: write the count you want as $X = I_1 + I_2 + \cdots + I_n$, then use linearity to get $E[X] = \sum_i P(A_i)$. The $I_i$ are almost always dependent — it doesn't matter.

Classic 1: Expected number of fixed points of a random permutation.

Setup. Shuffle $n$ cards labeled 1 through $n$. A fixed point is a card in its original position. What is $E[\text{fixed points}]$?

Without indicators. You would need to enumerate all $n!$ permutations, count fixed points in each, and average. Hopeless for large $n$.

With indicators. Let $I_i = 1$ if card $i$ is in position $i$. Then fixed points $= \sum_{i=1}^n I_i$. By linearity:

The indicators $I_1, \ldots, I_n$ are heavily dependent (if $n-1$ cards are fixed, the last must be too), yet linearity gives us the answer in two lines.

Classic 2: Expected number of coupons to complete the collection.

Setup. There are $n$ distinct coupon types, each draw uniformly at random. How many draws $T$ until you have at least one of each type? (The coupon collector problem.)

Decompose the waiting time. Let $T_k$ = draws to go from $k-1$ distinct types to $k$ distinct types. Then $T = T_1 + T_2 + \cdots + T_n$. At stage $k$ you already have $k-1$ types, so any new draw is a success with probability $\frac{n-(k-1)}{n} = \frac{n-k+1}{n}$. The number of draws at stage $k$ is Geometric with success probability $p_k = \frac{n-k+1}{n}$, so $E[T_k] = \frac{n}{n-k+1}$. By linearity:

This is used in ML for estimating how many examples you need before seeing every class at least once — relevant to rare-category sampling and dataset coverage analysis.

Classic 3: Expected number of birthday pairs.

Setup. $n$ people, each born on one of 365 days uniformly. How many pairs share a birthday?

With indicators. There are $\binom{n}{2}$ pairs. For pair $(i,j)$ let $I_{ij} = 1$ if they share a birthday. Then:

This is consistent with the famous fact that 23 people gives ~50% chance of at least one shared birthday — there's roughly $0.69$ expected pairs, so one pair is quite likely.

Variance measures the average squared deviation from the mean:

The standard deviation $\sigma = \sqrt{\text{Var}(X)}$ restores the original units.

Covariance measures how two RVs move together:

Variance of a sum — the full formula:

Numeric 2-variable example. Let $X$ be the number shown on a fair coin mapped to $\{0,1\}$ (heads=1, tails=0), and $Y = 1 - X$ (the opposite). Then $E[X]=E[Y]=0.5$, $\text{Var}(X)=\text{Var}(Y)=0.25$.

$\text{Cov}(X,Y) = E[XY] - E[X]E[Y] = 0 - 0.25 = -0.25$ (since $XY=0$ always — they can't both be 1).

General formula for $n$ variables:

The Law of the Unconscious Statistician (LOTUS) says: to find the expected value of a function $g(X)$, you don't need the distribution of $g(X)$ — just plug into the original distribution of $X$.

Example. $X \sim \text{Uniform}\{1,2,3,4,5,6\}$ (fair die). What is $E[X^2]$?

LOTUS: $E[X^2] = \sum_{x=1}^6 x^2 \cdot \tfrac{1}{6} = \tfrac{1+4+9+16+25+36}{6} = \tfrac{91}{6} \approx 15.17$. Then $\text{Var}(X) = E[X^2] - (E[X])^2 = \tfrac{91}{6} - 3.5^2 = \tfrac{91}{6} - \tfrac{49}{4} = \tfrac{182-147}{12} = \tfrac{35}{12} \approx 2.92$.

LOTUS is used constantly: computing variance (via $E[X^2]$), moments, moment-generating functions, and the KL divergence $E[\log p(X)/q(X)]$ — all applications of LOTUS.

For convex f: E[f(X)] ≥ f(E[X]); for concave f the inequality flips. Picture: a chord above a convex curve — averaging the outputs lands you on the chord, above the function at the average input.

Where it bites in ML: (1) log-likelihood of an average ≠ average log-likelihood — why ensembling probabilities then logging beats averaging log-probs; (2) the ELBO: log p(x) = log E_q[p(x,z)/q(z)] ≥ E_q[log p(x,z)/q(z)] — variational inference IS one application of Jensen; (3) E[1/X] ≥ 1/E[X] — why averaging rates and averaging times disagree (harmonic-mean traps in throughput math).

A joint distribution over two random variables X and Y assigns a probability to every pair of values (x, y). For discrete RVs the joint PMF is:

All joint probabilities must sum to 1 over every pair of values. From the joint you can always recover the individual (marginal) distributions by summing out the other variable:

Let X = "first coin flip" and Y = "second coin flip," both fair. Each takes values in {0, 1} (0 = tails, 1 = heads). The flips are independent, so the joint probability of every pair is 1/4.

Now make it more interesting. Suppose X ∈ {0, 1} with P(X=0) = 0.6, P(X=1) = 0.4, and given X the conditional distribution of Y is:

• P(Y=1 | X=0) = 0.3 (so P(Y=0 | X=0) = 0.7)
• P(Y=1 | X=1) = 0.8 (so P(Y=0 | X=1) = 0.2)

The joint table (each cell = P(X=x) × P(Y=y|X=x), verified to sum to 1):

Arithmetic check: 0.42 + 0.18 + 0.08 + 0.32 = 1.00 ✓. Marginal P(Y=1) = 0.18 + 0.32 = 0.50 ✓.

Now recover a conditional from the joint. What is P(X=1 | Y=1)?

Interpretation: even though only 40% of the population has X=1, among those with Y=1 the fraction rises to 64%—because X=1 makes Y=1 much more likely.

Covariance measures how two RVs move together. Positive = they tend to rise together; negative = one rises as the other falls; zero = no linear tendency.

Correlation is covariance scaled to [−1, 1] by dividing by both standard deviations:

A concentration inequality answers: "How likely is a random variable to be far from its mean?" The three canonical tools trade assumption strength for tightness. We will carry one running example all the way through so the tightening is concrete.

Markov needs only one thing: X is non-negative. Nothing about variance or distribution shape.

Running example. $a = 6$, $E[X] = 3.5$:

Why so loose? Markov knows nothing about spread. A distribution could put all its mass at $a - \varepsilon$ and still satisfy $E[X] = 3.5$. Knowing the variance fixes that.

Apply Markov to the non-negative variable $(X - \mu)^2$. The result bounds the probability of deviating from the mean by more than $k$ standard deviations.

Running example. $X \ge 6$ means $X - 3.5 \ge 2.5$, i.e., deviation $\ge 2.5$. With $\sigma \approx 1.708$: $k = 2.5 / 1.708 \approx 1.464$.

The $1/k^2$ decay is slow. Chebyshev is tight only for pathological distributions (two-point). For bounded random variables we can do exponentially better.

When $X$ is bounded in $[a, b]$ (or more generally when we have a sum of independent bounded terms), Hoeffding gives an exponentially decaying bound — the real workhorse in PAC learning, bandit theory, and generalisation bounds.

Running example, single die ($n=1$). $X \in [1, 6]$, range $= 5$, $t = 6 - 3.5 = 2.5$.

Informally: "the sample mean converges to the true mean as $n \to \infty$." Formally, two flavours.

Sum many independent, small-influence random effects and the sum's distribution approaches a Gaussian — regardless of the ingredients' shape. Formally: for i.i.d. X₁…Xₙ with mean μ and variance σ²,

Worked example: roll a fair die 100 times; P(sum > 380)? Per roll: μ = 3.5, σ² = 35/12 ≈ 2.917. Sum: mean 350, variance 291.7, SD ≈ 17.08. z = (380.5 − 350)/17.08 ≈ 1.79 (with continuity correction) → P ≈ 1 − Φ(1.79) ≈ 3.7%. A die is flat as can be — yet 100 of them produce a clean bell.

• Mini-batch gradients are sample means — approximately Gaussian noise around the true gradient, with variance ∝ 1/batch size. Batch size is a noise dial; LR scaling rules are downstream of this fact.
• Eval error bars: accuracy on n examples carries SE = √(p(1−p)/n) ≈ 0.5/√n at worst — on 1,000 examples that's ±1.5%, so a 0.8% "improvement" is noise. Always report n with the metric.
• A/B tests stand entirely on CLT-normality of metric means — chapters 12–13 cash this in.

An estimator θ̂ is any function of the data X₁,…,Xₙ. The key word is function — before data arrives, θ̂ is itself a random variable (different samples → different estimates). That randomness is what bias and variance measure.

Example: you flip a coin 10 times and see 7 heads. One natural estimator of the bias p is θ̂ = 7/10 = 0.7. Another is θ̂ = (7+1)/(10+2) ≈ 0.667 (Laplace smoothing). Which is better? That depends on the loss function and the true p — which is what bias/variance/MSE formalize.

Derivation in 3 lines: Let $\mu = E[\hat\theta]$. Then $(\hat\theta - \theta) = (\hat\theta - \mu) + (\mu - \theta)$. Square and take expectation: the cross term vanishes (why? $E[\hat\theta - \mu]=0$), leaving $E[(\hat\theta-\mu)^2] + (\mu-\theta)^2 = \text{Var}(\hat\theta) + \text{Bias}^2$.

Maximum Likelihood Estimation answers: which parameter value makes the data I actually observed most probable?

Data: $n$ independent coin flips; $k$ heads. Unknown: bias $p \in [0,1]$.

Step 1 — Likelihood:

Step 2 — Log-likelihood:

Step 3 — Differentiate:

Step 4 — Solve: $k(1-p) = (n-k)p \Rightarrow k = np \Rightarrow \hat p_{\text{MLE}} = k/n$.

Sanity check: 7 heads in 10 flips → $\hat p = 0.7$. This is just the empirical frequency. MLE formalizes the obvious choice, which is reassuring.

Data: $x_1,\dots,x_n \sim \mathcal{N}(\mu, \sigma^2)$, $\sigma^2$ known. Estimate $\mu$.

Step 1 — Likelihood:

Step 2 — Log-likelihood:

Steps 3–4 — Differentiate and solve:

Key insight: "maximize Gaussian likelihood" and "minimize sum of squared residuals" are the same problem. This is how Gaussian noise assumptions sneak into every regression.

The Fisher information measures how sharply the likelihood peaks around the true $\theta$ — how much information a single observation carries about $\theta$.

Plain words: if observing $X$ barely changes how you think about $\theta$ (flat likelihood), information is low. If the likelihood is sharply peaked, every observation is highly informative.

MLE ignores everything you knew before seeing the data. MAP (Maximum A Posteriori) incorporates a prior belief $p(\theta)$ and maximizes the posterior:

Suppose you believe the coin is roughly fair before seeing any data. Encode this as a Beta(α, β) prior on $p$.

Prior: $p(\theta) \propto \theta^{\alpha-1}(1-\theta)^{\beta-1}$. With $\alpha=\beta=2$: mild preference for fairness.

Data: $k$ heads in $n$ flips. Likelihood: $\theta^k(1-\theta)^{n-k}$.

Posterior (by Bayes):

MAP estimate: the mode of Beta$(k+\alpha, n-k+\beta)$ is:

Numeric example: $n=10$, $k=1$, prior $\alpha=\beta=2$. MLE: $1/10 = 0.10$. MAP: $2/12 \approx 0.167$. The prior pulls toward 0.5 — sensible when data is scarce.

As data grows: with $n=1000$, $k=100$: MAP $= 101/1002 \approx 0.1008$, MLE $= 0.100$. The two pseudo-counts become negligible; MAP → MLE.

Pseudo-count interpretation: $\alpha-1$ is your "imaginary" prior heads, $\beta-1$ your prior tails. Beta(2,2) is like having seen one head and one tail before any real data.

Suppose you want to estimate a population mean $\mu$. You collect a sample, run a formula, and output an interval $[L, U]$. You call it a "95% confidence interval." What does that guarantee?

The correct statement: The procedure that generated $[L, U]$ is designed so that, if you repeated the entire experiment many times — drawing new samples, computing new intervals each time — 95% of those intervals would contain the true $\mu$.

The interval in your hands is fixed. Either $\mu$ is inside it (probability 1) or it is not (probability 0). You do not know which. The 95% is a property of the procedure, not of this particular interval.

Start from the CLT: for i.i.d. data with mean $\mu$ and variance $\sigma^2$, the standardized sample mean converges in distribution to standard normal:

Step 1: For large $n$, $P(-1.96 \leq Z \leq 1.96) \approx 0.95$ (standard normal table: 1.96 cuts off 2.5% each tail).

Step 2: Substitute $Z$ and rearrange:

Result: the 95% z-interval is $\bar x \pm 1.96\,\hat\sigma/\sqrt{n}$, where $\hat\sigma$ estimates $\sigma$ from the data.

Numeric example: 100 users, sample mean session time = 4.2 min, sample std dev = 2.0 min. 95% CI: $4.2 \pm 1.96 \cdot (2.0/\sqrt{100}) = 4.2 \pm 0.39 = [3.81, 4.59]$ minutes.

What moves the width: half-width $= z^* \cdot \sigma/\sqrt{n}$. To halve the CI width, you need $4\times$ the sample size. To target a specific width $w$: $n = (2z^*\sigma/w)^2$.

In practice, $\sigma$ is unknown and is replaced by the sample std dev $s$. When $n$ is large, $s \approx \sigma$ and the z-interval works fine. When $n$ is small, the estimation error in $s$ adds extra uncertainty — the t-distribution captures this.

Rule of thumb: use the t-distribution whenever $n < 30$ and the data are reasonably close to normal. For skewed distributions, bootstrap (below) is safer than t for small $n$.

For a proportion $p$ (e.g., click-through rate), the natural CI is the Wald interval: $\hat p \pm z\sqrt{\hat p(1-\hat p)/n}$. This works fine for moderate $p$ and large $n$, but it has a known failure mode:

Wilson interval (the fix): invert the score test rather than the Wald test. The formula:

In practice: for $\hat p \in [0.1, 0.9]$ and $n \geq 30$, Wald is fine. Use Wilson whenever $n\hat p < 5$ or $n(1-\hat p) < 5$ — i.e., you have few successes or few failures. In A/B testing on low-volume pages (e.g., 2% CTR, $n=100$), always use Wilson.

The CLT-based z-interval requires knowing (or approximating) the distribution of $\hat\theta$. For the mean, the CLT does this. For a median, a ratio, or an AUC, the sampling distribution is complicated. The bootstrap sidesteps this by treating your sample as a proxy for the population and resampling from it.

Core idea: you have one sample of size $n$. You cannot afford another experiment. But you can simulate the experiment by drawing $n$ observations with replacement from your existing sample. Each bootstrap resample is a plausible dataset you might have gotten; computing $\hat\theta$ on each gives you a simulated sampling distribution of $\hat\theta$.

import numpy as np

def bootstrap_ci(data, stat_fn, B=5000, alpha=0.05):
    n = len(data)
    boot_stats = []
    for _ in range(B):
        resample = np.random.choice(data, size=n, replace=True)
        boot_stats.append(stat_fn(resample))
    lower = np.percentile(boot_stats, 100 * alpha / 2)
    upper = np.percentile(boot_stats, 100 * (1 - alpha / 2))
    return lower, upper

# Example: CI for the median
data = np.array([2.3, 1.1, 5.7, 3.2, 4.8, 2.9, 6.1, 1.8])
lo, hi = bootstrap_ci(data, np.median)
print(f"95% bootstrap CI for median: ({lo:.2f}, {hi:.2f})")

Every hypothesis test runs the same four-step program. (1) Assume a boring world — the null hypothesis $H_0$ ("the coin is fair", "the new model is no better"). (2) Pick a test statistic that measures discrepancy from that boring world. (3) Compute how surprising your observed statistic would be if the boring world were true — that probability of surprise is the p-value. (4) If the data is too surprising (p below a pre-chosen threshold $\alpha$), reject $H_0$ in favor of the alternative $H_1$. It's proof by contradiction with probability instead of certainty: we never prove $H_1$; we show $H_0$ strains to explain the data.

The court-trial analogy maps every piece:

The asymmetry is deliberate: $H_0$ gets the benefit of the doubt because false discoveries are expensive. That's also why "fail to reject" is the correct verdict language — a not-guilty verdict doesn't mean the defendant was proven innocent.

Tiny example: you suspect a coin favors heads, flip it 100 times, and see 60 heads. Under $H_0$ (fair coin), heads count is roughly $\mathcal{N}(50, 25)$, so $z = (60-50)/5 = 2.0$. One-sided p-value: $P(Z \ge 2.0) \approx 0.023$. Reading: if the coin were fair, only about 2.3% of experiments would show 60 or more heads. At $\alpha = 0.05$ we reject fairness. Note what we did not compute: the probability that the coin is fair.

Two ways to be wrong: convict the innocent (Type I, probability α — reject a true H0) and acquit the guilty (Type II, probability β — miss a real effect). Power = 1 − β is the probability you detect an effect that's really there.

Underpowered studies are double poison: they miss real effects, AND the effects they do "find" are exaggerated (only lucky overestimates cross the bar — the winner's curse).

Run 20 independent tests at α = .05 on true nulls: P(at least one false positive) = 1 − 0.95²⁰ ≈ 64%, and you EXPECT one "discovery." Segments × metrics × weekly looks multiply into dozens of tests without anyone deciding to test anything.

Rule: FWER (Bonferroni) when a single false claim is expensive; FDR (BH) when you're screening many leads for follow-up.

The OEC (Overall Evaluation Criterion) is the single metric the test is allowed to move and the one your ship/no-ship decision keys on. Choosing it after seeing results is the original sin of experimentation — with 20 metrics on a dashboard, one will be "significant" at α=0.05 by luck alone (Chapter 12's multiple-testing arithmetic, now with a shipping decision attached).

A good OEC is (a) sensitive enough to move in a 2-week window, (b) causally close to the change, and (c) aligned with long-term value. Revenue is aligned but noisy and slow; click-through rate is sensitive but gameable (clickbait raises CTR while destroying trust). Running example for this chapter: a new ranking model for a feed, OEC = session click-through rate proxy: fraction of users who click at least one recommended item, baseline 5.0%.

Guardrails are metrics that must NOT regress: latency (p95), crash rate, unsubscribe rate, ad revenue. They get tested too — usually as non-inferiority checks ("rule out a drop bigger than 1%") rather than "detect any improvement." A test that wins the OEC but trips a guardrail does not ship.

The randomization unit is the thing you flip the coin for. Two common choices:

The deeper assumption behind any unit choice is SUTVA — no interference: my treatment assignment doesn't change your outcome. Feeds with social sharing, marketplaces, and ride-sharing all violate it (treatment users buying up inventory makes control look worse, inflating the measured effect). We return to this at the end with cluster randomization.

Plain words first: the smaller the effect you want to detect, the more users you need, because you must shrink the noise (standard error ∝ $1/\sqrt{n}$) until the effect stands out from it. The MDE (minimum detectable effect) is the smallest lift you'd care about shipping — a product decision, not a statistics one. Ours: baseline conversion $p_1 = 5.0\%$, MDE = 0.2 percentage points (so $p_2 = 5.2\%$, a 4% relative lift), two-sided $\alpha = 0.05$, power $1-\beta = 80\%$.

Plug in, step by step:

1. $(z_{\alpha/2}+z_{\beta})^2 = (1.96+0.84)^2 = 2.8^2 = 7.84$
2. $p_1(1-p_1) = 0.05 \times 0.95 = 0.0475$;   $p_2(1-p_2) = 0.052\times 0.948 = 0.0493$; sum $= 0.0968$
3. $(p_2-p_1)^2 = (0.002)^2 = 4\times 10^{-6}$
4. $n = \dfrac{7.84 \times 0.0968}{4\times 10^{-6}} \approx \dfrac{0.7589}{0.000004} \approx 189{,}700$ per arm → round up: ≈190,000 per arm, ≈380,000 users total.

Sanity-check the size: detecting a 0.2pp move on a 5% base rate is hunting a 4% relative change in a coin that comes up heads 1 time in 20 — of course it takes ~400k flips. If the site randomizes ~40,000 eligible users/day at full allocation, that's ~10 days of traffic; run 14 days anyway to cover two full weekly cycles (weekend users behave differently than weekday users).

Run: hash user IDs (with an experiment-specific salt — reusing one hash across experiments correlates assignments) into 50/50 arms; before unblinding the OEC, run an SRM check (sample-ratio mismatch): a chi-square test that the realized split is actually 50/50. Getting 189,000 vs 191,000 when you expected equal arms is a red flag for broken assignment or differential logging loss — the most common silent killer of real experiments. SRM fails → throw the test away, no exceptions.

Analyze: after 14 days, control: 9,500 conversions / 190,000 ($\hat p_C = 5.00\%$); treatment: 9,956 / 190,000 ($\hat p_T = 5.24\%$). Two-proportion z-test (Chapter 12):

Decide: report effect size with uncertainty, never p alone: lift = +0.24pp, 95% CI [+0.10pp, +0.38pp] ($0.0024 \pm 1.96\times 0.000715$), p ≈ 0.0008. The CI sits entirely above zero and its lower end (+0.10pp) — check it against the MDE bar and launch cost. Guardrails clean, SRM clean → ship. Note the honest caveat: the CI is wide relative to the point estimate; the true lift could plausibly be half or 1.5× what we measured.

The α=0.05 guarantee is for one look at the data. Peek daily and decide "stop, it's significant!" whenever $|z|>1.96$, and you are running many correlated tests, taking the maximum excursion of the z-statistic over time. Under $H_0$ the cumulative z wanders like a random walk around 0 — give it 10 chances to touch ±1.96 and it will, far more than 5% of the time. Simulation: checking 10 times during a null experiment and stopping at the first "significant" result yields a false-positive rate of ≈19%, not 5%. Peek continuously forever and the random walk crosses any fixed bar with probability → 1: every flat null "wins" eventually.

The asymmetry that makes peeking poisonous: a true effect crossed-then-uncrossed still ends significant at day 14, but a null that grazes the line gets frozen as a win the moment you stop. Stopping rules harvest noise. Fixes, in order of practicality:

• Don't peek — fix the horizon at design time, look once. Simple, valid, what most teams should do.
• Alpha-spending / group-sequential tests (O'Brien–Fleming, Pocock): pre-plan K looks and spend the 5% budget across them with wider early bars (e.g., first look needs |z| > 4, final look ≈ 2.0). Early stopping for huge wins/harms stays legal.
• Always-valid inference (mSPRT / confidence sequences, the "anytime-valid" machinery behind Optimizely-style dashboards): intervals that hold simultaneously over all times, so you may stop whenever you like — at the price of wider intervals.

HARKing on 20 metrics. The flat-OEC test where "engagement among Android users aged 25–34 is up, p=0.03!" With 20 metrics × a handful of segments, dozens of tests run implicitly; at α=0.05 you expect spurious wins (Chapter 12). Rule: one pre-registered OEC decides; secondary metrics and segments generate hypotheses for the next test, or must survive an FDR correction.

Simpson's paradox. Segment readouts can tell the exact opposite story from the aggregate when arm composition differs across segments. Concrete table — treatment loses in every segment yet wins overall:

Treatment is worse on mobile (8.5% < 9.0%) and worse on desktop (3.8% < 4.0%), yet "wins" overall (8.03% > 4.5%) — purely because the treatment arm is 90% mobile (the high-CTR segment) while control is 90% desktop. Nothing here is a math error; the aggregate is confounded by segment mix. In a properly randomized test both arms get the same mix, so this table is itself diagnostic: composition this lopsided means broken randomization (and the SRM check per segment would have caught it — e.g., a staged rollout that ramped treatment on mobile first).

Novelty and primacy effects. A shiny new button gets clicked because it's new (novelty: effect decays); a redesigned flow looks bad because users must relearn it (primacy: effect grows). Both make week-1 results lie about steady state. Diagnose by plotting the treatment effect by day or by user-exposure cohort: a real effect is flat, novelty slopes down, primacy slopes up. Mitigations: run ≥2 weeks, weight later days, or analyze only users past their first few exposures.

The debate often generates more heat than light. Here is what actually differs:

A conjugate prior is a prior whose functional form is preserved under the likelihood — the posterior belongs to the same family. This turns inference into simple parameter arithmetic.

Setup. We are estimating the bias θ of a coin. We choose a Beta prior because it lives on [0,1] and has a natural pseudo-count interpretation:

Choosing the prior. We start with Beta(2,2) — weakly centered on 0.5, expressing mild belief the coin is fair. The mean is 2/(2+2) = 0.5. This is equivalent to having seen 1 imaginary head and 1 imaginary tail (the shape α−1 = 1, β−1 = 1).

Observing data. We flip the coin 10 times and see 7 heads, 3 tails. The likelihood of this data given θ is Binomial:

Updating (Bayes' rule). Multiply prior by likelihood:

What changed? The posterior mean is 9/(9+5) = 0.643. The prior mean was 0.5; the MLE would be 7/10 = 0.7. The posterior sits between them, pulled toward the MLE by data but tempered by the prior. With only 10 flips, the prior still matters.

The conjugate update rule says: posterior parameters = prior parameters + data counts. This gives a clean mental model called pseudo-counts:

This is why regularization and Bayesian priors are the same thing in different clothes: L2 regularization on logistic regression is exactly MAP inference under a Gaussian prior; a Beta(α,β) prior on a Bernoulli rate is exactly adding α+β−2 pseudo-observations.

Classical A/B testing answers: "Is the difference statistically significant?" Bayesian A/B testing answers: "What is the probability that B is better than A, and by how much?"

Setup. Variant A has prior Beta(α_A, β_A) and observes n_A conversions from N_A trials. Variant B similarly. After observing data:

Concrete example. Start both arms at Beta(1,1). After the experiment, A has 40 conversions / 200 trials (posterior Beta(41,161)), B has 52 / 200 (posterior Beta(53,149)). Sample 100k draws from each posterior; compute the fraction of times θ_B > θ_A. If that fraction is 0.97, you say: "There is a 97% posterior probability that B's true rate exceeds A's."

Choosing between arms (ads, headlines, ranking tweaks): sample each arm's conversion rate from its posterior, play the arm whose SAMPLE wins, update. Uncertain arms get explored exactly in proportion to their probability of being best — exploration falls out of Bayes for free.

« 8 lines, the whole algorithm »
alpha = [1, 1]; beta = [1, 1]          # Beta(1,1) priors per arm
for t in range(100000):
    theta = [random.betavariate(alpha[k], beta[k]) for k in (0, 1)]
    k = 0 if theta[0] > theta[1] else 1   # play the sampled best
    reward = pull(k)                       # 0 or 1
    alpha[k] += reward
    beta[k]  += 1 - reward

Production cameos: ad/creative selection, artwork choice, explore slots in recommenders. Strengths: no peeking problem, automatically tapers exploration. Caveats: delayed/batched rewards need care, and nonstationary rates need discounting or sliding windows.

Early-season: one player bats 9/20 (.450), another 60/200 (.300). Best guess at true skill? NOT the raw averages — small samples scatter wildly around true skill (chapter 8's law of total variance). Fit a prior from ALL players (league skill ≈ Beta centered ~.27), then each player's posterior mean = weighted blend of their data and the league prior, weights ∝ sample size. The 9/20 hitter shrinks hard toward .27; the 60/200 hitter barely moves. Stein's lesson: shrinking EVERYONE toward the center beats trusting each raw average — uniformly.

Recsys cash-out: item CTR = (clicks + α)/(impressions + α + β) with α, β fit from the catalog — exactly this machinery; "smoothed CTR" is empirical Bayes wearing a production name.

Memorising 30 individual puzzles is fragile — a slight rewordering breaks recall. Internalising 7 patterns is robust: a new costume on a familiar skeleton is immediately recognisable. The workflow is always the same:

1. Classify — which pattern does this smell like?
2. State the 30-second answer — headline number or formula, out loud, immediately.
3. Show the reasoning — derive it cleanly; the interviewer is watching your process.
4. Sanity-check — plug in extreme values; does the answer make sense at the limits?

When the problem has a uniform exchangeability structure — every seat, card, or person is interchangeable — you can skip counting and appeal directly to symmetry. The probability that some specific element lands in a particular slot equals 1/(number of slots).

30-second answer: The last passenger sits in their own seat with probability 1/2.

Setup. 100 passengers, 100 seats. Passenger 1 picks a random seat (theirs or someone else's). Each subsequent passenger sits in their assigned seat if it is free, otherwise picks randomly among the remaining seats. What is the probability passenger 100 ends up in seat 100?

Deeper reasoning. The key insight: the process ends the first time either seat 1 or seat 100 is chosen at random. By symmetry, these two outcomes are equally likely whenever a random choice occurs, regardless of how many other passengers have sat down. Therefore P(passenger 100 gets seat 100) = 1/2.

Formal proof by induction (give if pushed). Let $p_n$ = probability the last passenger gets their seat with $n$ passengers. For $n=2$: passenger 1 picks randomly, P = 1/2. For $n>2$: passenger 1 picks seat 1 (prob 1/n, last gets their seat), seat n (prob 1/n, last does NOT), or seat $k$ for $2 \le k \le n-1$ (prob $(n-2)/n$, reduces to subproblem of size $n-k+1$, which by induction also gives 1/2). So $p_n = 1/n + 0 + \tfrac{n-2}{n}\cdot\tfrac{1}{2} = \tfrac{1}{2}$ for all $n \ge 2$.

Sanity check. $n=2$: passenger 1 picks randomly, so P = 1/2. ✓

30-second answer: The expected number of cards you flip before seeing the first ace is 48/5 = 9.6.

Setup. A standard 52-card deck is shuffled uniformly at random. You flip cards one by one. How many non-ace cards appear before the first ace?

Symmetry argument. Think of the 52 cards as 4 aces and 48 non-aces. Consider the 5 "gaps" formed by the 4 aces in a random arrangement: the gap before the first ace, the gaps between consecutive aces, and the gap after the last ace. By symmetry, each of the 48 non-aces is equally likely to fall in any of the 5 gaps. So the expected number before the first ace is 48/5.

Alternative — indicator method. For each non-ace card $i$, let $I_i = 1$ if card $i$ appears before all 4 aces. Among card $i$ and the 4 aces (5 cards total), by symmetry $P(I_i=1)=1/5$. By linearity:

When the process is sequential and random, condition on what happens at time 1 and write a recursion. This turns a hard global question into a tractable local one. Most "how many flips/steps until…" questions live here.

30-second answer: HH takes 6 flips; HT takes 4 flips. They differ because HH has an "overlap" that resets progress.

Why they differ — the overlap insight. After seeing H, a T in the HT case completes the target. A T in the HH case doesn't waste the H — wait, it does: you need HH so a T resets to the start. But a second H completes. For HH: after seeing H and then H, you're done; but after seeing H and then T, you're fully back to start (no overlap). For HT: after seeing H and then H, you're still in state "last flip was H" — the new H is potentially the start of HT. So HT has an overlap that HH lacks, making HT easier to achieve.

HT — 3-state solution. States: $S_0$ = start, $S_H$ = last flip was H, $S_{HT}$ = done.

• From $S_0$: flip H (prob 1/2) → $S_H$; flip T (prob 1/2) → $S_0$. So $E_0 = 1 + \tfrac{1}{2}E_H + \tfrac{1}{2}E_0$.
• From $S_H$: flip T (prob 1/2) → done; flip H (prob 1/2) → $S_H$. So $E_H = 1 + \tfrac{1}{2}\cdot 0 + \tfrac{1}{2}E_H$.

Solving: $E_H = 2$; $E_0 = 1 + \tfrac{1}{2}\cdot 2 + \tfrac{1}{2}E_0 \Rightarrow E_0 = 4$.

HH — 3-state solution. States: $S_0$ = start, $S_H$ = last flip was H, $S_{HH}$ = done.

• From $S_0$: flip H → $S_H$; flip T → $S_0$. So $E_0 = 1 + \tfrac{1}{2}E_H + \tfrac{1}{2}E_0$.
• From $S_H$: flip H (prob 1/2) → done; flip T (prob 1/2) → back to $S_0$ (no overlap!). So $E_H = 1 + \tfrac{1}{2}\cdot 0 + \tfrac{1}{2}E_0$.

Solving: $E_0 = 1 + \tfrac{1}{2}E_H + \tfrac{1}{2}E_0$; $E_H = 1 + \tfrac{1}{2}E_0$. Substituting: $E_H = 1 + \tfrac{1}{2}(1 + \tfrac{1}{2}E_H + \tfrac{1}{2}E_0) = \ldots$ → $E_0 = 6$.

30-second answer: Starting with $k$ dollars, playing against a casino with $N$ dollars total (fair coin), probability of ruin is $(N-k)/N$ and expected duration is $k(N-k)$.

Setup. A gambler starts with $\$k$. At each step: win $\$1$ (prob $p$) or lose $\$1$ (prob $q=1-p$). Game ends when fortune hits 0 (ruin) or $N$ (win). What is the probability of ruin?

Condition on first step. Let $r_k = P(\text{ruin} | \text{start at } k)$. Then $r_k = p \cdot r_{k+1} + q \cdot r_{k-1}$ with $r_0=1$, $r_N=0$. This is a second-order linear recurrence.

Fair game ($p = q = 1/2$). The recurrence $r_k = \tfrac{1}{2}r_{k+1} + \tfrac{1}{2}r_{k-1}$ has solutions $r_k = A + Bk$. Boundary conditions: $r_0=1 \Rightarrow A=1$; $r_N=0 \Rightarrow B = -1/N$. So:

Intuition. In a fair game, the gambler's fortune is a martingale — its expected value never changes. So $E[\text{final fortune}] = k$. With probability $r_k$ the final fortune is 0 and with probability $1-r_k$ it is $N$: so $k = 0 \cdot r_k + N(1-r_k) \Rightarrow r_k = (N-k)/N$. The martingale optional stopping theorem makes this rigorous.

Linearity of expectation holds even under dependence. Any "expected count" question can be written as a sum of indicator random variables, each with a simple probability. The indicators may be wildly dependent — it does not matter.

30-second answer: The expected number of people who get their own hat back is 1, for any $n \ge 1$.

Setup. $n$ people check their hats; a careless attendant returns them in a uniformly random order. What is the expected number of people who receive their own hat?

Indicator argument. Let $I_i = 1$ if person $i$ gets their own hat. Then $P(I_i = 1) = 1/n$ by symmetry (person $i$'s hat is equally likely to be in any of the $n$ positions). By linearity:

Bonus — the derangement connection. The probability that nobody gets their hat ($P(\text{derangement})$) converges to $1/e \approx 0.368$ as $n \to \infty$. The expected count is 1 even though most of the time the actual count is 0 or 1 — a striking illustration of how expectation and typical value can diverge.

30-second answer: In a sequence of $n$ fair coin flips, the expected number of "runs" (maximal blocks of identical values) is $\frac{n+1}{2}$.

Setup. A run is a maximal consecutive block of the same symbol. HHTTHH has 3 runs. What is the expected number of runs in $n$ i.i.d. fair flips?

Indicator argument. The first flip always starts a run. For each subsequent flip $i = 2, \ldots, n$: $I_i = 1$ if flip $i$ differs from flip $i-1$, i.e., it starts a new run. $P(I_i=1) = 1/2$. So:

Sanity check. $n=1$: 1 run. $(1+1)/2 = 1$. ✓ $n=2$: either HH, TT (1 run, prob 1/2) or HT, TH (2 runs, prob 1/2), so E = 3/2 = (2+1)/2. ✓

30-second answer: To collect all $n$ distinct coupons (one per box, uniform), expected boxes needed is $n H_n = n(1 + 1/2 + 1/3 + \cdots + 1/n) \approx n \ln n$.

Indicator argument (waiting times). Let $T_k$ = additional boxes needed to go from $k-1$ distinct coupons to $k$ distinct. When you have $k-1$ coupons, probability the next box is new is $(n-k+1)/n$. So $T_k \sim \text{Geometric}((n-k+1)/n)$ and $E[T_k] = n/(n-k+1)$.

ML cameo. Coupon collector gives the expected number of samples before you see every class at least once — relevant for class-balanced sampling and estimating coverage in large categorical spaces.

$P(\text{at least one}) = 1 - P(\text{none})$. The complement is almost always easier to compute when events are independent (none = product of individual probabilities). The birthday problem is the canonical example.

30-second answer: With 23 people, P(shared birthday) exceeds 50%. With 57 people it exceeds 99%.

Why the number surprises. It's not about finding someone who shares YOUR birthday (that needs ~183 people). It's about any pair, and pairs grow as $\binom{n}{2}$.

Exact calculation. Assume 365 equally likely birthdays. P(no shared birthday among $n$ people):

At $n=23$: this product $\approx 0.493$, so P(collision) $\approx 0.507 > 50\%$.

Quick approximation. Using $\ln(1-x) \approx -x$ for small $x$:

Interview follow-up. "How many people until P > 99%?" Same formula: $n \approx \sqrt{2 \cdot 365 \cdot \ln 100} \approx 57$.

Some puzzles are designed to trick your intuition by hiding information. The cure is mechanical: write out the sample space explicitly, apply Bayes' rule, and be precise about exactly what information was revealed and how it was revealed. Intuition is optional; the calculation is not.

30-second answer: Always switch. Switching wins with probability 2/3; staying wins with probability 1/3.

Setup. Three doors: one car, two goats. You pick door 1. Monty (who knows) opens a goat door (say door 3). Should you switch to door 2?

Posterior calculation.

Monty opened door 3 in two of the three scenarios (with equal probability conditional on each). Given Monty opened door 3: P(car at door 2 | door 3 opened) = (1/3)/(1/2) = 2/3.

The 1000-door amplifier. Still unconvinced? Imagine 1000 doors: you pick door 1 (1/1000 chance of winning). Monty opens 998 goat doors, leaving door 473. Now switch? Of course — door 473 has prob 999/1000. Monty's knowledge concentrates all the "non-1" probability into the one remaining door.

Why intuition fails. The key is that Monty's choice is not random — he has information and acts on it. This selection-bias is exactly what Bayes' rule captures.

30-second answer: The answer depends critically on how you learned the information. Two phrasings, two answers.

Version 1: "I have two children. One is a boy. What's P(both boys)?"
Sample space of two children (equally likely): BB, BG, GB, GG. Ruling out GG: {BB, BG, GB}. P(BB | at least one boy) = 1/3.

Version 2: "I have two children. The older is a boy. What's P(both boys)?"
Sample space conditioning on the older child: (older=B, younger=B) or (older=B, younger=G). P(BB | older is boy) = 1/2.

The lesson. "At least one boy" is weaker information than "the older is a boy." The first reveals a property of the pair; the second reveals a property of a specific child. Specify exactly what is revealed and how — then calculate mechanically.

30-second answer: There is no switching strategy that improves your expected payoff — the apparent "gain by switching" argument contains a hidden error.

The puzzle. Two envelopes: one has $\$X$, the other $\$2X$. You open one and see amount $m$. The other has either $2m$ or $m/2$. Seemingly: E[switch] = $\tfrac{1}{2}(2m) + \tfrac{1}{2}(m/2) = 1.25m > m$. Switch!

The error. The two cases cannot both be equally likely for every value of $m$. If $X$ has a prior distribution, P(other = 2m | saw m) ≠ 1/2 in general — it depends on the prior over $X$. For a proper (integrable) prior on $X$, the gain from switching integrates to zero. The paradox exists because you're applying an improper uniform prior over all positive reals, which isn't a valid probability distribution.

When the sample space is a geometric region (line segment, square, circle), probability = (favorable area)/(total area). Draw the region, shade the favorable set, compute the ratio.

30-second answer: Break a stick at two random points; probability the three pieces form a triangle is 1/4.

Setup. Choose two break points $X, Y$ uniformly on $[0,1]$. WLOG assume $X < Y$; the three pieces have lengths $X$, $Y-X$, $1-Y$.

Triangle inequality conditions. Three lengths form a triangle iff each is less than 1/2 (since the longest side must be less than the sum of the other two, which equals 1 minus the longest). So all three conditions reduce to: $X < 1/2$, $Y - X < 1/2$, $1 - Y < 1/2$.

Area calculation. In the full unit square (not just $X < Y$), by symmetry: P(triangle) = 1/4. The favorable region is a triangle with vertices at $(0, 1/2)$, $(1/2, 1/2)$, $(1/2, 1)$, which has area $= \tfrac{1}{2} \cdot \tfrac{1}{2} \cdot \tfrac{1}{2} = 1/8$ of the upper triangle (where $Y > X$), doubling for the full square gives 1/4.

30-second answer: Two people each arrive uniformly in $[0, 60]$ minutes and wait 15 minutes. P(they meet) = 7/16.

Setup. Let $X$ and $Y$ be arrival times, uniform on $[0, 60]$. They meet if $|X - Y| \le 15$.

Geometric solution. Total area = $60^2 = 3600$. The non-meeting region consists of two triangles where $X - Y > 15$ or $Y - X > 15$, each with legs $60 - 15 = 45$. Non-meeting area = $2 \cdot \tfrac{1}{2} \cdot 45^2 = 45^2 = 2025$. P(meet) = $(3600 - 2025)/3600 = 1575/3600 = 7/16$.

A martingale is a process whose expected future value, given the present, equals the present value. This is an enormously powerful tool: if you can identify a martingale, optional stopping gives you the expected stopping time or probability for free — without solving a recursion explicitly.

The drunkard's walk. A drunkard starts at position $k$ on a number line, steps right (+1) or left (−1) with equal probability. Absorbing barriers at 0 and $N$. The position itself is a martingale.

30-second answer: Starting at $k$, P(reach $N$ before 0) = $k/N$. Expected steps to absorption = $k(N-k)$.

Probability via martingale. $X_t$ (position) is a martingale (fair walk). By optional stopping: $E[X_\tau] = X_0 = k$. At $\tau$, $X_\tau = N$ (prob $p$) or $X_\tau = 0$ (prob $1-p$). So $Np + 0 = k \Rightarrow p = k/N$.

Expected steps via the second martingale. $M_t = X_t^2 - t$ is a martingale (each step: $E[X_{t+1}^2] = \tfrac{1}{2}(X_t+1)^2 + \tfrac{1}{2}(X_t-1)^2 = X_t^2 + 1$, so $E[M_{t+1}] = M_t$). At stopping time $\tau$: $E[X_\tau^2 - \tau] = X_0^2 - 0 = k^2$. But $E[X_\tau^2] = N^2 \cdot (k/N) + 0 \cdot (1-k/N) = kN$. Therefore $E[\tau] = kN - k^2 = k(N-k)$.

Sanity check. $k = N/2$ (starting in the middle): P(win) = 1/2 and E[$\tau$] = $(N/2)^2 = N^2/4$ — maximum expected duration at the symmetric starting point. ✓

30-second answer: Biased walk with $p \ne 1/2$; P(ruin from $k$) = $[(q/p)^k - (q/p)^N]/[1 - (q/p)^N]$ where $q = 1-p$.

Martingale for biased walk. For $p \ne 1/2$, position $X_t$ is no longer a martingale (it has drift). Instead, $M_t = (q/p)^{X_t}$ is a martingale (verify: $E[M_{t+1}|X_t] = p(q/p)^{X_t+1} + q(q/p)^{X_t-1} = (q/p)^{X_t}[p(q/p) + q(p/q)] = (q/p)^{X_t}$). By optional stopping:

Solving with $P(\text{reach }N) + P(\text{ruin}) = 1$ gives P(ruin from $k$) = $\frac{(q/p)^k - (q/p)^N}{1 - (q/p)^N}$. When $p < 1/2$ and $N \to \infty$: P(ruin) → 1 (house always wins).

Every supervised loss function is the negative log-likelihood of some noise model. Minimising loss = maximising likelihood. The table below is the Rosetta Stone; memorise it.

Adding a regulariser to the loss is identical to adding a prior and doing MAP estimation instead of MLE. The prior encodes your belief about parameter scale before seeing data.

Worked intuition. Ridge: the Gaussian prior says "weights near zero are exponentially more likely than large weights." So maximising log-prior = $-\lambda\|\theta\|^2$, which is the same as subtracting L2 penalty from the log-likelihood. As $n\to\infty$, the likelihood dominates and MAP → MLE; as $n\to 0$, MAP collapses to the prior mean (zero).

The bias-variance tradeoff in ML is exactly the bias-variance decomposition of a statistical estimator. The MSE of any estimator $\hat\theta$ decomposes as: