Harvard Statistics 110 Probability Notes

Statistics 110: Probability — Exam Study Notes

Course: Harvard Statistics 110: Probability (Joe Blitzstein)

Style: one complete set of study notes organized the way the course actually thinks — stories first, then formulas, then the move that solves the problem. Every numbered example is machine-verified. This is a study guide, not a lecture transcript.

Notation: P probability, S sample space, |A| size of A, nPk = n!/(n−k)!, nCk = n!/(k!(n−k)!), I(A) indicator of A, X random variable, p(X) PMF, f(X) PDF, F(X) CDF, E expectation, Var variance, Cov covariance, M(t) moment generating function, π stationary distribution. Geom(p) = trials until first success (support 1, 2, …). Expo(λ) has PDF λe^(−λx) for x>0.

---

PART 1 — PROBABILITY AND COUNTING

1.1 Sample spaces and the naive definition

A sample space S is the set of possible outcomes. An event is a subset of S. The naive definition applies only when all outcomes are equally likely:

P(A) = |A| / |S|

That is an assumption, not a theorem. A loaded die, a biased coin, or “a random integer” with no equal-weighting story all fall outside it. When it does apply, the whole problem becomes counting.

Pebble World. Put one pebble on each equally likely outcome. Probability is the fraction of pebbles in the event. Later, pebbles can have different masses — that is the general definition.

1.2 How to count

Multiply across stages. Decide whether order matters and whether replacement is allowed.

Test: if rearranging the chosen items would be a different outcome, use permutations. If not, use combinations.

Example 1.1 (committee vs lineup). 10 people, choose 3. Committee: C(10,3) = 120. President/VP/treasurer (order matters): 10P3 = 720 = 3! × 120.

Example 1.2 (stars and bars). 10 indistinguishable books onto 3 distinguishable shelves, empty shelves allowed: C(10+3−1, 10) = C(12,10) = 66.

1.3 Story proofs

A story proof counts the same set two ways. The identity is then obvious.

Vandermonde: C(m+n, k) = Σ_j C(m, j) C(n, k−j). Story: choose k people from m women and n men; the sum is over how many women you take.

Example 1.3. C(10,4) = Σ_j C(5,j)C(5,4−j) = 5+50+100+50+5 = 210. Same as 10!/(4!6!).

1.4 Axioms (the non-naive definition)

1. P(A) ≥ 0
2. P(S) = 1
3. Countable additivity: if A_i are pairwise disjoint, P(∪ A_i) = Σ P(A_i)

From these: P(∅) = 0, P(A^c) = 1 − P(A), A ⊂ B ⇒ P(A) ≤ P(B), and the inclusion–exclusion formula.

Two events: P(A ∪ B) = P(A) + P(B) − P(A ∩ B). Three events: add the singles, subtract the pairs, add the triple.

Example 1.4. P(A)=P(B)=P(C)=0.20, each pairwise intersection 0.05, triple 0.01. P(union) = 0.60 − 0.15 + 0.01 = 0.46.

1.5 Birthday problem

Assume 365 equally likely days, independent birthdays, ignore February 29. P(at least one shared birthday among n people) = 1 − 365Pn / 365^n.

Example 1.5 (verified). n = 23 → 0.5073 (just over half). n = 57 → 0.9901. The complement (all distinct) is the easy count; “at least one” almost never wants a direct union over pairs.

Trap: expected number of pairs sharing a birthday is C(n,2)/365. For n = 23 that is 253/365 ≈ 0.693, which is not the probability of at least one collision. Linearity gives the mean; it does not give the probability.

1.6 Matching problem

n letters, n envelopes, random permutation. A match is a fixed point.

• E(number of matches) = 1 for every n ≥ 1 (indicators + linearity).
• P(no matches) = sum from k=0 to n of (−1)^k / k! → e^(−1)
• P(at least one match) → 1 − 1/e ≈ 0.6321
• Number of matches → Poisson(1) as n → ∞, so P(exactly k) → e^(−1)/k!

Example 1.6 (verified). n = 10: P(at least one) ≈ 0.6321, already at the limit. n = 5: 0.6333.

1.7 Part 1 checklist

• Can say when the naive definition is legal.
• Can pick the right row of the sampling table, including stars and bars.
• Can write a one-sentence story proof.
• Use the complement for “at least one.”
• Matching: mean is 1; probability of at least one is not 1.

---

PART 2 — CONDITIONAL PROBABILITY

2.1 Definition

P(A|B) = P(A ∩ B) / P(B) when P(B) > 0. Restrict the sample space to B, then re-measure A. Conditional probabilities are still probabilities: they satisfy the axioms as functions of A, with B held fixed.

Example 2.1 (cards). Draw one card. P(King | Heart) = 1/13. P(Heart | King) = 1/4. The two conditionings are different questions.

2.2 Multiplication, Bayes, LOTP

