Contents / Probability / Random Variables and Discrete Distributions

Chapter 2

Random Variables and Discrete Distributions

Random variables, PMFs, expected value, binomial, Poisson, and geometric distributions.

Introduction

Probability theory, as the previous chapter left it, is a calculus of events: subsets of a sample space, combined with unions, intersections and complements. That language is exact but it is not portable. The event "three heads in five flips" and the event "three defectives in a lot of five" are different subsets of different sample spaces, yet they carry the same probability for the same reason, and nothing in the language of events says so.

The device that makes the similarity visible is the random variable. Instead of working with the outcomes themselves we work with a number attached to each outcome — a count, a waiting time, a payout — and we study the pattern of probabilities that number inherits. Two experiments with nothing physical in common can then turn out to have the same distribution, and one calculation serves both.

This chapter builds that machinery and then stocks it. We define random variables, mass functions and distribution functions precisely; we define expectation and variance from the definition and prove the algebra they obey — including linearity of expectation, which is the single most useful fact in the chapter and which holds whether or not the variables are independent. Then we derive the standard discrete families: the binomial from a counting argument, the Poisson as a limit of the binomial, the geometric from the waiting-time picture, and the negative binomial and hypergeometric as the two most common variations. The final section is a decision guide, because in practice the hard part is almost never the arithmetic — it is recognising which family the problem belongs to.

Everything here is a prerequisite for the rest of the subject, and for statistical inference beyond it. A confidence interval is a statement about the distribution of an estimator; a $p$ -value is a tail probability under an assumed distribution. Neither means anything until "distribution" does.

2.1Random Variables, Mass Functions, and Distribution Functions

The word "variable" is a small lie: a random variable does not vary, and it is not a variable in the algebraic sense. It is a function.

Definition 2.1 (Random variable). Let $(\Omega, \mathcal{F}, P)$ be a probability space. A random variable is a function

X : \Omega \to \mathbb{R}

such that for every $x \in \mathbb{R}$ the set $\{\omega \in \Omega : X(\omega) \le x\}$ is an event (that is, it belongs to $\mathcal{F}$ , so it has a probability).

$X$ is discrete if its range $X(\Omega)$ is finite or countably infinite.

The measurability condition in the definition is there so that questions like "what is the probability that $X$ is at most $3$ ? " have answers. For a discrete random variable on a finite sample space it is automatic, and we will not fuss over it again; but it is worth seeing once, because it is the reason the definition is a definition and not merely a description.

Intuition. Think of the sample space as a bag of tickets, one ticket per possible outcome. A random variable is a rule that reads a number off each ticket. You draw a ticket at random; the number you read is the value of $X$ . The randomness lives entirely in which ticket you drew — the rule itself is fixed and deterministic.

This is why " $X = 3$ " is shorthand for a set of outcomes: it means "the ticket you drew is one of the tickets with a $3$ printed on it".

Notation. $\{X = x\}$ abbreviates the event $\{\omega : X(\omega) = x\}$ , and $P(X = x)$ its probability. Likewise $\{X \le x\}$ , $\{X > x\}$ , $\{a < X \le b\}$ . Capital letters denote random variables, lower-case letters the particular values they might take; the distinction is worth preserving, because $P(X = x)$ is a function of $x$ while $X$ is not a number at all.

Example 2.2 (Two coin flips). Toss a fair coin twice and let $X$ be the number of heads. Write $X$ explicitly as a function on the sample space, and find the probability of each value.

Solution.

The sample space is $\Omega = \{HH, HT, TH, TT\}$ , each outcome with probability $\tfrac14$ .
As a function, $X(HH) = 2$ , $X(HT) = X(TH) = 1$ , $X(TT) = 0$ . The range is $\{0,1,2\}$ , so $X$ is discrete.
The event $\{X = 1\}$ is $\{HT, TH\}$ , which has probability $\tfrac24 = \tfrac12$ . Similarly $P(X=0) = P(X=2) = \tfrac14$ .
Notice that $X$ collapses two distinct outcomes into one value. That is the whole point: we no longer care which flip was the head.

□

The probability mass function

Listing the probability of each value is the complete description of a discrete random variable, and it deserves a name.

Definition 2.3 (Probability mass function). The probability mass function (pmf) of a discrete random variable $X$ is the function

p_X(x) = P(X = x), \qquad x \in \mathbb{R}.

Its support is the set $S = \{x : p_X(x) > 0\}$ , which is finite or countable.

Not every function of $x$ is a pmf. Two conditions decide it, and they are exactly the conditions the axioms of probability force.

Theorem 2.4 (Characterisation of a pmf). A function $p : \mathbb{R} \to \mathbb{R}$ that is nonzero on at most countably many points $x_1, x_2, \ldots$ is the pmf of some discrete random variable if and only if

p(x_i) \ge 0 \ \text{ for all } i, \qquad \sum_{i} p(x_i) = 1.

Proof. ( $\Rightarrow$ ) If $p = p_X$ then $p(x_i) = P(X = x_i) \ge 0$ by nonnegativity of $P$ . The events $\{X = x_i\}$ are pairwise disjoint and their union is the certain event, so countable additivity gives $\sum_i P(X = x_i) = P(\Omega) = 1$ .

( $\Leftarrow$ ) Conversely, given such a $p$ , take $\Omega = \{x_1, x_2, \ldots\}$ with $P(\{x_i\}) = p(x_i)$ ; this is a legitimate probability measure precisely because the values are nonnegative and sum to $1$ . Let $X$ be the identity map $X(x_i) = x_i$ . Then $p_X = p$ .∎

The "if and only if" is doing real work. It says that a pmf carries all the probabilistic information about $X$ — we never need to go back to $\Omega$ — and it gives a two-line test for whether a proposed formula is legitimate. That test is also how you solve for an unknown constant.

Example 2.5 (Finding a normalising constant). Let $p(k) = c \cdot 3^{-k}$ for $k = 1, 2, 3, \ldots$ and $p(x) = 0$ otherwise. For which $c$ is this a pmf, and what is $P(X \ge 3)$ ?

Solution.

Nonnegativity forces $c \ge 0$ .
Summing the geometric series, $\sum_{k=1}^{\infty} 3^{-k} = \frac{1/3}{1 - 1/3} = \tfrac12$ .
So the total mass is $c/2$ , and it equals $1$ exactly when $c = 2$ .
For the tail, $P(X \ge 3) = \sum_{k=3}^{\infty} 2 \cdot 3^{-k} = 2 \cdot \frac{3^{-3}}{1 - 1/3} = 2 \cdot \frac{1/27}{2/3} = \tfrac{1}{9}$ .
Sanity check: $P(X=1) = 2/3$ and $P(X=2) = 2/9$ , and $\tfrac23 + \tfrac29 + \tfrac19 = 1$ ✓.

□

The cumulative distribution function

The pmf answers "what is the chance of exactly this value?". A great many questions are instead about accumulated probability, and those are read off a second function.

Definition 2.6 (Cumulative distribution function). The cumulative distribution function (cdf) of a random variable $X$ is

F_X(x) = P(X \le x), \qquad x \in \mathbb{R}.

For a discrete $X$ , $F_X(x) = \sum_{x_i \le x} p_X(x_i)$ .

Proposition 2.7 (Properties of a cdf). For any random variable $X$ , the function $F = F_X$ satisfies

$F$ is non-decreasing;
$\lim_{x \to -\infty} F(x) = 0$ and $\lim_{x \to +\infty} F(x) = 1$ ;
$F$ is right-continuous: $\lim_{h \downarrow 0} F(x+h) = F(x)$ .

Moreover, for a discrete $X$ the jump of $F$ at $x$ equals $p_X(x)$ :

p_X(x) = F(x) - \lim_{h \downarrow 0} F(x - h).

Proof. (1) If $x \le y$ then $\{X \le x\} \subseteq \{X \le y\}$ , and probability is monotone on nested events.

