Discrete random variables

Balls drop through ten rows of pegs, bouncing left or right at each one. Watch where a thousand of them pile up.

A number for each outcome

Follow one ball. At each of the ten pegs it goes left or right, so its trip is a list such as right, left, left, right, and so on: one of $2^{10}=1024$ possible paths. That path is the outcome. The bin it lands in is a single number, the count of rights on the path.

A rule that attaches a number to each outcome is a random variable. I write random variables as capital letters, like $X$, and the values they can take as small letters, like $x$. Here $X$ is the number of rights, and its values are $0,1,\dots,10$.

A random variable whose values can be listed one by one, like a count, is discrete. Its shape is given by the probability mass function, or pmf, which says how likely each value is:

Every ball lands in some bin, so the pmf adds up to 1 over all the values: $\sum_x p_X(x)=1$.

One run, or the long run

Watch the clip again. After 20 balls the bars are ragged: some bins are empty, one bar may stand far above its dot. After 1000 balls the bars sit on the dots.

The dots are the pmf. A pmf does not describe one run of 20 balls; it describes the shares in the long run, as every probability in What probability measures does. The middle bin’s share is $0.2461$. Of 20 balls, about $20\times0.2461=4.9$ should land there, give or take about $\sqrt{20\times0.2461\times0.7539}=1.9$. Three balls or seven would be ordinary. The clip’s first 20 put 6 there, a share of 0.300, and its 1000 put 265 there, 0.265.

After the clip, drag the tilt. At $p=0.3$ the dots move left and peak at 3; at $0.7$ they peak at 7. The 1000 balls follow closely but not exactly: at $0.3$ the bars at 2 and 3 are 0.241 and 0.238, and at $0.7$ the bars at 7 and 8 are 0.243 and 0.246, so a neighbour of the peak can come out a hair taller. At $0.1$ more balls land in bin 1 than in any other: 0.388 of them, against $0.3874$ in the long run.

Why the board makes this shape

Take one path with $k$ rights and $10-k$ lefts, in a given order. The bounces do not affect each other: each is independent of the others. So the chance of that one path is a product, $p$ for each right and $1-p$ for each left:

Every path with $k$ rights has this same chance, whatever the order. How many such paths are there? A path is fixed by choosing which $k$ of the 10 pegs send the ball right, so there are $\binom{10}{k}$ of them, the binomial coefficient of Counting. Add the equal chances of all these paths:

At $p=\tfrac12$ every path has chance $1/1024$, and bin 5 collects $\binom{10}{5}=252$ paths: $252/1024=0.2461$.

The same reasoning works for any number of tries $n$ with chance $p$ of success in each, the tries independent. The number of successes $X$ follows the binomial law, written $\mathrm{Bin}(n,p)$:

With a single try, $n=1$, the count is 1 with chance $p$ and 0 with chance $1-p$. That one-try variable is called a Bernoulli variable. A binomial count is a sum of $n$ independent Bernoulli variables, one per peg.

The distribution function

Often the question is not “exactly 3?” but “at most 3?”. The distribution function of $X$ answers it:

It climbs in steps, one step at each value, each step as tall as the pmf there, from 0 on the far left to 1 on the far right. For the board at $p=\tfrac12$, the chance of at most 4 rights is

The chance of more than 4 is then $1-F_X(4)$, by the complement rule.

Two more shapes

Waiting for the first success. Roll a die until the first six. Let $X$ be the number of rolls it takes. For $X=k$ the first $k-1$ rolls must miss and the $k$-th must hit, so with chance $p$ of a hit on each independent roll,

This is the geometric law, $\mathrm{Geom}(p)$. Its pmf is largest at $k=1$ and falls by the same factor $1-p$ at each step. It has no last value: any number of misses in a row is possible, only less and less likely.

All values equally likely. A fair die’s face is 1 to 6, each with chance $\tfrac16$. A variable that takes $m$ values, each with chance $1/m$, follows the discrete uniform law.

Worked example

1. Guessing a quiz. A quiz has 10 questions, each with 4 answers to pick from. You guess every answer at random, independently. The number right, $X$, follows $\mathrm{Bin}(10,\tfrac14)$:

These add to $F_X(4)=0.9219$. So the chance of passing with 5 or more right is $1-0.9219=0.0781$, about one in 13.

The chance of at least one right answer is easier through the complement. All ten wrong has chance $0.75^{10}$, so $\Pr\{X\ge1\}=1-0.75^{10}=0.9437$.

2. Waiting for a six. Roll a die until the first six. The chance that it comes within six rolls is one minus the chance that all six rolls miss:

The same complement works for every $k$: $F_X(k)=1-(1-p)^k$ for the geometric law.

Try it yourself. On the board at $p=\tfrac12$, what is the chance of exactly 5 rights? $252/1024=0.2461$, the middle bin.

Where you’ll meet this

Counts of defects. A machine makes parts that are faulty with chance $p$, each independently. The number of faulty parts in a box of $n$ follows $\mathrm{Bin}(n,p)$, and a factory sets its checks by it.

Data links. A packet sent over a noisy link arrives or is lost. Out of $n$ packets, the number lost is binomial, and the number of tries until one gets through is geometric. Bit errors in a word of $n$ bits follow the same binomial law.

Retries. Any “try until it works” loop, from a phone redialling to a program retrying a server, counts its attempts with the geometric law.

Reference card