• Multiplication: P(A ∩ B) = P(A) P(B|A) = P(B) P(A|B)
• Law of total probability (LOTP): if B_1, …, B_k partition S, then P(A) = Σ P(A|B_i) P(B_i)
• Bayes: P(B_i|A) = P(A|B_i) P(B_i) / P(A), with P(A) from LOTP

Bayes inverts a story: you know P(evidence | cause) and you want P(cause | evidence). The denominator is the law of total probability, not a new object.

Example 2.2 (screening test, verified). Prevalence 2%, sensitivity 90%, false-positive rate 5%.

• P(D ∩ +) = 0.02 × 0.90 = 0.018
• P(healthy ∩ +) = 0.98 × 0.05 = 0.049
• P(+) = 0.067
• P(D|+) = 0.018/0.067 ≈ 0.2687

Most positives are still false positives. Sensitivity is P(+|D), not P(D|+).

2.3 Independence

A and B are independent if P(A ∩ B) = P(A)P(B), equivalently P(A|B) = P(A). Information about B does not change A.

Independent ≠ mutually exclusive. If A and B are disjoint and both have positive probability, they are dependent: seeing A happen drives P(B|A) to 0.

Pairwise vs mutual. Pairwise independence of each pair does not give P(A ∩ B ∩ C) = P(A)P(B)P(C). Mutual independence is the stronger statement (every subcollection factors).

Conditional independence. A and B are conditionally independent given C if P(A ∩ B|C) = P(A|C)P(B|C). Ordinary independence does not imply conditional independence, and vice versa. A common hidden cause can make two symptoms dependent, yet independent given the cause.

2.4 Monty Hall

Three doors, one car. You pick door 1. Host, who knows where the car is, always opens a remaining goat door. You are offered a switch.

• Stay: P(win) = 1/3
• Switch: P(win) = 2/3

Story: your first pick is right with probability 1/3 and wrong with 2/3. If it was wrong, the host’s forced reveal leaves the car behind the other closed door — switching harvests that 2/3.

Trap: “the host opened a door, so two doors remain, so 50–50.” That would be correct only if the host opened a random remaining door, including possibly the car.

2.5 Simpson’s paradox

An association in the aggregate can reverse inside every subgroup.

Example 2.5 (batting averages, verified).

Player A: 4/10 = .400 in year 1, 25/100 = .250 in year 2, combined 29/110 ≈ .264 Player B: 35/100 = .350 in year 1, 2/10 = .200 in year 2, combined 37/110 ≈ .336

B has the better combined average even though A hits better in each year. The weights (at-bats) differ. That is Simpson: aggregate ≠ every slice.

2.6 First-step analysis and gambler’s ruin

Condition on the first step, then write a recurrence.

Gambler starts with i dollars, opponent has N − i, each bet the gambler wins $1 with probability p and loses $1 with probability q = 1 − p. Let p(i) = P(hit N before 0 | start at i).

• p_0 = 0, p_N = 1
• p(i) = p · p(i+1) + q · p(i−1)
• If p = 1/2: p(i) = i/N
• If p ≠ 1/2: p(i) = (1 − r^i) / (1 − r^N) with r = q/p

Example 2.6 (verified). p = 1/2, i = 20, N = 100 → p_20 = 0.20. Fair game: probability of ruin is (N − i)/N = 0.80. p = 0.4, i = 2, N = 4, r = 0.6/0.4 = 1.5 → p_2 = (1 − 1.5^2)/(1 − 1.5^4) = (1 − 2.25)/(1 − 5.0625) = 0.3077.

2.7 Part 2 checklist

• Write Bayes as “likelihood × prior / total probability.”
• Never treat P(+|D) as P(D|+).
• Independent and disjoint are opposite flavors of “can’t happen together / don’t inform each other.”
• Monty Hall: switch 2/3, because the host’s policy is information.
• Simpson: always check the weights of subgroups.
• First-step: condition, don’t invent a new sample space from scratch.

---

PART 3 — RANDOM VARIABLES

3.1 What an RV is

A random variable is a function from S to the real line. The distribution is the law of that number: P(X ∈ B) for events B.

• PMF (discrete): p(X)(x) = P(X = x), sums to 1
• CDF: F(X)(x) = P(X ≤ x), always defined, right-continuous, from 0 to 1
• Two RVs with the same CDF have the same distribution (same law), even if they are not equal as functions on S

3.2 Bernoulli and Binomial

• X ~ Bern(p): 1 with probability p, 0 with probability q = 1 − p. E(X) = p, Var(X) = p q
• X ~ Bin(n, p): number of successes in n independent Bern(p) trials
  • PMF: P(X = k) = C(n,k) p^k q^(n−k)
  • Mean np, variance npq
  • Story: sum of n i.i.d. Bernoullis

Example 3.1 (verified). 8 fair coin flips. P(exactly 3 heads) = C(8,3)/256 = 56/256 = 0.2188.

Example 3.2 (verified). n = 20, p = 0.4. P(X = 8) = C(20,8) (0.4)^8 (0.6)^(12) ≈ 0.1797. Mean 8, so this is the mode region.