(2) The events $\{X \le n\}$ increase to $\Omega$ as $n \to \infty$ and decrease to $\varnothing$ as $n \to -\infty$ ; continuity of $P$ along monotone sequences of events gives the two limits.

(3) Right-continuity is the same continuity property applied to $\{X \le x + 1/n\} \downarrow \{X \le x\}$ ; the intersection is $\{X \le x\}$ because the inequality is non-strict.

For the jump, $\{X \le x\} \setminus \bigcup_n \{X \le x - 1/n\} = \{X = x\}$ , and the union is the increasing limit whose probability is the left-hand limit of $F$ .∎

So the pmf and the cdf are two encodings of the same object: the cdf is the running total of the pmf, and the pmf is the size of the cdf's jumps. For a discrete variable the cdf is a staircase — flat between the support points, jumping at each of them by exactly that point's probability.

Figure 2.8. The cdf of the payout

X

with

P(X=-2)=0.6

P(X=5)=0.3

P(X=10)=0.1

. The staircase is flat between support points and jumps at each one by exactly that point's probability; the filled dot at the top of a jump is the value

F

actually takes there, which is why

F

is right-continuous.

Pitfall. For a discrete variable $P(X < x)$ and $P(X \le x)$ are different, and the difference is exactly $p_X(x)$ . Reading $P(X < 5)$ off a cdf table gives $F(4)$ , not $F(5)$ , whenever $X$ is integer-valued. This is the single most common arithmetic slip in binomial and Poisson work, and it disappears only for continuous variables, where individual points have probability zero. Write the complement rule out in full whenever you use it:

P(X \ge k) = 1 - P(X \le k-1) = 1 - F(k-1).

Exercises for §2.1 →

2.2Expectation, Variance, and Linearity

A pmf is a complete description, but it is rarely a usable summary: nobody quotes eleven numbers to describe the outcome of ten coin flips. Two numbers do most of the work — a centre and a spread.

Definition 2.9 (Expected value). Let $X$ be discrete with support $S$ and pmf $p_X$ . The expected value (or mean, or expectation) of $X$ is

\mu = E(X) = \sum_{x \in S} x \, p_X(x),

provided the sum converges absolutely, i.e. $\sum_{x \in S} |x| \, p_X(x) < \infty$ . If it does not, $E(X)$ does not exist.

The absolute-convergence proviso is not pedantry. A sum of infinitely many terms with mixed signs can be rearranged to give any value you like, and a mean that depends on the order in which you list the outcomes is no mean at all. Distributions with no expectation exist and are not exotic; the St. Petersburg payout, which pays $2^k$ with probability $2^{-k}$ , has $\sum_k 2^k 2^{-k} = \sum_k 1 = \infty$ .

Intuition. $E(X)$ is a weighted average of the possible values, weighted by how often each occurs. Mechanically it is the centre of mass of the pmf: put a mass $p_X(x)$ at position $x$ on a weightless rod, and $E(X)$ is where the rod balances.

That picture explains why the mean need not be a possible value — the balance point of two equal masses at $1$ and $6$ is $3.5$ , where there is no mass at all — and why a single far-out value with small probability can still drag the mean a long way.

We frequently need the mean not of $X$ but of some function of it, and the following result says we can compute it without ever finding the distribution of that function.

Theorem 2.10 (Law of the unconscious statistician). Let $X$ be discrete with pmf $p_X$ and let $g : \mathbb{R} \to \mathbb{R}$ . Then

E[g(X)] = \sum_{x \in S} g(x) \, p_X(x),

whenever the sum converges absolutely.

Proof. Let $Y = g(X)$ , with support $T = g(S)$ . By the definition of expectation applied to $Y$ ,

E(Y) = \sum_{y \in T} y \, P(Y = y).

Now $\{Y = y\} = \bigcup \{X = x\}$ over those $x \in S$ with $g(x) = y$ , a disjoint union, so $P(Y = y) = \sum_{x : g(x) = y} p_X(x)$ . Substituting,

E(Y) = \sum_{y \in T} \ \sum_{x : g(x) = y} y \, p_X(x) = \sum_{y \in T} \ \sum_{x : g(x) = y} g(x) \, p_X(x),

since $g(x) = y$ on the inner sum. The sets $\{x : g(x) = y\}$ , as $y$ ranges over $T$ , partition $S$ , so the double sum is just $\sum_{x \in S} g(x) p_X(x)$ . Absolute convergence licenses the rearrangement.∎

The name is a joke at the expense of people who use the formula without noticing it needs proof. The content is that you may evaluate $g$ at each $x$ and weight by $p_X(x)$ , rather than first working out the pmf of $g(X)$ — a saving that is enormous in practice.

Linearity

Theorem 2.11 (Linearity of expectation). Let $X$ and $Y$ be discrete random variables on the same probability space with finite expectations, and let $a, b, c$ be constants. Then

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

No independence is required.

Proof. Write the expectation as a sum over the outcomes rather than over the values. For a discrete $X$ on a countable $\Omega$ ,

E(X) = \sum_{x} x \, P(X = x) = \sum_{x} \ \sum_{\omega : X(\omega) = x} X(\omega) P(\{\omega\}) = \sum_{\omega \in \Omega} X(\omega) P(\{\omega\}),

because the events $\{X = x\}$ partition $\Omega$ ; absolute convergence, which is exactly the finiteness of $E|X|$ , justifies collapsing the double sum.

In that form the result is immediate. Let $Z = aX + bY + c$ , so $Z(\omega) = aX(\omega) + bY(\omega) + c$ pointwise. Then

E(Z) = \sum_{\omega} \big( aX(\omega) + bY(\omega) + c \big) P(\{\omega\}) = a\sum_{\omega} X(\omega)P(\{\omega\}) + b\sum_{\omega} Y(\omega)P(\{\omega\}) + c\sum_{\omega} P(\{\omega\}),

and the three sums are $E(X)$ , $E(Y)$ and $1$ .∎

Look at what the proof used: only that $X$ and $Y$ are functions on the same $\Omega$ , so that they can be added pointwise. The joint behaviour of $X$ and $Y$ never appeared. This is why linearity survives arbitrary dependence, and it is what makes it the most useful single fact in the chapter.

Remark. The contrast with variance is the thing to remember. Expectation is a sum over outcomes and therefore additive, always. Variance involves a square, and $(x+y)^2 \ne x^{2} + y^{2}$ ; the cross term is what independence kills. Whenever you find yourself wondering whether a rule needs independence, ask whether a product of two variables appears anywhere in it.

Intuition. Linearity is a licence to decompose. If a complicated count $X$ can be written as $X = X_1 + X_2 + \cdots + X_n$ for simple pieces — usually indicators, each worth $0$ or $1$ — then $E(X)$ is just the sum of $n$ easy expectations, no matter how tangled the dependence between the pieces. You will see this used to get the binomial mean in two lines rather than half a page of series manipulation, and it is the standard tool for expectations that no direct summation can reach.

Lemma 2.12 (Expectation of an indicator). For an event $A$ , define the indicator $\mathbf{1}_A$ by $\mathbf{1}_A(\omega) = 1$ if $\omega \in A$ and $0$ otherwise. Then

E(\mathbf{1}_A) = P(A), \qquad E(\mathbf{1}_A^2) = P(A), \qquad \text{Var}(\mathbf{1}_A) = P(A)\big(1 - P(A)\big).

Proof. $\mathbf{1}_A$ takes the value $1$ with probability $P(A)$ and $0$ with probability $1 - P(A)$ , so $E(\mathbf{1}_A) = 1 \cdot P(A) + 0 \cdot (1 - P(A)) = P(A)$ . Since $\mathbf{1}_A^{2} = \mathbf{1}_A$ (as $0^2 = 0$ and $1^2 = 1$ ), the second expectation is the same. Then $\text{Var}(\mathbf{1}_A) = E(\mathbf{1}_A^{2}) - E(\mathbf{1}_A)^2 = P(A) - P(A)^2$ .∎

