Discrete distributions

Most questions about chance are questions about numbers: how many heads in 10 flips, how many clicks out of 1,000 impressions, how many rolls until the first six, how many requests reach a server in a second. A random variable is such a number, and its distribution says how its probability is spread over the possible values. A handful of distributions, each with a short story that produces it, covers most counts that occur in practice. This note introduces random variables and five of these stories; the next note does the same for measurements that vary continuously.

Notation. $X, Y$ are random variables. $p_X(k) = P(X = k)$ is the probability mass function (PMF) of a discrete $X$, and $F_X(x) = P(X \le x)$ its cumulative distribution function (CDF). $X \sim \mathrm{Bin}(n, p)$ reads ”$X$ has the binomial distribution with parameters $n$ and $p$”. $\mathbb 1_A$ is the indicator of an event $A$: 1 if $A$ happens and 0 otherwise.

Random variables#

Formally, a random variable is a function $X : \Omega \to \mathbb R$ that assigns a number to every outcome. Roll two dice; the sum $S$ maps the outcome $(3, 5)$ to 8. Events about $X$ are events about outcomes: $\{S = 8\}$ is the set of five pairs that sum to 8, so $p_S(8) = 5/36$. The whole PMF of $S$ is

$$p_S(2), \dots, p_S(12) = \tfrac{1}{36}, \tfrac{2}{36}, \tfrac{3}{36}, \tfrac{4}{36}, \tfrac{5}{36}, \tfrac{6}{36}, \tfrac{5}{36}, \tfrac{4}{36}, \tfrac{3}{36}, \tfrac{2}{36}, \tfrac{1}{36} .$$

A PMF is non-negative and sums to 1 over the values, and every probability about $X$ is a sum of it: $P(S \ge 10) = \frac{3 + 2 + 1}{36} = \frac16$. Once the distribution is known, the sample space can be forgotten. Two different experiments, a die and a spinner with six equal sectors, give random variables with the same distribution, and every probability statement about them is the same.

The CDF $F_X(x) = P(X \le x)$ carries the same information in cumulative form. For a discrete variable it is a staircase that jumps by $p_X(k)$ at every value $k$, and $P(a < X \le b) = F_X(b) - F_X(a)$.

Bernoulli and categorical#

The simplest random variable takes the value 1 with probability $p$ and 0 with probability $1 - p$: $X \sim \mathrm{Bernoulli}(p)$. Every yes/no event gives one, its indicator $\mathbb 1_A \sim \mathrm{Bernoulli}(P(A))$. A spam filter, a click model and a binary classifier all output the parameter $p$ of a Bernoulli distribution over the label.

With $K$ possible values instead of two, the categorical distribution gives value $k$ probability $p_k$, with $p_1 + \dots + p_K = 1$. A classifier’s softmax output is a categorical distribution over classes, and a language model’s output is a categorical distribution over the vocabulary. Training them by cross-entropy is fitting these parameters by maximum likelihood.

Binomial#

Repeat a Bernoulli trial $n$ times independently, with the same $p$, and count the successes: $X \sim \mathrm{Bin}(n, p)$. A particular sequence with $k$ successes and $n - k$ failures has probability $p^k (1-p)^{n-k}$, by independence, and there are $\binom nk$ such sequences, so

$$P(X = k) = \binom nk p^k (1-p)^{n-k}, \qquad k = 0, 1, \dots, n .$$

Ten fair coin flips give exactly 5 heads with probability $\binom{10}{5} / 2^{10} = 252/1024 = 0.246$; at least 8 heads with probability $56/1024 = 0.055$. An ad shown 1,000 times with a click probability of 2% gets $\mathrm{Bin}(1000, 0.02)$ clicks, 20 on average, and 30 or more with probability only $0.021$. Whether 30 clicks are evidence of a better ad or luck is a question for hypothesis tests; the binomial distribution is what they compute with. The number of correct answers of a classifier on a test set is binomial too, if the test examples are independent.

Geometric#

Repeat the trial until the first success and count the trials: $X \sim \mathrm{Geom}(p)$. The first success comes at trial $k$ if the first $k - 1$ trials fail and the $k$-th succeeds:

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

Waiting for a six takes more than 10 rolls with probability $(5/6)^{10} = 0.16$. (Some books count the failures before the first success instead, which shifts the values by one.)