3.3 Hypergeometric

Draw n times without replacement from a finite population of N items, K of which are “success” type. X = number of successes in the hand.

P(X = k) = C(K,k) C(N−K, n−k) / C(N,n), for k in the feasible range.

Mean n K/N (same as binomial with p = K/N). Variance is smaller than binomial: multiply by the finite-population factor (N − n)/(N − 1).

Example 3.3 (verified). 5-card hand, hearts (K = 13, N = 52).

• E(hearts) = 5 × 13/52 = 1.25
• P(exactly 3 hearts) = C(13,3)C(39,2)/C(52,5) = 211926 / 2598960 ≈ 0.0815
• P(exactly 2 aces) = C(4,2)C(48,3)/C(52,5) ≈ 0.0399
• P(at least one ace) = 1 − C(48,5)/C(52,5) ≈ 0.3412

Binomial vs Hypergeometric. With replacement (or a huge population) → binomial, independent trials. Without replacement from a small population → hypergeometric, dependent draws. If n ≪ N, the two PMFs sit on top of each other.

3.4 Geometric and Negative Binomial

• X ~ Geom(p): trials until first success. P(X = k) = q^(k−1) p for k = 1, 2, …; E(X) = 1/p; Var(X) = q/p^2
• Memoryless: P(X > s+t | X > s) = P(X > t)
• NB(r, p): trials until r successes. Sum of r i.i.d. Geom(p). E = r/p

(Some books count failures before the first success; that version has mean q/p and support 0, 1, 2, …. Name the support before you write the mean.)

Example 3.4 (verified). p = 0.2, trials until first success. P(X = 3) = 0.8^2 × 0.2 = 0.128. E(X) = 5. NB(3, 0.5): P(X = 5) = C(4, 2) (0.5)^5 = 6/32 = 0.1875 (two failures in the first four trials, then a success). E(X) = 6.

3.5 Poisson

X ~ Pois(λ): P(X = k) = e^(−λ) λ^k / k!. Mean = variance = λ.

Poisson paradigm. n large, p small, np → λ, trials independent or weakly dependent → Bin(n, p) ≈ Pois(λ). Rare events with a stable mean count.

Example 3.5 (verified). λ = 3: P(X = 0) = e^(−3) ≈ 0.0498; P(X = 2) = e^(−3) · 9/2 ≈ 0.2240. Bin(100, 0.03): P(X = 0) = 0.97^(100) ≈ 0.0476, next to the Poisson(3) value 0.0498. Pois(2): P(X ≤ 1) = e^(−2)(1+2) ≈ 0.406.

Connection: a Bin(n, p) given a large n looks Poisson; the sum of independent Poissons is Poisson with added rates.

3.6 Part 3 checklist

• Name the story before the PMF.
• Binomial needs independent trials; hypergeometric is the without-replacement cousin.
• Geometric starts at 1 in this course; write E = 1/p only then.
• Poisson: mean equals variance; use it for rare counts.
• CDF is defined for every RV; PMF is only for discrete.

---

PART 4 — EXPECTATION

4.1 Definition and linearity

For a discrete RV, E(X) = Σ x p(X)(x) (when the sum is absolutely convergent). Linearity:

E(aX + bY + c) = a E(X) + b E(Y) + c

No independence required. This is the most used fact in the course.

4.2 Indicators and the fundamental bridge

I(A) = 1 if A happens, 0 otherwise. Fundamental bridge: E(I(A)) = P(A).

To find a probability, find the expectation of an indicator. To find an expectation of a count, write the count as a sum of indicators and take E of each term.

Example 4.1 (matching, again). Let I(j) = 1 if letter j is in envelope j. E(I(j)) = 1/n. Number of matches X = Σ I(j), so E(X) = n · (1/n) = 1, for every n.

Example 4.2 (birthday pairs). Let I(jk) = 1 if people j and k share a birthday. E(I(jk)) = 1/365. Number of shared pairs = Σ I(jk), so E = C(n,2)/365. n = 23 → 0.693; n = 30 → 1.192. You expect about one shared pair at n = 30; the collision probability is a different object.

Example 4.3 (coupon collector). n coupon types, uniform independent draws. Time to collect all has expectation n H_n (H_n = harmonic number). n = 10 → 10 H_10 ≈ 29.29. n = 365 → 2364.6.

4.3 LOTUS

Law of the unconscious statistician: E(g(X)) = Σ g(x) p(X)(x). You do not need the PMF of g(X) first. “Unconscious” because it feels like you forgot to transform the distribution — and you are allowed to forget.

4.4 Variance

Var(X) = E(X^2) − (E(X))^2 = E( (X − E X)^2 ). Var(aX + b) = a^2 Var(X). Var(X+Y) = Var(X) + Var(Y) + 2 Cov(X,Y). Independence ⇒ the covariance term drops, but linearity of variance is not free.

For an indicator: Var(I(A)) = p(1−p).