Variance

Definition 2.13 (Variance and standard deviation). Let $X$ have finite mean $\mu$ . The variance of $X$ is

\sigma^2 = \text{Var}(X) = E\big[(X - \mu)^2\big] = \sum_{x \in S} (x - \mu)^2 p_X(x),

and the standard deviation is $\sigma = \sqrt{\text{Var}(X)}$ .

Variance is the mean squared distance from the mean. Squaring is what stops positive and negative deviations from cancelling — $E(X - \mu) = 0$ always, by linearity, so the un-squared average deviation carries no information. The price is that variance is in squared units, which is why the standard deviation, in the original units, is what gets reported.

Proposition 2.14 (Computational formula for the variance). If $E(X^{2}) < \infty$ then

\text{Var}(X) = E(X^2) - [E(X)]^2.

Proof. Expand the square inside the expectation and apply linearity, treating $\mu = E(X)$ as the constant it is:

E[(X-\mu)^2] = E[X^2 - 2\mu X + \mu^2] = E(X^2) - 2\mu E(X) + \mu^2 = E(X^2) - 2\mu^2 + \mu^2 = E(X^2) - \mu^2.

∎

Corollary 2.15 (Variance is non-negative, and $E(X^{2}) \ge [E(X)]^2$ ). Since $\text{Var}(X) = E[(X-\mu)^2]$ is the expectation of a non-negative quantity, $\text{Var}(X) \ge 0$ ; hence $E(X^{2}) \ge [E(X)]^2$ , with equality if and only if $X$ is constant with probability $1$ .

Proposition 2.16 (Variance under a linear change of scale). For constants $a$ and $b$ ,

\text{Var}(aX + b) = a^2 \, \text{Var}(X), \qquad \text{SD}(aX+b) = |a| \, \text{SD}(X).

Proof. Let $Y = aX + b$ . By linearity $E(Y) = a\mu + b$ , so

Y - E(Y) = (aX + b) - (a\mu + b) = a(X - \mu).

The shift $b$ cancels — it moves $Y$ and its mean by the same amount. Squaring and taking expectations,

\text{Var}(Y) = E\big[a^2 (X-\mu)^2\big] = a^2 E\big[(X-\mu)^2\big] = a^2 \text{Var}(X),

using linearity to pull the constant $a^{2}$ out. Taking square roots gives $|a|\sigma$ , the absolute value because a standard deviation is non-negative.∎

The $b$ dropping out is the whole content: adding a constant relocates a distribution without stretching it, so it cannot change the spread. The $a^{2}$ says spread scales with the square of a multiplier — double every payout and the variance quadruples, while the standard deviation merely doubles.

Lemma 2.17 (Expectation of a product of independent variables). If $X$ and $Y$ are independent discrete random variables with finite expectations, then $E(XY) = E(X)E(Y)$ .

Proof. Independence means $P(X = x, Y = y) = P(X = x)P(Y = y)$ for all $x, y$ . By the two-variable form of the law of the unconscious statistician applied to $g(x,y) = xy$ ,

E(XY) = \sum_{x}\sum_{y} xy \, P(X=x, Y=y) = \sum_{x}\sum_{y} xy \, P(X=x)P(Y=y),

and the double sum factors:

= \left(\sum_{x} x\,P(X=x)\right)\left(\sum_{y} y\,P(Y=y)\right) = E(X)E(Y).

∎

Theorem 2.18 (Variance of a sum of independent variables). If $X$ and $Y$ are independent with finite variances, then

\text{Var}(X + Y) = \text{Var}(X) + \text{Var}(Y).

More generally, if $X_1, \ldots, X_n$ are pairwise independent with finite variances, $\text{Var}\!\left(\sum_{i} X_i\right) = \sum_{i} \text{Var}(X_i)$ .

Proof. Write $\mu_X = E(X)$ , $\mu_Y = E(Y)$ . By linearity $E(X+Y) = \mu_X + \mu_Y$ , so

\text{Var}(X+Y) = E\big[\big((X - \mu_X) + (Y - \mu_Y)\big)^2\big].

Expand the square and use linearity:

= E[(X-\mu_X)^2] + E[(Y-\mu_Y)^2] + 2E[(X-\mu_X)(Y-\mu_Y)].

The first two terms are $\text{Var}(X)$ and $\text{Var}(Y)$ . For the third, note that if $X$ and $Y$ are independent then so are $X - \mu_X$ and $Y - \mu_Y$ , so by Lemma Expectation of a product of independent variables

E[(X-\mu_X)(Y-\mu_Y)] = E(X - \mu_X)\,E(Y-\mu_Y) = 0 \cdot 0 = 0.

Hence the cross term vanishes and the variances add. For the general case, expand $\big(\sum_i (X_i - \mu_i)\big)^2$ directly: it produces the $n$ squares $(X_i-\mu_i)^2$ and the $\binom{n}{2}$ cross terms $2(X_i-\mu_i)(X_j-\mu_j)$ with $i \ne j$ , each of which vanishes by the same argument. Only pairs ever appear, which is why pairwise independence suffices and mutual independence is not needed.∎

Remark. The quantity $E[(X-\mu_X)(Y-\mu_Y)]$ that vanished is the covariance $\text{Cov}(X,Y)$ . Without independence the identity reads

\text{Var}(X+Y) = \text{Var}(X) + \text{Var}(Y) + 2\,\text{Cov}(X,Y),

which is always true. Independence is a sufficient condition for the covariance to vanish, not a necessary one: uncorrelated variables need not be independent. Note also that subtracting independent variables still adds their variances, since $\text{Var}(X - Y) = \text{Var}(X) + (-1)^2\text{Var}(Y)$ — uncertainty never cancels.

Pitfall. Standard deviations do not add, ever. If $X$ and $Y$ are independent each with $\sigma = 3$ , then $\text{Var}(X+Y) = 9 + 9 = 18$ and $\text{SD}(X+Y) = \sqrt{18} \approx 4.24$ , not $6$ . Add variances, then take the square root once at the end.

Example 2.19 (Mean and variance of a payout). A game pays $10 with probability $0.1$ , $5 with probability $0.3$ , and $-\$2$ with probability $0.6$ . Find $E(X)$ and $\text{Var}(X)$ , and then the mean and variance of $Y = 3X + 4$ .

Solution.

First verify the pmf: all values are non-negative and $0.1 + 0.3 + 0.6 = 1$ ✓.
$E(X) = 10(0.1) + 5(0.3) + (-2)(0.6) = 1 + 1.5 - 1.2 = 1.3$ .
By the law of the unconscious statistician with $g(x) = x^{2}$ : $E(X^{2}) = 100(0.1) + 25(0.3) + 4(0.6) = 10 + 7.5 + 2.4 = 19.9$ .
By the computational formula, $\text{Var}(X) = 19.9 - 1.3^2 = 19.9 - 1.69 = 18.21$ , so $\sigma = \sqrt{18.21} \approx 4.27$ .
For $Y = 3X + 4$ : $E(Y) = 3(1.3) + 4 = 7.9$ and $\text{Var}(Y) = 3^2(18.21) = 163.89$ .
Sanity check: the payouts run from $-2$ to $10$ , so a typical distance of about $4.3$ from $1.3$ is believable; and $Y$ ranges over $-2, 19, 34$ , a threefold stretch, so a ninefold variance is right.

□

Example 2.20 (Linearity without independence). Five cards are dealt from a standard $52$ -card deck without replacement. Let $X$ be the number of hearts. Find $E(X)$ .

Solution.

