Probability

From basic event probabilities through expectation and variance to concentration inequalities.

Probability Basics

Probability Basics — Sample space , event A ⊆ , measure P(A) ∈ [0, 1].
Random Variables — A random variable is a number-valued function of the outcome — the language of expectation.
Conditional Probability — P(A | B) = P(A ∩ B) / P(B) — count, divide, divide.
Markov Chains — Memoryless hops between states, and the distribution they settle into.
Independence — P(A ∩ B) = P(A) P(B) — the multiplication rule.
Expected Value — E[X] = _x x · P(X = x) — value-weighted average.
Linearity of Expectation — E[aX + bY] = a E[X] + b E[Y] — no independence needed.
Variance — Var(X) = E[X^2] - E[X]^2.
Law of Total Probability — P(A) = _i P(A | B_i) P(B_i) — condition and weight.

Bayes' Theorem — P(A | B) = P(B | A) P(A)/P(B) — flip conditionals.
Law of Large Numbers — Sample averages converge to the true mean: X_n → .
Monty Hall — Switch your door — P doubles. The reveal is informative, not symmetric.
Secretary Problem — Reject the first n/e, then take the next record — wins with probability 1/e.

Markov's Inequality — P(X ≥ a) ≤ E[X]/a for X ≥ 0 — the simplest tail bound.
Chebyshev's Inequality (Prob.) — P(|X - | ≥ k ) ≤ 1/k^2 — Markov's variance-flavored sibling.
Chernoff Bound — Exponentially tight tails for sums of independent bounded RVs.
Hoeffding's Inequality — Sub-Gaussian tails for sums of independent bounded RVs — no variance needed.
Wald's Identity — E[ _i=1^N X_i] = E[N] · E[X_1] for stopping times N.
Azuma-Hoeffding — Hoeffding for martingales — concentration without independence.
McDiarmid's Inequality — Bounded differences give concentration. The workhorse of combinatorial probability.

Central Limit Theorem — Standardized sums of independent terms approach a normal, whatever their shape.
Binomial Distribution — Successes in n independent trials: the PMF, probabilities, and the mean.
Normal Distribution — Standardize to Z, then read probabilities from .
Poisson Distribution — Rare-event counts: the pmf, mean and variance λ, and the binomial limit.
Geometric Distribution — Waiting time to the first success: mass function, survival, and mean.
Exponential Distribution — Continuous waiting times: tail, mean, and memorylessness.
Covariance & Correlation — Joint variation, its sign, and the unit-free correlation in [-1, 1].
Joint & Marginal Distributions — Joint pmf tables, marginals by summing, and the independence test.
Conditional Expectation — Condition on Y, then average back with the tower law.