Example 4.4. I with p = 0.3: Var = 0.21. A count of 20 independent such indicators is Bin(20, 0.3) with variance 20 × 0.21 = 4.2.

4.5 St. Petersburg paradox

A game pays $2^k if the first head occurs on toss k of a fair coin. Expected payout = Σ_k (2^k) · (1/2^k) = Σ_k 1 = ∞. A finite entry fee has infinite expected net gain, which is not how anyone plays. Expectation can be infinite; “fair price = mean” is not a moral law.

4.6 Part 4 checklist

• Linearity never needs independence.
• Counts → indicators → fundamental bridge.
• LOTUS skips the distribution of g(X).
• Variance of a sum needs covariances (or independence).
• Matching mean is 1; birthday-pair mean is C(n,2)/365.

---

PART 5 — CONTINUOUS RANDOM VARIABLES

5.1 PDFs

A continuous RV has a density f such that P(X ∈ A) = ∫ over A f(x) dx and ∫ f = 1. P(X = exact value) = 0. The CDF is F(x) = the integral of f from −∞ to x, and f = F′ at continuity points. Units: density is probability per unit of x, not a probability.

5.2 Uniform and universality

U ~ Unif(0, 1): f(u) = 1 on (0,1), E = 1/2, Var = 1/12 ≈ 0.0833. Unif(a,b) is the location-scale version: mean (a+b)/2, variance (b−a)^2/12.

Universality of the Uniform. If X has a continuous increasing CDF F, then F(X) ~ Unif(0,1). Conversely, if U ~ Unif(0,1), then F⁻¹(U) has CDF F. This is how you simulate a continuous RV from a uniform random number.

Example 5.1. Expo(λ) has F(x) = 1 − e^(−λx), so X = −log(1−U)/λ ~ Expo(λ). Equivalently −log(U)/λ.

Example 5.2 (two uniforms, verified). U, V i.i.d. Unif(0,1). E|U − V| = 1/3. (Integrate |u−v| over the unit square, or condition.)

5.3 Normal

Z ~ N(0,1) has density (1/√(2π)) e^(−z^2/2). X = μ + σZ ~ N(μ, σ^2). Standardize: Z = (X − μ)/σ.

Empirical landmarks (exact): P(|Z| < 1) ≈ 0.6827, P(|Z| < 1.96) ≈ 0.95, Φ(1) ≈ 0.8413.

Example 5.3 (verified). Fair coin, n = 100, X ~ Bin(100, 0.5), mean 50, sd 5. P(X ≥ 60) with continuity correction: z = (59.5 − 50)/5 = 1.9 → 0.0287. Without the 0.5: z = 2 → 0.0228.

5.4 Exponential

X ~ Expo(λ): f(x) = λ e^(−λx) for x > 0. CDF 1 − e^(−λx). Mean 1/λ, variance 1/λ^2. Median (log 2)/λ.

Memoryless: P(X > s+t | X > s) = P(X > t). Among continuous distributions, this characterizes the exponential. The discrete analogue is Geometric.

Example 5.4 (verified). λ = 1, P(X > 2) = e^(−2) ≈ 0.1353. Median ≈ 0.693. λ = 2, mean 0.5, P(X > 1) = e^(−2) ≈ 0.1353.

Minimum of independent Expo(λ_i) is Expo(Σ λ_i). Competing exponential clocks: the first to ring is exponential with the summed rate, and P(i wins) = λ_i / Σ λ_j.

5.5 LOTUS, continuous

E(g(X)) = ∫ g(x) f(X)(x) dx. Same skip-the-transform idea as the discrete case.

5.6 Part 5 checklist

• Density is not P(X = x).
• Simulate with F⁻¹(U).
• Standardize every Normal question.
• Memoryless: Geometric or Exponential, not Binomial or Normal.
• Min of independent expos is expo with added rates.

---

PART 6 — MOMENT GENERATING FUNCTIONS

6.1 Moments

The k-th moment is E(X^k). Mean is the first; variance is built from the first two. Skew and tails live in higher moments. A distribution can have a mean but no variance (or no mean at all: Cauchy).

6.2 Moment generating functions

M(t) = E(e^(tX)), defined in a neighborhood of 0. Then M^((k))(0) = E(X^k).

Named MGFs (memorize the easy ones):

Sums of independent RVs: M(X+Y)(t) = M(X)(t) M(Y)(t). This is why Binomial is a sum of Bernoullis (raise the Bernoulli MGF to n), and why the sum of independent Poissons is Poisson (exponents add).

Uniqueness: if two RVs have MGFs that agree in a neighborhood of 0, they have the same distribution.

Example 6.1. Sum of independent Pois(2) and Pois(3) is Pois(5), because exp(2(e^t−1)) exp(3(e^t−1)) = exp(5(e^t−1)).

6.3 Hybrid Bayes and Laplace’s rule of succession