The draws are not independent — dealing a heart makes the next heart less likely — so no product rule is available and the pmf is a hypergeometric one, awkward to sum directly.
Let $X_i = 1$ if the $i$ th card dealt is a heart, and $0$ otherwise. Then $X = X_1 + X_2 + \cdots + X_5$ .
By symmetry each individual card is equally likely to be any of the $52$ , so $P(X_i = 1) = 13/52 = 1/4$ for every $i$ , including the fifth. By Lemma Expectation of an indicator, $E(X_i) = 1/4$ .
Linearity does not care that the $X_i$ are dependent: $E(X) = 5 \times \tfrac14 = 1.25$ .
The variance would be a genuinely harder calculation, because there the dependence does not cancel — this is exactly the asymmetry the chapter keeps returning to.

□

Exercises for §2.2 →

2.3The Binomial Distribution

The binomial is what you get when you repeat the same two-outcome experiment a fixed number of times and count successes. Its ubiquity comes from how little it assumes.

Definition 2.21 (Bernoulli trial and Bernoulli random variable). A Bernoulli trial is an experiment with exactly two outcomes, labelled success and failure, with $P(\text{success}) = p$ . The associated Bernoulli random variable takes the value $1$ on success and $0$ on failure:

P(X = 1) = p, \qquad P(X = 0) = 1 - p.

We write $X \sim \text{Bernoulli}(p)$ , and by Lemma Expectation of an indicator, $E(X) = p$ and $\text{Var}(X) = p(1-p)$ .

Definition 2.22 (Binomial distribution). Let $X$ count the successes in $n$ independent Bernoulli trials, each with the same success probability $p$ . Then $X$ has the binomial distribution with parameters $n$ and $p$ , written $X \sim B(n,p)$ .

The four conditions are worth stating as a checklist, because a violated one invalidates everything that follows. The mnemonic is BINS: Binary outcomes; Independent trials; Number of trials $n$ fixed in advance; Same success probability $p$ throughout. Note what "fixed in advance" rules out — if you keep sampling until you have $10$ successes, $n$ is random and the distribution is negative binomial, not binomial.

Theorem 2.23 (The binomial pmf). If $X \sim B(n,p)$ then

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

Proof. Fix $k$ . Any particular sequence of $n$ trial outcomes containing exactly $k$ successes and $n-k$ failures — say $SSFSF\ldots$ — has probability $p^k(1-p)^{n-k}$ , because the trials are independent, so the probability of the sequence is the product of the individual probabilities, and $p$ appears once per success, $1-p$ once per failure. Crucially this product does not depend on the order: multiplication is commutative, so every such sequence has the same probability.

The event $\{X = k\}$ is the disjoint union of all such sequences. The number of them is the number of ways to choose which $k$ of the $n$ trial positions are the successes, namely $\binom{n}{k}$ . Summing the common probability over those $\binom{n}{k}$ disjoint outcomes gives the claim.∎

Corollary 2.24 (The binomial pmf is a pmf). The expressions $\binom{n}{k}p^k(1-p)^{n-k}$ are non-negative and sum to $1$ over $k = 0, \ldots, n$ .

Proof. Non-negativity is clear. For the total, the binomial theorem gives

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

∎

That is the counting argument in full: a per-sequence probability that does not depend on order, times a count of the orders. Every piece of the formula is doing a job, and reading the formula back in those terms — " $p^k(1-p)^{n-k}$ for one arrangement, $\binom{n}{k}$ arrangements" — is the fastest way to reconstruct it when you have forgotten it.

Mean and variance, the cheap way

You can obtain $E(X)$ by summing $k\binom{n}{k}p^k(1-p)^{n-k}$ and manipulating factorials. It works, and it is unpleasant. The decomposition argument is better, and the technique generalises far beyond this distribution.

Theorem 2.25 (Mean and variance of the binomial). If $X \sim B(n,p)$ then

E(X) = np, \qquad \text{Var}(X) = np(1-p), \qquad \text{SD}(X) = \sqrt{np(1-p)}.

Proof. Let $X_i = 1$ if trial $i$ is a success and $0$ otherwise, so each $X_i \sim \text{Bernoulli}(p)$ and

X = X_1 + X_2 + \cdots + X_n.

This identity is exact — the sum of the indicators literally counts the successes.

For the mean, apply Theorem Linearity of expectation, which needs no independence at all:

E(X) = \sum_{i=1}^n E(X_i) = \sum_{i=1}^n p = np.

For the variance we do need independence, and the binomial model supplies it by hypothesis. By Theorem Variance of a sum of independent variables,

\text{Var}(X) = \sum_{i=1}^n \text{Var}(X_i) = \sum_{i=1}^n p(1-p) = np(1-p).

∎

Remark. The proof is worth more than the formula. It shows the two hypotheses are used in different places: identical distribution and additivity of expectation give the mean; independence is what gives the variance. If the trials were dependent but still each had success probability $p$ — dealing cards without replacement, say — the mean would still be $np$ and the variance would not be $np(1-p)$ . That is exactly what happens with the hypergeometric distribution later in this chapter.

Intuition. $np$ is the answer you would have guessed: $200$ flips of a coin that lands heads $30\%$ of the time should give around $60$ heads.

The variance $np(1-p)$ is less obvious, but notice where it is largest. As a function of $p$ , the product $p(1-p)$ peaks at $p = 0.5$ and vanishes at $p = 0$ and $p = 1$ . That is right: a coin that always lands heads produces no uncertainty at all, while a fair coin is the most unpredictable one there is.

Figure 2.26. Binomial pmfs for

n = 10

. With

p = 0.5

(line and points) the distribution is symmetric about

5

; with

p = 0.2

(bars) the mean slides down to

2

and the distribution is right-skewed, because the values are squeezed against the floor at

0

while the tail still has room to run toward

10

The figure makes a point that the formulas alone do not. For $p = 0.5$ the pmf is symmetric, because swapping the labels "success" and "failure" maps $k \mapsto n-k$ and leaves the probabilities alone. For $p < 0.5$ that symmetry is broken and the distribution leans right; for $p > 0.5$ it leans left. The skew is strongest when $np$ is small — when the mean is close to the hard boundary at $0$ — and it washes out as $n$ grows, which is the seed of the normal approximation to the binomial, derived in the chapter on Continuous Probability Distributions.

Example 2.27 (Exactly $k$ successes). A fair coin is flipped $5$ times. Find $P(X = 3)$ , and the mean and standard deviation of $X$ .

Solution.

Check BINS: two outcomes per flip, flips independent, $n = 5$ fixed, $p = 0.5$ constant ✓.
$\binom{5}{3} = 10$ , so $P(X=3) = 10 (0.5)^3 (0.5)^2 = 10 (0.5)^5 = \tfrac{10}{32} = 0.3125$ .
$E(X) = np = 2.5$ ; $\text{Var}(X) = 5(0.5)(0.5) = 1.25$ , so $\sigma = \sqrt{1.25} \approx 1.118$ .
Sanity check: $3$ is within one standard deviation of $2.5$ , so a probability near $\tfrac13$ is reasonable for the second-most-likely value.

□

Example 2.28 (A cumulative probability via the complement). For $X \sim B(6, 0.3)$ , find $P(X \ge 2)$ .

Solution.

Direct summation needs five terms ( $k = 2, \ldots, 6$ ); the complement needs two. Use $P(X \ge 2) = 1 - P(X = 0) - P(X = 1)$ , being careful that "at least $2$ " excludes $0$ and $1$ only.
$P(X=0) = (0.7)^6 = 0.117649$ .
$P(X=1) = 6(0.3)(0.7)^5 = 6(0.3)(0.16807) = 0.302526$ .
$P(X \ge 2) = 1 - 0.117649 - 0.302526 = 0.579825$ .
Sanity check: $np = 1.8$ , so "at least $2$ " straddles the mean from just above; a value a little over one half is what you would expect.

□

