🎲 Distributions

Almost every interview question starts by recognizing which distribution is hiding in the story. Learn the six below as stories, not formulas, and the formulas follow.

The big picture

Four of the six distributions fit a 2×2 grid. Ask two questions: am I counting events or waiting for one? And is time discrete (trials) or continuous?

	discrete (trials)	continuous (time)
counting	Binomial: how many successes in $n$ trials?	Poisson: how many events in a fixed window?
waiting	Geometric: how many trials until the first success?	Exponential: how long until the first event?

Discrete distributions

Bernoulli: one coin flip

$X \sim \Bern(p)$ is a single trial that succeeds ($X=1$) with probability $p$ and fails ($X=0$) otherwise.

$$P(X=1)=p,\qquad P(X=0)=1-p \qquad\Longleftrightarrow\qquad P(X=x)=p^x(1-p)^{1-x}$$

The compact form on the right just "selects" $p$ when $x=1$ and $1-p$ when $x=0$. It is useful when you need to multiply many of these together, as in MLE.

Proof

$\E[X]=1\cdot p+0\cdot(1-p)=p$. Since $X\in\{0,1\}$, we have $X^2=X$, so $\E[X^2]=p$.

$$\Var(X)=\E[X^2]-\E[X]^2=p-p^2=p(1-p).$$

The categorical distribution generalizes Bernoulli from 2 outcomes to $k$: $P(X=i)=p_i$. Each indicator $\1[X=i]$ is $\Bern(p_i)$, so it has mean $p_i$ and variance $p_i(1-p_i)$.

Binomial: count successes in $n$ flips

$X\sim\Bin(n,p)$ counts the successes in $n$ independent $\Bern(p)$ trials, so $X=X_1+\dots+X_n$.

$$P(X=k)=\binom nk p^k(1-p)^{n-k}$$

Read it as (number of sequences with exactly $k$ successes) × (probability of any one such sequence). Every such sequence has the same probability $p^k(1-p)^{n-k}$, and there are $\binom nk$ of them.

Proof: decompose into Bernoullis

Linearity of expectation (no independence needed): $\E[X]=\sum_i\E[X_i]=np$.

Variance adds because the $X_i$ are independent: $\Var(X)=\sum_i\Var(X_i)=np(1-p)$.

Sanity check that the PMF sums to 1, via the binomial theorem $(a+b)^n=\sum_k\binom nk a^kb^{n-k}$:

$$\sum_{k=0}^n\binom nk p^k(1-p)^{n-k}=(p+(1-p))^n=1.$$

Poisson: count rare events in a window

$X\sim\Pois(\lambda)$ counts events in a fixed window when events happen independently at an average rate of $\lambda$ per window. Examples: emails per hour, typos per page, decays per second.

$$P(X=k)=\frac{\lambda^k e^{-\lambda}}{k!}$$

Over a window of length $t$, the count is $N(t)\sim\Pois(\lambda t)$.

Where it comes from. Chop the window into $n$ tiny slots, each so small that at most one event fits. Each slot has an event with probability $p=\lambda/n$, so the total is $\Bin(n,\lambda/n)$. Now let $n\to\infty$:

Derivation of the limit

$$\begin{aligned} P(X=k) &=\binom nk \Big(\frac\lambda n\Big)^k\Big(1-\frac\lambda n\Big)^{n-k}\\ &=\frac{\lambda^k}{k!}\cdot\underbrace{\frac{n!}{(n-k)!\,n^k}}_{\to 1}\cdot\underbrace{\Big(1-\frac\lambda n\Big)^n}_{\to e^{-\lambda}}\cdot\underbrace{\Big(1-\frac\lambda n\Big)^{-k}}_{\to 1}\;\longrightarrow\;\frac{\lambda^ke^{-\lambda}}{k!} \end{aligned}$$

The original notes wrote $(\lambda/n)^n$ in the second line. It should be $(\lambda/n)^k$, since that is where the $\lambda^k$ comes from.

Mean = variance is the Poisson's fingerprint. If count data has variance much bigger than its mean ("overdispersion"), it isn't Poisson. Additivity is intuitive: merge two independent streams of events and the rates add. You can prove it with MGFs.