A prior can be continuous while the likelihood is discrete (or the reverse). Write Bayes with a density in the prior and a PMF in the likelihood; the posterior is a density. This is hybrid Bayes.

Laplace’s rule of succession. Uniform prior on a coin’s p, then s heads in n flips. Predictive probability the next flip is heads: (s+1)/(n+2). After 3 heads in 3 flips: 4/5 = 0.80, not 1. After no data: 1/2.

6.4 Part 6 checklist

• MGF of an independent sum is a product.
• Read moments by differentiating at 0.
• Cauchy has no mean — do not write E of it.
• Laplace succession: (s+1)/(n+2), Uniform prior.

---

PART 7 — JOINT DISTRIBUTIONS

7.1 Joint, marginal, conditional

Discrete: p(x,y) = P(X=x, Y=y). Marginal: sum out the other variable. Conditional: p(x|y) = p(x,y) / p(y).

Continuous: same picture with a joint density f(x,y). P((X,Y) ∈ A) = ∬ over A f. Marginal density = ∫ the joint. Independence: the joint factors as a product of marginals (for all x, y).

2-D LOTUS: E(g(X,Y)) = ΣΣ g(x,y) p(x,y), or the double integral.

If X, Y independent, E(XY) = E(X)E(Y). The converse is false.

7.2 Covariance and correlation

Cov(X,Y) = E(XY) − E(X)E(Y) = E( (X−EX)(Y−EY) ). Corr(X,Y) = Cov(X,Y) / (σ(X) σ(Y)) ∈ [−1, 1].

• Cov(X,X) = Var(X)
• Cov is bilinear; Var(X+Y) = Var(X)+Var(Y)+2Cov(X,Y)
• Independent ⇒ uncorrelated. Uncorrelated ⇏ independent (unless extra structure, e.g. bivariate Normal)
• Classic counterexample: X ~ N(0,1), Y = X^2. Uncorrelated, strongly dependent

Example 7.1 (hypergeometric variance, verified). Hearts in a 5-card hand: n=5, N=52, K=13, p=1/4. Var = n p (1−p) (N−n)/(N−1) = 5·(1/4)·(3/4)·47/51 ≈ 0.864, sd ≈ 0.930. (The binomial variance 5·(1/4)·(3/4) = 0.9375 is a bit larger — without-replacement negative dependence.)

7.3 Multinomial

n independent trials, k categories with probabilities p_1, …, p_k. Counts (X_1, …, X_k) ~ Mult(n, p). Each margin is Binomial. Lumping categories yields another Multinomial (or a Binomial if you lump to two).

7.4 Chicken–egg

N ~ Pois(λ). Given N=n, each item is type A with probability p, independently. Then N_A ~ Pois(λ p), N_B ~ Pois(λ(1−p)), and N_A is independent of N_B. Poisson thinning. The name: eggs laid Poisson, each hatches with probability p.

7.5 Multivariate Normal and Cauchy

Linear images of i.i.d. standard Normals are Multivariate Normal. For MVN, uncorrelated ⇔ independent.

Cauchy: ratio of independent standard Normals; density 1/(π(1+x^2)); no mean. Sample averages of Cauchys are still Cauchy — the CLT does not apply (variance is infinite).

7.6 Part 7 checklist

• Marginalize by summing/integrating; condition by dividing.
• Independent ⇒ joint factors; E(XY)=E(X)E(Y).
• Uncorrelated is weaker than independent.
• Hypergeometric variance includes (N−n)/(N−1).
• Chicken–egg: Poisson splits into independent Poissons.

---

PART 8 — TRANSFORMATIONS

8.1 Change of variables

Y = g(X) with g smooth and monotone on the support. Then

f_Y(y) = f(X)(x) / |g′(x)|, x = g^(−1)(y)

In higher dimensions, divide by the absolute Jacobian. LogNormal: Y = e^Z for Z Normal — always positive, right-skewed, mean exp(μ + σ^2/2), not exp(μ).

8.2 Convolutions

The density of X+Y for independent continuous X, Y is the convolution (f * g)(s) = ∫ f(x) g(s−x) dx. Discrete analog: sum over x of p(X)(x) p(Y)(s−x). MGFs often beat convolution by turning sums into products.

8.3 Beta and Gamma

• Gamma(a, λ) (shape-rate): waiting time for the a-th event in a rate-λ Poisson process when a is an integer; sum of a i.i.d. Expo(λ). Mean a/λ. Expo(λ) = Gamma(1, λ).
• Beta(a, b): on (0,1). Mean a/(a+b). Uniform(0,1) = Beta(1,1). Conjugate prior for a Bernoulli p.

Example 8.1. Beta(2,3) has mean 2/5 = 0.4. Gamma(3, 1) has mean 3.

8.4 Bank–post office (Beta–Gamma)

X ~ Gamma(a, λ), Y ~ Gamma(b, λ) independent (same rate). Then:

• X + Y ~ Gamma(a+b, λ)
• X / (X+Y) ~ Beta(a, b)
• the sum is independent of the proportion