Pitfall. Sampling without replacement breaks the I and the S in BINS at once: the trials are dependent and $p$ shifts after each draw. The binomial is then wrong, and the hypergeometric is right. The usual rule of thumb is that the binomial remains a serviceable approximation when the sample is no more than about $10\%$ of the population, because then the probabilities barely move; below that threshold, do not use it.

Exercises for §2.3 →

2.4The Poisson Distribution

The binomial needs a fixed $n$ . Many counting problems have no natural $n$ at all: the number of calls arriving at a switchboard in an hour, the number of typos on a page, the number of $\alpha$ -particles a sample emits in a second. There is no list of trials to count — only a rate and a window.

Definition 2.29 (Poisson distribution). For $\lambda > 0$ , a random variable $X$ has the Poisson distribution with parameter $\lambda$ , written $X \sim \text{Poisson}(\lambda)$ , if

P(X = k) = \frac{e^{-\lambda} \lambda^k}{k!}, \qquad k = 0, 1, 2, \ldots.

Proposition 2.30 (The Poisson pmf is a pmf). The stated probabilities are non-negative and sum to $1$ .

Proof. Each term is positive since $e^{-\lambda} > 0$ and $\lambda^k / k! > 0$ . Summing and using the exponential series $\sum_{k \ge 0} \lambda^k/k! = e^{\lambda}$ ,

\sum_{k=0}^{\infty} \frac{e^{-\lambda}\lambda^k}{k!} = e^{-\lambda} \sum_{k=0}^{\infty} \frac{\lambda^k}{k!} = e^{-\lambda} e^{\lambda} = 1.

∎

The support is all of $\{0, 1, 2, \ldots\}$ : there is no upper bound, which is the structural difference from the binomial and the reason the Poisson is the natural model when no maximum count exists.

Theorem 2.31 (Mean and variance of the Poisson). If $X \sim \text{Poisson}(\lambda)$ then $E(X) = \lambda$ and $\text{Var}(X) = \lambda$ .

Proof. For the mean, the $k = 0$ term contributes nothing, so start at $k = 1$ and cancel one factor of $k$ against the factorial:

E(X) = \sum_{k=1}^{\infty} k \frac{e^{-\lambda}\lambda^k}{k!} = \lambda e^{-\lambda} \sum_{k=1}^{\infty} \frac{\lambda^{k-1}}{(k-1)!} = \lambda e^{-\lambda} e^{\lambda} = \lambda,

after substituting $j = k-1$ in the sum.

For the variance, compute the factorial moment $E[X(X-1)]$ , which is easier than $E(X^{2})$ because $k(k-1)$ cancels two factors of the factorial. The $k = 0$ and $k=1$ terms vanish, so

E[X(X-1)] = \sum_{k=2}^{\infty} k(k-1)\frac{e^{-\lambda}\lambda^k}{k!} = \lambda^2 e^{-\lambda}\sum_{k=2}^{\infty}\frac{\lambda^{k-2}}{(k-2)!} = \lambda^2 e^{-\lambda}e^{\lambda} = \lambda^2.

By linearity $E(X^{2}) = E[X(X-1)] + E(X) = \lambda^{2} + \lambda$ , and therefore

\text{Var}(X) = E(X^2) - [E(X)]^2 = \lambda^2 + \lambda - \lambda^2 = \lambda.

∎

That the mean and the variance coincide is a strong and checkable claim about data, and it is the first thing to test before adopting a Poisson model.

Where the distribution comes from

The Poisson is not an arbitrary formula. It is what the binomial becomes when you chop a window into more and more, smaller and smaller, trials.

Theorem 2.32 (Poisson limit of the binomial). Fix $\lambda > 0$ and for each $n$ let $X_n \sim B(n, p_n)$ with $n p_n = \lambda$ . Then for every fixed $k \ge 0$ ,

\lim_{n \to \infty} P(X_n = k) = \frac{e^{-\lambda}\lambda^k}{k!}.

Proof. Write $p_n = \lambda/n$ and expand the binomial pmf:

P(X_n = k) = \binom{n}{k}\left(\frac{\lambda}{n}\right)^k \left(1 - \frac{\lambda}{n}\right)^{n-k} = \frac{n(n-1)\cdots(n-k+1)}{k!}\cdot\frac{\lambda^k}{n^k}\cdot\left(1-\frac{\lambda}{n}\right)^{n}\left(1-\frac{\lambda}{n}\right)^{-k}.

Group the pieces and take $n \to \infty$ with $k$ fixed.

The falling factorial over $n^k$ has $k$ factors, each of the form $(n-j)/n = 1 - j/n \to 1$ ; there are finitely many, so their product tends to $1$ .
$\left(1 - \frac{\lambda}{n}\right)^{n} \to e^{-\lambda}$ , the standard limit defining the exponential.
$\left(1 - \frac{\lambda}{n}\right)^{-k} \to 1^{-k} = 1$ , again because $k$ is fixed.

The surviving constant factor is $\lambda^k/k!$ , so the product tends to $e^{-\lambda}\lambda^k / k!$ .∎

Intuition. Split an hour into $n$ tiny intervals, so small that at most one call can arrive in any one of them. Each interval is then a Bernoulli trial, and if calls arrive at $\lambda$ per hour the success probability in each is about $\lambda/n$ . The count of calls is binomial with these parameters — and as you refine the intervals, $n \to \infty$ while $np$ stays pinned at $\lambda$ . What you are left with is the Poisson.

The limit also explains the mean and variance. The binomial variance is $np(1-p) = \lambda(1 - \lambda/n) \to \lambda$ , which is the binomial mean $np = \lambda$ in the limit. Mean and variance agree for the Poisson because $p$ has been driven to zero, and $1-p$ with it, to $1$ .

Figure 2.33. Binomial

(100, 0.03)

pmf (bars) against the Poisson

(3)

pmf that approximates it (dashed line and points). With

n

large and

p

small the two are visually indistinguishable — the largest discrepancy anywhere is about

0.003

, at

k = 3

Method 2.34 (When a Poisson model is appropriate). Before fitting a Poisson, check the assumptions behind the limit:

Counts, not measurements. $X$ must be a count of occurrences in a fixed window of time, length, area or volume.
Constant rate. The expected number of events in a window is proportional to its size, with the same constant of proportionality throughout. A call centre busier at $9$ am than at $3$ am violates this unless you model the hours separately.
Independence. Events in disjoint windows are independent, and one occurrence neither encourages nor inhibits another. Contagious diseases and traffic accidents in a pile-up both fail here.
No simultaneity. In a sufficiently short window the chance of two or more events is negligible compared with the chance of one.
Empirical check. The sample mean and sample variance should be close. If the variance is much larger — overdispersion, the usual outcome — the events are clustering and a negative binomial model normally fits better.

Proposition 2.35 (Sums of independent Poissons). If $X \sim \text{Poisson}(\lambda_1)$ and $Y \sim \text{Poisson}(\lambda_2)$ are independent, then $X + Y \sim \text{Poisson}(\lambda_1 + \lambda_2)$ .

Proof. Condition on the total. For $k \ge 0$ , decomposing over the ways $X + Y = k$ and using independence,

P(X+Y = k) = \sum_{j=0}^{k} P(X=j)P(Y=k-j) = \sum_{j=0}^{k} \frac{e^{-\lambda_1}\lambda_1^j}{j!}\cdot\frac{e^{-\lambda_2}\lambda_2^{k-j}}{(k-j)!}.

Factor out $e^{-(\lambda_1+\lambda_2)}/k!$ and multiply and divide by $k!$ inside the sum:

= \frac{e^{-(\lambda_1+\lambda_2)}}{k!}\sum_{j=0}^{k}\binom{k}{j}\lambda_1^j \lambda_2^{k-j} = \frac{e^{-(\lambda_1+\lambda_2)}(\lambda_1+\lambda_2)^k}{k!}

by the binomial theorem.∎