Geometric: trials until the first success

$X\sim\Geom(p)$ is the number of trials up to and including the first success.

$$P(X=k)=(1-p)^{k-1}p \qquad\qquad P(X>k)=(1-p)^k$$

The PMF reads "$k-1$ failures, then a success." The tail is even simpler: $X>k$ just means the first $k$ trials all failed.

Proof of $\E[X]=1/p$ by first-step analysis (the interview way)

Look at the first trial. With probability $p$ you are done after 1 trial. With probability $1-p$ you have used 1 trial and are back where you started:

$$\E[X]=p\cdot 1+(1-p)\,(1+\E[X]) \;\Rightarrow\; p\,\E[X]=1 \;\Rightarrow\; \E[X]=\frac1p.$$

This "express the answer in terms of itself" move is the most useful trick in this whole set of notes. See first-step analysis.

Sanity check: the PMF sums to 1 (geometric series)

The geometric series is $\sum_{i=0}^\infty r^i=\frac{1}{1-r}$ for $|r|<1$. Re-index with $i=k-1$:

$$\sum_{k=1}^\infty(1-p)^{k-1}p=p\sum_{i=0}^\infty(1-p)^i=p\cdot\frac{1}{1-(1-p)}=1.$$

Memory check from the original: with $r=\tfrac12$ (not $r=2$), $1+\tfrac12+\tfrac14+\dots=2=\frac{1}{1-1/2}$. ✓

Memoryless property. $P(X>m+n\mid X>m)=P(X>n)$. Having already failed $m$ times tells you nothing: the coin has no memory. The geometric is the only memoryless distribution on the positive integers.

Continuous distributions

Uniform: equally likely anywhere

$X\sim\Unif(a,b)$ is equally likely to land anywhere in $[a,b]$.

$$f(x)=\frac1{b-a}\ \ (a\le x\le b) \qquad\qquad F(x)=\begin{cases}0 & xb\end{cases}$$

Mean

$\dfrac{a+b}2$ (the midpoint)

Variance

$\dfrac{(b-a)^2}{12}$

Proofs

$$\E[X]=\int_a^b\frac{x}{b-a}\,dx=\frac{b^2-a^2}{2(b-a)}=\frac{a+b}2$$ $$\E[X^2]=\int_a^b\frac{x^2}{b-a}\,dx=\frac{a^2+ab+b^2}{3}\;\Rightarrow\;\Var(X)=\frac{a^2+ab+b^2}{3}-\frac{(a+b)^2}{4}=\frac{(b-a)^2}{12}$$

Two facts that show up in puzzles:

• The difference of two independent uniforms is triangular. For $U_1-U_2$ on $[-1,1]$, values near 0 can be made in many ways, while values near ±1 need both draws to be extreme. Try it below.
• $n$ uniform points cut $[0,1]$ into $n+1$ gaps that all have the same distribution, so each gap has mean $\frac1{n+1}$. This gives $\E[\max]=\frac n{n+1}$ and $\E[\min]=\frac1{n+1}$ instantly (more here).

Sums and differences of uniforms

This is a histogram of 20,000 draws of the chosen combination. Adding a few uniforms already looks Gaussian, which previews the CLT.

Exponential: waiting time in continuous time

$X\sim\Exp(\lambda)$ is the waiting time until the next event when events occur at rate $\lambda$ per unit time. Equivalently, it is the time to the first event of a Poisson process.

$$f(x)=\lambda e^{-\lambda x}\ (x\ge0)\qquad\qquad P(X>x)=e^{-\lambda x}\ \ \text{(survival function)}$$

Mean

$1/\lambda$

Variance

$1/\lambda^2$

Memoryless

$P(X>s+t\mid X>s)=P(X>t)$

The exponential is the continuous twin of the geometric, and the only memoryless continuous distribution on $[0,\infty)$. A light bulb that "doesn't age" has an exponential lifetime.

Poisson ⇔ Exponential: two views of the same process.

• "How many events in the next hour?" → $\Pois(\lambda)$
• "How long until the next event?" → $\Exp(\lambda)$

One Poisson process, two distributions

The ticks are events on a timeline. Left: count the events in each unit window, which gives a Poisson. Right: measure the gaps between consecutive events, which gives an exponential.