Story: two independent gamma waiting times with the same clock rate; the fraction of time spent on the first task is Beta, independent of the total wait.

8.5 Order statistics

X((1)) < ⋯ < X((n)) from i.i.d. continuous X. For Uniform(0,1), U((k)) ~ Beta(k, n−k+1). Mean k/(n+1).

Example 8.2. n = 5 i.i.d. Unif(0,1), median U((3)) ~ Beta(3,3), mean 0.5. The expected sample minimum is 1/6.

8.6 Poisson processes

Events at rate λ. N(t) ~ Pois(λ t). Interarrival times i.i.d. Expo(λ). Independent increments. Thinning (keep each point with probability p) is a Poisson process of rate λp. Superposition of independent processes adds the rates.

This is the continuous-time home of Exponential, Gamma, Poisson, and chicken–egg.

8.7 Part 8 checklist

• Change of variables: divide by |g′|.
• Gamma waits for the a-th Poisson event; Beta lives on (0,1).
• Same-rate Gammas: sum Gamma, proportion Beta, independent.
• Uniform order statistic k is Beta(k, n−k+1).
• Poisson process: counts Poisson, gaps Exponential.

---

PART 9 — CONDITIONAL EXPECTATION

9.1 Given an event vs given an RV

E(Y | A) is a number: the mean of Y restricted to A. E(Y | X) is a random variable, a function of X: on the event {X = x} it equals E(Y | X = x).

9.2 Taking out what’s known

E( h(X) Y | X ) = h(X) E(Y | X). Given X, h(X) is a constant and factors out.

9.3 Adam’s law and Eve’s law

• Adam (law of total expectation): E( E(Y|X) ) = E(Y)
• Eve (law of total variance): Var(Y) = E( Var(Y|X) ) + Var( E(Y|X) )

“Average of the inner variance, plus variance of the inner mean.” Extra uncertainty from not knowing X.

Example 9.1 (verified, random sum / Wald). N independent of i.i.d. X_i, E(X)=3, Var(X)=4, N ~ Pois(10) so E(N)=Var(N)=10. S = X_1 + ⋯ + X_N (S=0 if N=0). E(S) = E(N)E(X) = 30 Var(S) = E(N)Var(X) + Var(N)[E(X)]^2 = 10·4 + 10·9 = 130

9.4 Waiting for HT vs HH

Fair coin tosses. Pattern waiting times by first-step analysis (condition on the first tosses, keep a state for the overlap).

• E(wait for HT) = 4
• E(wait for HH) = 6

HH overlaps itself (the second H can start a new HH). HT does not: after H you either finish with T or you stay “have H.” Overlap makes you wait longer in expectation. Do not treat every two-flip pattern as equally long.

9.5 Two-envelope caution

A naive “the other envelope has 1.25x” calculation double-counts a prior. Conditional expectation has to be a function of the observed amount with a proper distribution on the pair. Paradoxes here are prior mistakes, not failures of E(Y|X).

9.6 Part 9 checklist

• E(Y|X) is a function of X, not a number.
• Adam recovers E(Y); Eve splits variance.
• Random sums: Wald for the mean; Eve for the variance.
• Pattern waiting: draw the overlap states.
• Taking out what’s known: functions of X factor given X.

---

PART 10 — INEQUALITIES AND LIMITS

10.1 Four inequalities

• Cauchy–Schwarz: |E(XY)|^2 ≤ E(X^2) E(Y^2)
• Jensen: g convex ⇒ E(g(X)) ≥ g(E(X)). (g concave: reverse.) x^2, e^x, −log are convex.
• Markov: X ≥ 0, a > 0 ⇒ P(X ≥ a) ≤ E(X)/a
• Chebyshev: P( |X − μ| ≥ c ) ≤ Var(X)/c^2 (Markov on (X−μ)^2)

Example 10.1 (verified). E(X)=4, X≥0: P(X ≥ 20) ≤ 4/20 = 0.20 (Markov). Mean 50, variance 25: P(|X−50| ≥ 10) ≤ 25/100 = 0.25 (Chebyshev). X = 1 or 3 with equal probability: E(X)=2, E(X^2)=5 ≥ (E X)^2 = 4 (Jensen for x^2).

These are bounds, often loose. Use the true distribution when you have it.

10.2 Law of large numbers vs CLT

• WLLN: X̄_n → μ in probability (typical values sit near the mean).
• CLT: √n (X̄_n − μ) / σ → N(0,1). The shape of the sampling distribution of the mean becomes Normal.

CLT needs a finite variance. Cauchy is the standard counterexample: averages stay Cauchy.

Example 10.2 (verified). i.i.d. Expo with mean 2 (so λ = 1/2, sd = 2), n = 36, X̄ = sample mean. SE = 2/√36 = 1/3. P(X̄ > 2.5): z = (2.5−2)/(1/3) = 1.5 → 0.0668.

10.3 Chi-square and t