This is the property that lets you rescale a rate. If defects occur at $2$ per metre, then the count in $3$ metres is the sum of three independent Poisson $(2)$ variables, hence Poisson $(6)$ — rescale $\lambda$ to the window you are actually asked about before doing anything else.

Example 2.36 (A Poisson probability, and a rescaled window). Emails arrive at a rate of $\lambda = 4$ per hour. Find the probability of exactly $2$ emails in one hour, and the probability of no emails in a $15$ -minute period.

Solution.

For one hour, $P(X = 2) = \dfrac{e^{-4}4^2}{2!} = 8e^{-4} \approx 8(0.0183156) \approx 0.1465$ .
A quarter of an hour is a quarter of the window, so the rate rescales to $\lambda' = 4 \times \tfrac14 = 1$ .
$P(\text{no emails in 15 min}) = e^{-1} \approx 0.3679$ .
Sanity check by the sum rule: four independent quarter-hours each empty has probability $(e^{-1})^4 = e^{-4}$ , which agrees with $P(X = 0)$ computed directly for the full hour ✓.

□

Example 2.37 (At least one occurrence). Accidents at an intersection occur at $\lambda = 2$ per week. Find $P(X \ge 1)$ in a given week.

Solution.

"At least one" spans infinitely many values, but its complement is the single term $P(X=0)$ .
$P(X = 0) = e^{-2}\lambda^{0}/0! = e^{-2} \approx 0.135335$ .
$P(X \ge 1) = 1 - 0.135335 = 0.864665$ .
Sanity check: with two accidents expected per week, a completely clear week should be the exception, so a value near $0.86$ is right.

□

Example 2.38 (Poisson approximation to a binomial). A component is defective with probability $p = 0.03$ , independently, and a lot contains $n = 100$ components. Approximate $P(X = 0)$ and compare with the exact binomial value.

Solution.

$n$ is large and $p$ small, so set $\lambda = np = 3$ and treat $X$ as approximately Poisson $(3)$ .
Approximation: $P(X=0) \approx e^{-3} \approx 0.049787$ .
Exact: $P(X = 0) = (0.97)^{100} \approx 0.047553$ .
The absolute error is about $0.0022$ — small, and the approximation replaces a $100$ th power by a single exponential. The error is of order $\lambda^{2}/n$ , so it shrinks as $n$ grows with $\lambda$ fixed.

□

Pitfall. $\lambda$ and $p$ are not interchangeable. $p$ is a probability, so $0 \le p \le 1$ ; $\lambda$ is a rate, an expected count, and can be any positive number. Seeing " $\lambda = 3$ " and computing $3^k(1-3)^{n-k}$ is a category error. Equally, $\lambda$ is attached to a window: a rate of $2$ per week is not the parameter to use for a question about a month.

Exercises for §2.4 →

2.5The Geometric Distribution and Memorylessness

The binomial fixes the number of trials and lets the number of successes be random. Turn that around — fix the number of successes at one, and let the number of trials be random — and you get a waiting time.

Definition 2.39 (Geometric distribution). Perform independent Bernoulli $(p)$ trials with $0 < p \le 1$ , and let $X$ be the index of the first success. Then $X$ has the geometric distribution with parameter $p$ :

P(X = k) = (1-p)^{k-1} p, \qquad k = 1, 2, 3, \ldots.

Notation. Two conventions are in circulation. The one above counts trials up to and including the first success, so $X \in \{1,2,3,\ldots\}$ and $E(X) = 1/p$ . The other counts the failures before the first success, giving $Y = X - 1 \in \{0,1,2,\ldots\}$ and $E(Y) = (1-p)/p$ . The variance is the same for both, since they differ by a constant. Software differs: check which one a function implements before trusting its output. This chapter uses the trial-counting convention throughout.

The pmf reads directly off the experiment: for the first success to be on trial $k$ , the first $k-1$ trials must all fail — probability $(1-p)^{k-1}$ by independence — and the $k$ th must succeed, probability $p$ . There is no binomial coefficient because there is only one arrangement.

Proposition 2.40 (The geometric tail). If $X$ is geometric with parameter $p$ , then for every integer $n \ge 0$ ,

P(X > n) = (1-p)^n,

and consequently $F_X(n) = P(X \le n) = 1 - (1-p)^n$ . In particular the probabilities sum to $1$ .

Proof. The event $\{X > n\}$ says the first $n$ trials all failed, which by independence has probability $(1-p)^n$ — no summation required. The cdf is the complement. Letting $n \to \infty$ , $(1-p)^n \to 0$ because $0 \le 1 - p < 1$ , so $P(X = \infty) = 0$ and the pmf accounts for all the mass.∎

Theorem 2.41 (Mean and variance of the geometric). If $X$ is geometric with parameter $p$ then

E(X) = \frac{1}{p}, \qquad \text{Var}(X) = \frac{1-p}{p^2}.

Proof. Write $q = 1 - p$ . For a non-negative integer-valued $X$ the tail-sum identity $E(X) = \sum_{n \ge 0} P(X > n)$ holds, and by Proposition The geometric tail this is a geometric series:

E(X) = \sum_{n=0}^{\infty} q^n = \frac{1}{1-q} = \frac{1}{p}.

For the variance use the factorial moment again. Differentiating the geometric series $\sum_{k \ge 0} q^k = (1-q)^{-1}$ twice with respect to $q$ gives $\sum_{k \ge 2} k(k-1) q^{k-2} = 2(1-q)^{-3}$ , so

E[X(X-1)] = \sum_{k=1}^{\infty} k(k-1) q^{k-1} p = pq\sum_{k=2}^{\infty}k(k-1)q^{k-2} = pq \cdot \frac{2}{p^3} = \frac{2q}{p^2}.

Then $E(X^{2}) = E[X(X-1)] + E(X) = \dfrac{2q}{p^{2}} + \dfrac{1}{p}$ , and

\text{Var}(X) = \frac{2q}{p^2} + \frac{1}{p} - \frac{1}{p^2} = \frac{2q + p - 1}{p^2} = \frac{2q - q}{p^2} = \frac{q}{p^2},

using $p - 1 = -q$ .∎

$E(X) = 1/p$ is the formula everyone remembers and it is the one worth sanity-checking against: if one trial in five succeeds, you wait five trials on average. Note how fast the variance grows as $p$ shrinks — at $p = 0.01$ the mean is $100$ and the standard deviation is about $99.5$ , so waiting times of this kind are wildly variable, and the mean alone is a poor summary.

Memorylessness

Theorem 2.42 (Memorylessness of the geometric). Let $X$ be geometric with parameter $p$ . Then for all integers $m, n \ge 0$ ,

P(X > m + n \mid X > m) = P(X > n).

Conversely, the geometric is the only distribution on $\{1,2,3,\ldots\}$ with this property.

Proof. Since $\{X > m+n\} \subseteq \{X > m\}$ , the intersection of the two events is $\{X > m+n\}$ itself. By the definition of conditional probability and Proposition The geometric tail,

P(X > m+n \mid X > m) = \frac{P(X > m+n)}{P(X>m)} = \frac{(1-p)^{m+n}}{(1-p)^m} = (1-p)^n = P(X > n),

the division being legitimate because $P(X > m) = (1-p)^m > 0$ .

For the converse, suppose $G(n) = P(X > n)$ satisfies $G(m+n) = G(m)G(n)$ for all $m,n \ge 0$ with $G(1) < 1$ . Taking $m = n = \cdots = 1$ and inducting gives $G(n) = G(1)^n$ . Setting $p = 1 - G(1)$ yields $P(X > n) = (1-p)^n$ , whose differences $P(X = k) = G(k-1) - G(k) = (1-p)^{k-1}p$ are exactly the geometric pmf.∎

Intuition. A coin has no memory. Ten tails in a row do not make a head "due" on the eleventh flip, and the number of further flips you must wait has exactly the distribution it had at the start. Memorylessness is the formal statement of that, and it is the mathematical refutation of the gambler's fallacy.