The geometric distribution is memoryless: having already failed $m$ times changes nothing about the wait ahead,

$$P(X > m + k \mid X > m) = \frac{(1-p)^{m+k}}{(1-p)^m} = (1-p)^k = P(X > k) .$$

After 10 rolls without a six, the probability of 10 more without one is still $0.16$. The dice have no memory; the belief that a six is “due” is the gambler’s fallacy.

Poisson#

Many counts are numbers of rare events among very many opportunities: typos on a page, requests to a server in a second, mutations in a genome, goals in a football match. If there are $n$ opportunities, each with a small probability $p = \lambda / n$, the count is $\mathrm{Bin}(n, \lambda/n)$, and as $n$ grows with the mean $\lambda$ fixed,

$$\binom nk \Big(\frac{\lambda}{n}\Big)^k \Big(1 - \frac{\lambda}{n}\Big)^{n-k} = \underbrace{\frac{n (n-1) \cdots (n-k+1)}{n^k}}_{\to 1} \frac{\lambda^k}{k!} \underbrace{\Big(1 - \frac{\lambda}{n}\Big)^{n}}_{\to e^{-\lambda}} \underbrace{\Big(1 - \frac{\lambda}{n}\Big)^{-k}}_{\to 1} \to e^{-\lambda} \frac{\lambda^k}{k!} .$$

In words: the first factor compares the number of ways to place $k$ events, $\binom nk$, with $n^k / k!$ and tends to 1, since $k$ is fixed while $n$ grows; so does the last factor; and the middle one is the probability that none of the $n$ opportunities fires, which tends to $e^{-\lambda}$ by the limit $(1 + x/n)^n \to e^x$ from calculus, the one behind continuous compounding of interest.

The limit is the Poisson distribution, $X \sim \mathrm{Poisson}(\lambda)$, with $P(X = k) = e^{-\lambda} \lambda^k / k!$ for $k = 0, 1, 2, \dots$ It has a single parameter, the mean count, and needs neither $n$ nor $p$ separately, which is why it fits counts whose number of opportunities nobody knows. The approximation is good already for moderate $n$:

Figure

A binomial with small p approaches the Poisson distribution

The classic data set is Bortkiewicz’s count of soldiers killed by horse kicks in the Prussian cavalry. In 200 corps-years there were 122 deaths, a mean of $0.61$ per corps per year. The Poisson distribution with $\lambda = 0.61$, fitted from that one number, predicts how many corps-years should have had 0, 1, 2, 3 and 4 deaths:

Figure

Deaths from horse kicks in the Prussian cavalry and the Poisson distribution

The fit is close because the story fits: many soldiers, each with a tiny and roughly independent risk.

Hypergeometric#

Draw $n$ items without replacement from a population of $N$, of which $K$ are special, and count the special ones. The counting note already computed it for two aces in a hand of five:

$$P(X = k) = \frac{\binom Kk \binom{N - K}{n - k}}{\binom Nn} ,$$

and $P(X = 2) = 0.0399$ for $N = 52$, $K = 4$, $n = 5$. The count ranges from $\max(0, n - (N - K))$, when the sample is too large to avoid all special items, to $\min(n, K)$; outside that range a binomial coefficient in the formula is zero. The draws are dependent: each ace drawn makes the next one less likely. Treating them as independent trials with $p = 4/52$ gives the binomial answer $0.0465$, 17% too high. When the population is much larger than the sample, removing a few items barely changes the proportions, and the hypergeometric distribution is close to the binomial; this is why polls of 1,000 people from a country of millions use binomial formulas.

Which story gives which distribution#

Story	Distribution	Values	PMF
One yes/no trial	$\mathrm{Bernoulli}(p)$	0, 1	$p^k (1-p)^{1-k}$
One of $K$ categories	$\mathrm{Categorical}(p_1, \dots, p_K)$	$1, \dots, K$	$p_k$
Successes in $n$ independent trials	$\mathrm{Bin}(n, p)$	$0, \dots, n$	$\binom nk p^k (1-p)^{n-k}$
Trials until the first success	$\mathrm{Geom}(p)$	$1, 2, \dots$	$(1-p)^{k-1} p$
Rare events among many opportunities	$\mathrm{Poisson}(\lambda)$	$0, 1, \dots$	$e^{-\lambda} \lambda^k / k!$
Special items in a sample without replacement	$\mathrm{HGeom}(N, K, n)$	$\max(0, n - N + K), \dots, \min(n, K)$	$\binom Kk \binom{N-K}{n-k} / \binom Nn$