Minimum of exponentials. If $X_1\sim\Exp(\lambda_1)$ and $X_2\sim\Exp(\lambda_2)$ are independent, then

$$\min(X_1,X_2)\sim\Exp(\lambda_1+\lambda_2), \qquad P(X_1 \text{ is the min}) = \frac{\lambda_1}{\lambda_1+\lambda_2}.$$

Emails arrive at rate $\lambda_1$ and texts at rate $\lambda_2$. "Either one" arrives at rate $\lambda_1+\lambda_2$, because merged streams add their rates.

Proof (via tails, which is always the easy way for a min)

$$P(\min>t)=P(X_1>t)\,P(X_2>t)=e^{-\lambda_1t}e^{-\lambda_2t}=e^{-(\lambda_1+\lambda_2)t}.$$

That is exactly the survival function of $\Exp(\lambda_1+\lambda_2)$.

Three independent servers have exponential lifetimes with mean 6 months each. What's the expected time until the first one fails?

• 6 months
• 2 months
• 18 months
• 3 months

Each has rate $1/6$ per month, so the min has rate $3/6=1/2$ and mean $2$ months.

Gaussian (normal)

$X\sim\N(\mu,\sigma^2)$ has mean $\mu$ and variance $\sigma^2$. Any normal can be turned into the standard normal by shifting to mean 0 and rescaling to variance 1:

$$Z=\frac{X-\mu}{\sigma}\sim\N(0,1)$$

Example. Heights are $\N(70, 3^2)$ inches. What fraction of people are taller than 76″? Standardize: $Z=(76-70)/3=2$, so $P(X>76)=P(Z>2)\approx 2.3\%$.

Percentiles. $z_\alpha$ is the point with probability $\alpha$ to its left: $P(Z\le z_\alpha)=\alpha$. By symmetry $z_{1-\alpha}=-z_\alpha$. For a general normal, $x_\alpha=\mu+\sigma z_\alpha$.

Normal areas & percentiles

Drag $c$ to see $P(|Z|\le c)$, the area in the middle. The famous 68–95–99.7 rule falls out at $c=1,2,3$.

confidence $1-\alpha$	two-sided $z_{1-\alpha/2}$	one-sided $z_{1-\alpha}$
90%	1.645	1.282
95%	1.960	1.645
99%	2.576	2.326

A two-sided $(1-\alpha)$ interval puts $\alpha/2$ in each tail: $P(|Z|\le z_{1-\alpha/2})=1-\alpha$.

Sums of independent Gaussians are Gaussian: means add and variances add (standard deviations do not).

$$X_1+X_2\sim\N(\mu_1+\mu_2,\ \sigma_1^2+\sigma_2^2)$$

Adding standard deviations instead of variances is a very common mistake. If $X_1, X_2\sim\N(0,1)$ are independent, then $X_1+X_2$ has standard deviation $\sqrt2$, not $2$. In general, $\Var(aX)=a^2\Var(X)$ but $\Var(X_1+X_2)=\Var(X_1)+\Var(X_2)$ when independent.

Cheat sheet

Distribution	PMF / PDF	Mean	Variance	Story
$\Bern(p)$	$p^x(1-p)^{1-x}$	$p$	$p(1-p)$	one coin flip
$\Bin(n,p)$	$\binom nk p^k(1-p)^{n-k}$	$np$	$np(1-p)$	#heads in $n$ flips
$\Pois(\lambda)$	$\lambda^ke^{-\lambda}/k!$	$\lambda$	$\lambda$	#events in a window
$\Geom(p)$	$(1-p)^{k-1}p$	$1/p$	$(1-p)/p^2$	#flips to first head
$\Unif(a,b)$	$1/(b-a)$	$(a+b)/2$	$(b-a)^2/12$	no information
$\Exp(\lambda)$	$\lambda e^{-\lambda x}$	$1/\lambda$	$1/\lambda^2$	time to next event
$\N(\mu,\sigma^2)$	$\frac{1}{\sigma\sqrt{2\pi}}e^{-(x-\mu)^2/2\sigma^2}$	$\mu$	$\sigma^2$	sums/averages of many things