Be careful about what it does not say. Waiting a long time is unlikely in advance — $P(X > 10) = (1-p)^{10}$ is small. What memorylessness says is that given you have already waited that long, the future looks brand new. Surprise about the past is not evidence about the future.

Pitfall. Memorylessness is a property of independent trials with a constant $p$ , and nothing else. A lightbulb that wears out, a machine whose failure probability rises with age, a patient whose risk grows over time — none of these are memoryless, and modelling them as geometric will systematically understate the chance of imminent failure. Among discrete distributions the geometric is the unique memoryless one; among continuous ones it is the exponential, and no others.

Example 2.43 (Free throws). A player sinks each free throw independently with probability $p = 0.25$ . Let $X$ be the number of the shot on which she records her first make. Find $P(X = 3)$ , $P(X > 4)$ , $E(X)$ and $\text{Var}(X)$ .

Solution.

$P(X = 3) = (0.75)^2(0.25) = 0.5625 \times 0.25 = 0.140625$ — two misses, then a make.
$P(X > 4) = (0.75)^4 = 0.31640625$ : still no make after four attempts.
$E(X) = 1/0.25 = 4$ shots on average.
$\text{Var}(X) = (1-p)/p^{2} = 0.75/0.0625 = 12$ , so $\sigma = \sqrt{12} \approx 3.46$ — nearly as large as the mean.
Sanity check on memorylessness: given she has missed four, the chance she needs more than three further shots is $P(X > 3) = 0.75^3 \approx 0.4219$ , the same as it was before she started.

□

Exercises for §2.5 →

2.6Negative Binomial and Hypergeometric

Two variations account for most of the remaining discrete problems you will meet. One relaxes the geometric's "first success" to " $r$ th success"; the other relaxes the binomial's independence by sampling from a finite pool.

Definition 2.44 (Negative binomial distribution). Perform independent Bernoulli $(p)$ trials and let $X$ be the index of the trial on which the $r$ th success occurs. Then $X$ has the negative binomial distribution with parameters $r$ and $p$ :

P(X = k) = \binom{k-1}{r-1}(1-p)^{k-r}p^{r}, \qquad k = r, r+1, r+2, \ldots.

Proof. The formula deserves its derivation. The event $\{X = k\}$ requires two things at once: trial $k$ is a success, and exactly $r-1$ of the first $k-1$ trials are successes. These concern disjoint sets of trials and so are independent. The first has probability $p$ . The second is a binomial event on $k-1$ trials, with probability $\binom{k-1}{r-1}p^{r-1}(1-p)^{k-r}$ . Multiplying gives $\binom{k-1}{r-1}p^r(1-p)^{k-r}$ .∎

The constraint that the last trial is a success is what makes the coefficient $\binom{k-1}{r-1}$ rather than $\binom{k}{r}$ — a very common slip. Setting $r = 1$ recovers the geometric, as it must.

Proposition 2.45 (Mean and variance of the negative binomial). If $X$ is negative binomial with parameters $r$ and $p$ , then

E(X) = \frac{r}{p}, \qquad \text{Var}(X) = \frac{r(1-p)}{p^2}.

Proof. Decompose the waiting time into stages. Let $W_1$ be the number of trials up to the first success, $W_2$ the number of further trials from there to the second success, and so on, so that

X = W_1 + W_2 + \cdots + W_r.

Because the trials are independent with constant $p$ , each $W_i$ is geometric $(p)$ — this is memorylessness in action, since after the $(i-1)$ th success the process restarts — and the $W_i$ are independent of one another, as they depend on disjoint blocks of trials.

Linearity gives $E(X) = r \cdot 1/p$ , and Theorem Variance of a sum of independent variables gives $\text{Var}(X) = r(1-p)/p^{2}$ .∎

Example 2.46 (Waiting for the third make). A shooter makes each free throw independently with probability $p = 0.5$ . Let $X$ be the shot on which she records her third make. Find $P(X = 5)$ and $E(X)$ .

Solution.

Here $r = 3$ , $k = 5$ . The fifth shot must be a make, and exactly $2$ of the first $4$ must be makes.
$P(X=5) = \binom{4}{2}(0.5)^3(0.5)^{2} = 6(0.5)^5 = \tfrac{6}{32} = 0.1875$ .
$E(X) = r/p = 3/0.5 = 6$ .
Sanity check: $5$ sits just below the mean of $6$ , and it is in fact the modal value together with $4$ — a probability near $0.19$ for the single most likely outcome of a spread-out distribution is plausible.

□

Sampling without replacement

Definition 2.47 (Hypergeometric distribution). A population of $N$ items contains $K$ successes and $N-K$ failures. Draw $n$ items without replacement, all subsets equally likely, and let $X$ be the number of successes drawn. Then $X$ is hypergeometric:

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

for $\max(0, n-(N-K)) \le k \le \min(n, K)$ .

The formula is a counting argument, not a product of probabilities: of the $\binom{N}{n}$ equally likely samples, the ones with exactly $k$ successes are obtained by choosing $k$ of the $K$ successes and $n-k$ of the $N-K$ failures.

Proposition 2.48 (Mean and variance of the hypergeometric). With $p = K/N$ the population success proportion,

E(X) = np, \qquad \text{Var}(X) = np(1-p)\cdot\frac{N-n}{N-1}.

Proof. (Mean.) Let $X_i = 1$ if the $i$ th item drawn is a success. By symmetry every item is equally likely to appear in position $i$ , so $P(X_i = 1) = K/N = p$ for every $i$ , and $E(X) = \sum_i E(X_i) = np$ by linearity — which, as in the card example, does not care that the $X_i$ are dependent.

(Variance.) The $X_i$ are not independent, so the cross terms survive and the calculation of the covariance is the extra work; carrying it out gives the stated factor. We quote the result.∎

The mean is exactly the binomial mean: sampling without replacement does not bias the count. The variance, however, is smaller, by the finite population correction $\frac{N-n}{N-1}$ . That factor is at most $1$ , equals $1$ when $n = 1$ , and drops to $0$ when $n = N$ — as it must, because a census has no sampling variability at all. Sampling without replacement is more precise than sampling with replacement, because it cannot waste draws on items it has already seen.

Corollary 2.49 (Binomial approximation to the hypergeometric). If $n/N$ is small, the correction factor is close to $1$ and the hypergeometric probabilities are close to binomial probabilities with $p = K/N$ . The usual working rule is $n \le 0.1N$ .

Example 2.50 (Defective fuses). A box holds $20$ fuses, $4$ of them defective. Three are drawn without replacement. Find the probability that exactly one is defective, and $E(X)$ .

Solution.

Here $N = 20$ , $K = 4$ , $n = 3$ , $k = 1$ .
$\binom{4}{1} = 4$ , $\binom{16}{2} = 120$ , $\binom{20}{3} = 1140$ .
$P(X = 1) = \dfrac{4 \times 120}{1140} = \dfrac{480}{1140} = \dfrac{8}{19} \approx 0.421$ .
$E(X) = n K/N = 3 \times 4/20 = 0.6$ .
Compare the binomial: $\binom{3}{1}(0.2)(0.8)^2 = 3(0.2)(0.64) = 0.384$ . The sample is $15\%$ of the population, above the $10\%$ rule, and the two values differ by nearly $0.04$ — visible evidence that the approximation is being pushed too far here.

□

Exercises for §2.6 →

2.7Choosing a Distribution

Every distribution in this chapter is built from Bernoulli trials or a limit of them, so the differences come down to three questions: what is fixed, what is random, and are the trials independent?

Method 2.51 (Identifying the distribution).