• χ²_ν : sum of ν i.i.d. N(0,1) squares. χ²_2 = Expo(1/2).
• Student-t_ν : Z / √(V/ν) with Z ~ N(0,1) independent of V ~ χ²_ν. Heavier tails than Normal; t_∞ becomes Normal.

10.4 Part 10 checklist

• Markov needs non-negative; Chebyshev needs a variance.
• Jensen’s direction follows convexity.
• LLN is about accuracy; CLT is about shape.
• No finite variance ⇒ do not invoke the CLT.
• t has heavier tails than z for small df.

---

PART 11 — MARKOV CHAINS

11.1 Definition

{X(n)} is a Markov chain if the future depends on the past only through the present: P(X(n+1) = j | X(n) = i, history) = P(ij). The transition matrix P has rows that sum to 1.

11.2 Stationary distribution

π is stationary if π = π P (row vector) and π sums to 1. Interpretation: start from π, stay at π forever; also the long-run fraction of time in each state, when the chain converges.

Example 11.1 (two-state, verified). States 0,1. P(01) = a = 0.3 (leave 0), P(10) = b = 0.4 (leave 1). π0 = b/(a+b) = 0.4/0.7 ≈ 0.571, π1 = a/(a+b) ≈ 0.429. Check: from 0 you leave at rate 0.3, from 1 at 0.4; the stationary mass balances those flows.

If a = 0.1, b = 0.2: π0 = 2/3, π1 = 1/3.

11.3 Structure

• Irreducible: every state can reach every other.
• Period: gcd of return times. Aperiodic: that gcd is 1.
• Finite, irreducible, aperiodic ⇒ unique stationary π, and P(X(n) = j | X_0 = i) → πj regardless of i.
• Reversible / detailed balance: πi P(ij) = πj P(ji) for all i, j. Then π is automatically stationary. Birth–death chains and random walks on undirected graphs are reversible.
• Random walk on an undirected graph: πi ∝ degree(i).

11.4 PageRank

Web pages as a Markov chain: follow a random out-link, with a small teleport probability to a random page so the chain is irreducible. The stationary mass is the rank. Teleportation is the modeling move that makes “importance” well-defined on a messy graph.

11.5 MCMC, briefly

To sample from a target π that you can evaluate up to a constant, build a chain that has π as stationary (Metropolis–Hastings: propose, then accept/reject to enforce detailed balance). Run the chain, treat late visits as samples. The course’s point: stationary distributions are not only for describing a process — you can design a process to have the distribution you want.

11.6 Part 11 checklist

• Rows of P sum to 1; π is a left eigenvector with eigenvalue 1.
• Two-state formula π0 = b/(a+b).
• Irreducible + aperiodic + finite ⇒ convergence to unique π.
• Detailed balance ⇒ reversible ⇒ π P = π.
• PageRank = stationary distribution of a teleported web walk.

---

APPENDIX A — FORMULA SHEET

COUNTING
  ordered w/ replacement n^k     ordered w/o  nPk = n!/(n−k)!
  unordered w/o  nCk              stars and bars C(n+k−1, k)
  Vandermonde C(m+n,k)=Σ C(m,j)C(n,k−j)

PROBABILITY
  P(A^c)=1−P(A)     P(A∪B)=P(A)+P(B)−P(A∩B)
  P(A|B)=P(A∩B)/P(B)    Bayes P(B|A)=P(A|B)P(B)/P(A)
  independent: P(A∩B)=P(A)P(B)
  matching: E=1, P(at least one)→1−1/e
  birthday: 1 − 365Pn / 365^n     E(pairs)=C(n,2)/365

NAMED DISTRIBUTIONS (discrete)
  Bern(p): E=p, Var=pq
  Bin(n,p): C(n,k)p^k q^(n−k), E=np, Var=npq
  Hypergeo(N,K,n): C(K,k)C(N−K,n−k)/C(N,n), E=nK/N
                  Var=np(1−p)(N−n)/(N−1)
  Geom(p) trials: q^(k−1)p, E=1/p, memoryless
  NB(r,p) trials until r successes: E=r/p
  Pois(λ): e^(−λ) λ^k/k!, E=Var=λ

NAMED DISTRIBUTIONS (continuous)
  Unif(0,1): E=1/2, Var=1/12; F(X)~U(0,1) (universality)
  N(μ,σ^2): Z=(X−μ)/σ
  Expo(λ): λe^(−λx), E=1/λ, memoryless; min adds rates
  Gamma(a,λ): mean a/λ; Expo=Gamma(1,λ)
  Beta(a,b) on (0,1): mean a/(a+b)
  U((k)) ~ Beta(k, n−k+1) for i.i.d. Unif(0,1)

EXPECTATION
  linearity always     E(I(A))=P(A)
  LOTUS E(g(X))=Σ g(x)p(x) or ∫ g f
  Var(X)=E(X^2)−(EX)^2     Var(aX+b)=a^2 Var(X)
  Cov(X,Y)=E(XY)−EX EY     Corr=Cov/(σx σy)
  Eve: Var(Y)=E(Var(Y|X))+Var(E(Y|X))
  random sum: E(S)=E(N)E(X)
              Var(S)=E(N)Var(X)+Var(N)(EX)^2

