18.600 story sheet

Binomial pmf

P(X=k) = C(n,k) p^k q^(n-k), k = 0..n, q = 1-p

Binomial mean and variance

E = np, Var = np(1-p) = npq

Poisson(λ): story

Count of rare events; λ = average count. λ = np when approximating Binomial(n,p) with n large, p small

Poisson pmf

P(X=k) = e^(-λ) λ^k / k!, k = 0,1,2,... (factorial is k!, never λ!)

Poisson mean and variance

E = λ, Var = λ

λ for Poisson approximation of a binomial

λ = np = the MEAN. Never np(1-p)

Poisson process, rate λ, window length t

N(t) ~ Poisson(λt); disjoint windows independent; P(no event in time t) = e^(-λt)

Sum of independent Poisson(λ1) and Poisson(λ2)

Poisson(λ1 + λ2)

P(R1 = 1 | R1 + R2 = 1), independent Poissons

λ1 / (λ1 + λ2). Numerator = P(R1=1)·P(R2=0) — both factors!

Geometric(p): story

Trial number of the FIRST success

Geometric pmf

P(X=k) = q^(k-1) p, k = 1,2,3,...

Geometric mean and variance

E = 1/p, Var = (1-p)/p^2

Geometric tail and memoryless

P(X>k) = q^k; P(X > m+n | X > m) = P(X > n)

Negative binomial(r,p): story

Trial number of the r-th success

Negative binomial pmf

P(X=k) = C(k-1, r-1) p^r q^(k-r), k = r, r+1, ... (last trial pinned as success)

Negative binomial mean and variance

E = r/p, Var = r(1-p)/p^2

Negative binomial tail P(X_r > n)

= P(at most r-1 successes in n trials) = Σ_{k=0}^{r-1} C(n,k) p^k q^(n-k)

Uniform[a,b]

density 1/(b-a); E = (a+b)/2; Var = (b-a)^2/12

Bernoulli(p) / indicator

E = p, Var = p(1-p); I^2 = I

Hypergeometric: exactly k special when drawing n from N with m special

C(m,k)·C(N-m, n-k) / C(N,n) — one binomial per group

Variance definition

Var(X) = E[(X-μ)^2] = E[X^2] - (E[X])^2

Var(aX + b)

a^2 Var(X)

Var(X + Y)

Var(X) + Var(Y) ONLY if independent

Var of polynomial in X (e.g. 20X + 20X^3 with X = ±2)

Plug in the values of X, simplify first (constants drop, X^3 = cX), then a^2 Var(X). Never add variances of dependent terms

Two-point variable taking a, b with probs p, 1-p

Var = (a-b)^2 p(1-p)

Variance shortcut when the mean is round

Use deviations: average of (x - μ)^2

E[g(X)] for weird g

List values g takes, their probabilities, multiply and add

Linearity of expectation

E[X+Y] = E[X] + E[Y] ALWAYS, no independence needed

Indicator recipe step 1–3

Name events A_i, count n; find P(A_1); E[X] = n·P(A_1)

How to find P(A_1)

Fix one person/item and ask how likely its event is. m chosen of N → m/N. 2n people paired → 1/(2n-1)

How to find P(A_1 A_2)

Multiplication rule: P(A_1)·P(A_2 | A_1). Remove the first, recount: (m/N)·((m-1)/(N-1)). Never square unless independent

E[X^2] for X = count of n symmetric events

n·P(A_1) + n(n-1)·P(A_1 A_2)

Why E[X^2] = nP(A1) + n(n-1)P(A1A2)

X^2 = X + X(X-1); X(X-1) = # ordered pairs of different events that both happen

Hats: P(k specific people all get own hat), n hats

(n-k)!/n! — the rest are free, subtract nothing

Hats: expected number of matches

1

Pairing 2n people into unordered pairs

(2n)!/(2^n n!) = (2n-1)(2n-3)···3·1

P(two specific people are partners), 2n people

1/(2n-1)

Inclusion–exclusion, 2 events

P(A∪B) = P(A) + P(B) - P(AB)

Inclusion–exclusion, 3 events

singles - pairs + triple

Inclusion–exclusion, n symmetric events

C(n,1)p1 - C(n,2)p2 + C(n,3)p3 - ... (n = number of events in the union)

Why signs alternate in inclusion–exclusion

Each step fixes the overcount/undercount of the previous step

When to use 1 - P(none)

Only when "none" is easy: independent events (multiply) or a direct count

When to use inclusion–exclusion

"At least one" with dependent events (shuffling, matching, pairing) or when intersection probs / p_k are given

Conditional probability

P(A|B) = P(AB)/P(B). Check answer is between 0 and 1

Bayes

P(F|E) = P(E|F)P(F) / [P(E|F)P(F) + P(E|F^c)P(F^c)]; draw the 4-leaf tree

Independent vs disjoint

Independent: one doesn't change the other's chance, multiply. Disjoint: can't both happen, P(both) = 0

Ordered vs unordered choice

Swap the two things. Same outcome → unordered C(n,k). Different outcome → ordered

Two pair hands

C(13,2)·C(4,2)^2·44 (pairs interchangeable)

Full house hands

13·12·C(4,3)·C(4,2) (triple and pair play different roles)

Labeled groups (e.g. 5 from each of 4 years)

C(1000,5)^4 / C(4000,20) — no extra 4!

Multinomial coefficient

n!/(n1! n2! ... nr!) = ways to split n objects into labeled groups of those sizes

Stars and bars: nonnegative integers, r variables summing to n

C(n+r-1, r-1)

Stars and bars: positive integers

C(n-1, r-1)

Stars and bars: sum ≤ n

Add slack variable → C(n+r, r)

lim (1 - a/n)^(bn)

e^(-ab). Never 1

Σ_{k≥0} a^k / k!

e^a (watch disguise 1/(2^k k!) = (1/2)^k/k! → e^(1/2))

Σ_{k=0}^{n} C(n,k) a^k

(1+a)^n (watch disguise n!/(k!(n-k)!))

Coefficient of x^a y^b z^c in (x+y+z)^n

n!/(a! b! c!)

pmf × k, summed over all k

E[X]

pmf × k^2, summed over all k

E[X^2] = Var + (E[X])^2. Poisson(λ): λ + λ^2

Σ_{k≥1} k q^(k-1) p

E[Geometric] = 1/p

Binomial(n,p): story

Number of successes in n independent trials, each with success prob p