Is the quantity a count of successes, or a count of trials? Successes $\Rightarrow$ binomial or hypergeometric. Trials $\Rightarrow$ geometric or negative binomial.
If it is a count of successes: is the number of trials fixed in advance? If yes, and the draws are independent with constant $p$ — sampling with replacement, or from an effectively infinite population — it is binomial. If the draws are made without replacement from a finite pool, it is hypergeometric.
If it is a count of trials: how many successes are you waiting for? One $\Rightarrow$ geometric. Exactly $r$ $\Rightarrow$ negative binomial.
Is there no list of trials at all — only a rate over a window of time, length, area or volume? Then it is Poisson, with $\lambda$ rescaled to the window in the question.
Check the boundary cases. $n$ large with $p$ small and $np$ moderate: the Poisson approximates the binomial. Sample no more than $10\%$ of the population: the binomial approximates the hypergeometric.

The tells in the wording are reliable. "Out of $20$ patients, how many respond?" fixes $n = 20$ and counts successes: binomial. "How many patients must be screened to find $3$ who qualify?" counts trials until the third success: negative binomial. "How many earthquakes next decade?" has no trials at all, only a rate: Poisson. "Five cards from a deck" is drawing from a small finite pool: hypergeometric.

|---|---|---|---|---|---|

| Bernoulli $(p)$ | one trial | success or not | $\{0,1\}$ | $p$ | $p(1-p)$ |

| Binomial $(n,p)$ | $n$ trials | number of successes | $\{0,\ldots,n\}$ | $np$ | $np(1-p)$ |

| Poisson $(\lambda)$ | a window | number of events | $\{0,1,2,\ldots\}$ | $\lambda$ | $\lambda$ |

| Geometric $(p)$ | one success | number of trials | $\{1,2,\ldots\}$ | $1/p$ | $(1-p)/p^{2}$ |

| NegBinom $(r,p)$ | $r$ successes | number of trials | $\{r,r+1,\ldots\}$ | $r/p$ | $r(1-p)/p^{2}$ |

| Hypergeom $(N,K,n)$ | $n$ draws, no replacement | number of successes | see above | $nK/N$ | $np(1-p)\frac{N-n}{N-1}$ |

Example 2.52 (Reading the distribution off the wording). Classify each scenario, and give the parameters.

A. A quiz has $10$ true/false questions and a student guesses every one. How many does she get right?

B. A page of a manuscript averages $0.5$ typos. What is the chance a page is clean?

C. How many pages must an editor read to find the first typo?

D. A box of $20$ fuses contains $4$ defectives; three are drawn without replacement. How many are defective?

Solution.

A — binomial, $B(10, 0.5)$ . A fixed number of independent trials with constant $p$ , counting successes. The mean is $5$ .
B — Poisson, $\lambda = 0.5$ per page. Counting events in a fixed window with no natural $n$ ; $P(X=0) = e^{-0.5} \approx 0.6065$ .
C — geometric on pages, with $p = P(\text{a page has at least one typo}) = 1 - e^{-0.5} \approx 0.3935$ . The expected wait is $1/p \approx 2.54$ pages. Note the two-step reading: a Poisson calculation supplies the $p$ that a geometric then consumes.
D — hypergeometric, $N=20$ , $K=4$ , $n=3$ , as computed earlier; the binomial would give $0.384$ against the correct $8/19 \approx 0.421$ .
The four tells, in order: fixed count of trials; rate over an interval; wait until the first success; draw from a small finite pool without replacement.

□

Summary. The load-bearing results of this chapter, with the hypotheses they need.

A pmf is any non-negative function summing to $1$ over a countable support; the cdf $F(x) = P(X \le x)$ is its running total, and $p_X(x)$ is the size of $F$ 's jump at $x$ . For discrete $X$ , $P(X < x) \ne P(X \le x)$ .
Linearity of expectation. $E(aX + bY + c) = aE(X) + bE(Y) + c$ for any $X, Y$ with finite means on a common sample space. No independence needed — this is what makes the indicator decomposition work.
Variance identities. $\text{Var}(X) = E(X^{2}) - [E(X)]^2$ and $\text{Var}(aX+b) = a^{2}\text{Var}(X)$ , both unconditionally. But $\text{Var}(X+Y) = \text{Var}(X) + \text{Var}(Y)$ requires independence (or at least zero covariance); in general the cross term $2\,\text{Cov}(X,Y)$ is there.
Binomial $B(n,p)$ : $P(X=k) = \binom{n}{k}p^k(1-p)^{n-k}$ , needing binary outcomes, independence, fixed $n$ and constant $p$ . Mean $np$ (needs only constant $p$ ), variance $np(1-p)$ (needs independence). Symmetric at $p = 0.5$ , right-skewed below it.
Poisson $(\lambda)$ : $P(X=k) = e^{-\lambda}\lambda^k/k!$ , the $n \to \infty$ , $np \to \lambda$ limit of the binomial. Mean $=$ variance $= \lambda$ , which is a testable claim; overdispersed data violates it. Independent Poissons add, so $\lambda$ rescales with the window.
Geometric $(p)$ : $P(X=k) = (1-p)^{k-1}p$ on $k \ge 1$ , tail $P(X>n) = (1-p)^n$ , mean $1/p$ , variance $(1-p)/p^{2}$ . It is the unique memoryless discrete distribution, and memorylessness needs independence and constant $p$ — not true of anything that ages or wears.
Negative binomial $(r,p)$ : the $r$ th-success waiting time, a sum of $r$ independent geometrics; mean $r/p$ , variance $r(1-p)/p^{2}$ .
Hypergeometric $(N,K,n)$ : sampling without replacement. Mean $nK/N$ , the same as the binomial, but variance $np(1-p)\frac{N-n}{N-1}$ — strictly smaller. The binomial approximates it when $n \le 0.1N$ .

Exercises for §2.7 →

Common Mistakes

Using the binomial when sampling without replacement from a small population. The trials are neither independent nor identically weighted. Use the hypergeometric unless the sample is under about $10\%$ of the population.
Adding standard deviations instead of variances. Variances add for independent variables; standard deviations never do. Add the variances, then take one square root.
Assuming independence for a variance. $E(X+Y) = E(X)+E(Y)$ always; $\text{Var}(X+Y) = \text{Var}(X)+\text{Var}(Y)$ only when the covariance vanishes. Deciding which rule you are using is the first step, not an afterthought.
**Forgetting that $\text{Var}(X - Y) = \text{Var}(X) + \text{Var}(Y)$ ** for independent $X, Y$ . The minus sign squares away; uncertainty accumulates whether you add or subtract.
**Mixing up $P(X \le k)$ and $P(X < k)$ . ** For integer-valued $X$ , $P(X < k) = P(X \le k-1)$ , and $P(X \ge k) = 1 - P(X \le k-1)$ . Write the complement out rather than trusting a remembered form.
**Confusing $\lambda$ with $p$ . ** $p$ is a probability in $[0,1]$ ; $\lambda$ is an expected count and can exceed $1$ . Also, $\lambda$ belongs to a stated window — rescale it before answering a question about a different one.
**Using $\binom{k}{r}$ in the negative binomial pmf.** The last trial is forced to be a success, so the coefficient is $\binom{k-1}{r-1}$ over the trials that remain free.
Treating an ageing process as memoryless. Bulbs, machines and patients all have failure probabilities that change with time. The geometric model assumes constant $p$ ; without it, memorylessness — and the mean $1/p$ — is simply wrong.
Fitting a Poisson to overdispersed counts. If the sample variance greatly exceeds the sample mean, the events are clustering and the independence assumption has failed. Check mean against variance before you fit.
Reporting a mean for a highly skewed waiting time. When $p$ is small the geometric has a standard deviation nearly equal to its mean, so "on average $100$ trials" hides an enormous range.

About the practice questions. They check that you can carry out this chapter's computations correctly, and each one is graded on a single answer. They are not proof exercises: working through them confirms the mechanics, not that you could prove the results yourself. For that, re-read the statements above and try to reconstruct their proofs with the page closed.

← Foundations of Probability Continuous Random Variables →

Helpful?