What changed#

	Events	Random variables
What is described	one yes/no statement at a time	a number and all statements about it at once
How	$P(A)$	a PMF $p_X(k)$ or a CDF $F_X(x)$
Reuse	a new calculation per problem	a named distribution per story: binomial, geometric, Poisson, …

Limitations#

• A distribution is only as good as its story. The binomial needs independent trials with the same $p$; clicks from the same user, or a test set with near-duplicates, break both conditions and make the real spread wider than the binomial one.
• Real counts are often overdispersed. Counts of events that come in bursts (requests from bots, words in documents) vary more than a Poisson with the same mean allows; negative binomial or mixture models are then used.
• Values must be countable. Measurements such as a waiting time or a height need densities, the subject of the next note.

What you should remember#

• A random variable is a number determined by the outcome; its PMF $p_X(k) = P(X = k)$ or CDF $F_X(x) = P(X \le x)$ answers every probability question about it.
• Bernoulli and categorical: one trial with two or $K$ outcomes, the output of a classifier.
• Binomial: successes in $n$ independent trials, $\binom nk p^k (1-p)^{n-k}$.
• Geometric: trials until the first success, $P(X > k) = (1-p)^k$, memoryless.
• Poisson: the limit of $\mathrm{Bin}(n, \lambda/n)$, $e^{-\lambda} \lambda^k / k!$, for rare events among many opportunities.
• Hypergeometric: sampling without replacement; close to binomial when the population is much larger than the sample.

Code#

Every number of the note, with scipy.stats:

import numpy as np
from scipy import stats

# the sum of two dice: a random variable and its PMF (counts out of 36)
s = np.add.outer(np.arange(1, 7), np.arange(1, 7)).ravel()
print(np.bincount(s)[2:])                                         # [1 2 3 4 5 6 5 4 3 2 1]

print(round(stats.binom(10, 0.5).pmf(5), 4), round(stats.binom(10, 0.5).sf(7), 4))   # 0.2461 0.0547
clicks = stats.binom(1000, 0.02)
print(clicks.mean(), round(clicks.sf(29), 4))                     # 20.0 0.0207

print(round((5 / 6) ** 10, 4))                                    # 0.1615: more than 10 rolls to the first six

# binomial(n, 3/n) against Poisson(3): total variation distance
for n in [5, 10, 100]:
    k = np.arange(n + 1)
    tv = 0.5 * (np.abs(stats.binom(n, 3 / n).pmf(k) - stats.poisson(3).pmf(k)).sum() + stats.poisson(3).sf(n))
    print(n, round(tv, 3))                                        # 5 0.219, 10 0.086, 100 0.008

# Bortkiewicz's horse kicks: corps-years with 0..4 deaths, and the Poisson fit
observed = np.array([109, 65, 22, 3, 1])
lam = (observed * np.arange(5)).sum() / observed.sum()
print(lam, (observed.sum() * stats.poisson(lam).pmf(np.arange(5))).round(1))   # 0.61 [108.7  66.3  20.2   4.1   0.6]

# two aces in five cards: hypergeometric, and the binomial that ignores the missing cards
print(round(stats.hypergeom(52, 4, 5).pmf(2), 4), round(stats.binom(5, 4 / 52).pmf(2), 4))   # 0.0399 0.0465

Next#

Counts take separate values, and their probabilities are masses at those values. A waiting time, a height or the position of a random point can take any value in an interval, and each single value has probability 0, as the axioms note showed for a point in $[0, 1]$. The next note replaces the PMF by a density, introduces the uniform, exponential and normal distributions, and shows that the exponential is the continuous geometric: the only memoryless waiting time.

References#

• J. K. Blitzstein, J. Hwang. Introduction to Probability, 2nd ed. CRC Press, 2019. Chapter 3 (random variables, Bernoulli, binomial, hypergeometric), Chapter 4 (geometric, Poisson, the Poisson approximation).
• W. Feller. An Introduction to Probability Theory and Its Applications, Vol. 1, 3rd ed. Wiley, 1968. Chapter VI (the binomial and Poisson distributions).
• L. von Bortkiewicz. Das Gesetz der kleinen Zahlen. Teubner, 1898. The horse-kick data.