MGFs
  M(t)=E(e^(tX))     independent sum → product of MGFs
  Pois exp(λ(e^t−1))    N exp(μt+σ^2 t^2/2)    Expo λ/(λ−t)

INEQUALITIES / LIMITS
  Markov P(X≥a)≤E(X)/a (X≥0)
  Chebyshev P(|X−μ|≥c)≤Var/c^2
  Jensen E(g(X))≥g(E X) for convex g
  LLN: X̄→μ     CLT: √n(X̄−μ)/σ → N(0,1)

MARKOV CHAINS
  π=πP, rows of P sum to 1
  two-state: π0=b/(a+b) if P_01=a, P_10=b
  detailed balance πi Pij = πj Pji
  graph RW: πi ∝ degree(i)

APPENDIX B — WORKED MINI-EXAM

1. 10 indistinguishable items, 3 distinguishable boxes, empties allowed. Number of ways? → C(12,10)=66
2. n=23 birthdays. P(at least one shared day) ≈ ? → 0.5073
3. Random permutation of 10 letters. E(matches)? P(at least one)≈? → 1 and 0.632
4. Prevalence 2%, sensitivity 90%, FPR 5%. P(disease|+)≈? → 0.2687
5. Monty Hall, always opens a goat. P(win by switching)? → 2/3
6. Fair gambler, i=20, N=100. P(hit 100 before 0)? → 0.20
7. 5-card hand. P(exactly 3 hearts)? → 0.0815
8. Geom(0.2), trials until first success. P(X=3) and E(X)? → 0.128 and 5
9. Pois(3) vs Bin(100, 0.03): P(0)? → 0.0498 vs 0.0476
10. n=23, E(number of birthday-sharing pairs)? → 0.693
11. U,V iid Unif(0,1). E|U−V|? → 1/3
12. n=100 fair coin, P(X≥60) with continuity correction? → ≈0.0287
13. Expo(1). P(X>2) and median? → 0.1353 and ln2≈0.693
14. Independent Pois(2)+Pois(3). Distribution? → Pois(5)
15. Laplace: 3 heads in 3 flips, P(next is heads)? → 4/5
16. Hearts in 5 cards: E and Var? → 1.25 and ≈0.864
17. Chicken–egg: N~Pois(10), p=0.3 hatch. Law of hatched count? → Pois(3), independent of unhatched Pois(7)
18. n=5 Unif(0,1). Law of the sample median? → Beta(3,3)
19. N~Pois(10), X_i mean 3 var 4 independent. E(S), Var(S)? → 30 and 130
20. Fair coin, E(wait for HT) vs E(wait for HH)? → 4 vs 6
21. Mean 50, var 25. Chebyshev bound on P(|X−50|≥10)? → 0.25
22. Expo mean 2, n=36. P(X̄>2.5) by CLT? → ≈0.0668
23. Two-state a=0.3, b=0.4. π0? → 4/7≈0.571
24. Cauchy sample mean as n grows? → still Cauchy; CLT does not apply
25. Undirected graph random walk. Stationary mass at a vertex? → proportional to degree

APPENDIX C — TRAP CHECKLIST

1. Naive definition needs equally likely outcomes. A story about bias kills it.
2. “At least one” → complement. Direct unions without inclusion–exclusion double-count.
3. Birthday probability is not E(number of pairs)/something. Mean of pairs ≠ P(collision).
4. Matching mean is 1; P(at least one match) is about 0.63, not 1.
5. P(A|B) ≠ P(B|A). Write Bayes with the total-probability denominator.
6. Independent ≠ disjoint. Disjoint positive events are dependent.
7. Pairwise independence is weaker than mutual independence.
8. Independence can fail after conditioning (Simpson, lurking groups).
9. Monty Hall is not 50–50; the host’s policy is data.
10. Binomial = with replacement / independent trials. Hypergeometric = without, finite population.
11. Geometric: say whether you count trials or failures before you write 1/p vs q/p.
12. Linearity does not need independence. Variance of a sum does.
13. LOTUS does not need the law of g(X).
14. Density is not a probability. P(X=x)=0 for continuous X.
15. Memoryless is Exponential / Geometric, not “any waiting time.”
16. Uncorrelated ⇏ independent (unless MVN, etc.).
17. Cauchy has no mean; do not take E or invoke the CLT.
18. E(Y|X) is a random variable. Adam and Eve are identities, not estimates.
19. HH vs HT: overlap changes the expectation. Patterns are not exchangeable.
20. Markov / Chebyshev are upper bounds, often far from the truth.
21. Stationary π is a left eigenvector: πP=π, not Pπ=π unless you use columns.
22. PageRank without teleportation can fail on dangling or disconnected graphs.