M2-T1 — Discrete Random Variables and Probability Mass Functions

Learning objectives

After this lesson, you should be able to:

• Define a random variable as a function of the outcome, and distinguish the variable from its value.
• Write and check a probability mass function, and read a cumulative distribution from it.
• Use the Bernoulli, binomial and categorical distributions and say what each assumes.
• Derive the binomial distribution and use it to design a k-of-n voting rule.

The intuition

Rover's camera looks for the marker above the charging dock. One frame gives one of two outcomes: detected or not. Over five frames there are $2^5 = 32$ possible sequences, such as hit, miss, hit, hit, hit. For deciding whether the dock is really there, the sequence is more detail than we need. What matters is one number: how many frames detected the marker.

That number is a random variable. It is not random in itself and it does not vary in the way a program variable does. It is a rule that reads a number off whatever outcome occurred: the sequence above gives 4. Before the frames are taken we do not know which number we will get, but we can say how probable each one is.

The list of those probabilities is the probability mass function. Picture the one unit of probability from the last module as one kilogram of clay. The mass function says how much clay sits on each possible value: a lump on 0, a lump on 1, and so on up to 5.

The two charts already show why counting helps. A single frame is wrong 20% of the time when the marker is present and 10% of the time when it is absent. The count over five frames separates the two situations far better: the mass sits on 4 and 5 in one case and on 0 and 1 in the other.

Write a capital letter for the random variable (the rule) and a small letter for a value it can take. “P(X = 3)” reads: the probability that the count X comes out as 3.

Definitions

Random variable $X$

A function that assigns a number to every outcome: $X : \Omega \to \mathbb{R}$. It is discrete when its possible values can be listed.

Value $x$

One number that $X$ can produce. $\{X = x\}$ is an event: the set of outcomes that the rule maps to $x$.

Probability mass function $p_X(x)$

The probability of each value: $p_X(x) = P(X = x)$. Often written $p(x)$ when the variable is clear.

Cumulative distribution $F_X(x)$

The probability of a value at or below $x$: $F_X(x) = P(X \le x)$. It rises from 0 to 1 in steps.

Support

The set of values with non-zero probability.

Because the events $\{X = x\}$ for different $x$ are disjoint and together cover the sample space, the axioms of the last module turn into two conditions on a mass function, and a rule for any event about $X$:

Three distributions to know

The symbol $\binom{n}{k} = \frac{n!}{k!\,(n-k)!}$ reads “n choose k”: the number of ways to pick which $k$ of the $n$ trials are the successes. A Bernoulli variable is a binomial with $n = 1$, and a categorical variable with two categories is a Bernoulli.

Derivation: the binomial distribution

Let $X$ be the number of detections in $n$ frames. Two assumptions are made, and both will matter later: every frame detects with the same probability $p$, and the frames are independent, meaning that the result of one tells you nothing about another. M3-T3: Independence and Conditional Independence defines independence precisely; the property used here is that the probability of a whole sequence is the product of the probabilities of its parts.

1. $$P(\text{hit, hit, miss, hit, miss}) = p \cdot p \cdot (1-p) \cdot p \cdot (1-p) = p^{3}(1-p)^{2}$$

   Independence: multiply the probability of each frame’s result. The example has $n = 5$ and $k = 3$ hits.

2. $$P(\text{any one sequence with } k \text{ hits}) = p^{k}(1-p)^{n-k}$$

   The product does not depend on the order of the factors, so every sequence with the same number of hits has the same probability.

3. $$\#\{\text{sequences with } k \text{ hits}\} = \binom{n}{k}$$

   A sequence is fixed by choosing which $k$ of the $n$ positions are hits.

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

   The event $\{X = k\}$ is the union of those sequences. They are disjoint (two different sequences cannot both occur), so axiom 3 adds their equal probabilities.

5. $$\sum_{k=0}^{n} \binom{n}{k}\, p^{k}(1-p)^{n-k} = \bigl(p + (1-p)\bigr)^{n} = 1$$

   Check of normalization, by the binomial theorem. The masses use up exactly the unit of probability.

From the mass function to a voting rule

A k-of-n rule declares the marker present when at least $k$ of $n$ frames detect it. Its probability of firing is the mass at and above $k$:

Counting over several independent trials turns a mediocre yes-or-no sensor into a reliable one. The binomial distribution says exactly how reliable, and the word “independent” says when the promise holds.

A worked example

The marker detector fires on a frame with probability 0.8 when the marker is in view, and with probability 0.1 when it is not (a false alarm). Rover uses a 3-of-5 rule. How often does the rule fire in each case?

1. Marker present, mass function. $X \sim \text{Binomial}(5, 0.8)$. For example $P(X = 3) = \binom{5}{3}\,0.8^{3}\,0.2^{2} = 10 \times 0.512 \times 0.04 = 0.2048$. The six masses are 0.0003, 0.0064, 0.0512, 0.2048, 0.4096 and 0.3277.
2. Marker present, rule fires. $P(X \ge 3) = 0.2048 + 0.4096 + 0.3277 = 0.9421$. The rule misses a marker that is there about 6 times in 100, against 20 in 100 for a single frame.
3. Marker absent. $X \sim \text{Binomial}(5, 0.1)$: $P(X \ge 3) = 0.0081 + 0.00045 + 0.00001 = 0.0086$. False alarms fall from 10 in 100 to fewer than 1 in 100.
4. The trade-off. A stricter rule, 4-of-5, cuts false alarms to 0.0005 but detects a real marker only 73.7% of the time. A looser rule, 2-of-5, detects 99.3% but raises false alarms to 8.1%. The threshold is a design choice between two kinds of error, made with these numbers.
5. Check by simulation. 20 000 simulated groups of five frames give 0.9405 for the present case, within sampling error of 0.9421 (the standard error is 0.0017).

from robotprob import Rng, binomial_pmf

n, p_det, p_false = 5, 0.8, 0.1
for k in range(n + 1):
    print(k, round(binomial_pmf(k, n, p_det), 5), round(binomial_pmf(k, n, p_false), 5))

def fires(k_min, p):                      # P(X >= k_min)
    return sum(binomial_pmf(k, n, p) for k in range(k_min, n + 1))

for k_min in (2, 3, 4):
    print(k_min, 'of 5: detection =', round(fires(k_min, p_det), 4), ' false alarm =', round(fires(k_min, p_false), 4))

rng = Rng(5)                              # check the 3-of-5 detection rate by simulation
trials = 20000
hits = sum(1 for _ in range(trials) if sum(1 for _ in range(n) if rng.bernoulli(p_det)) >= 3)
print('simulated 3 of 5 detection =', round(hits / trials, 4))

0 0.00032 0.59049
1 0.0064 0.32805
2 0.0512 0.0729
3 0.2048 0.0081
4 0.4096 0.00045
5 0.32768 1e-05
2 of 5: detection = 0.9933  false alarm = 0.0815
3 of 5: detection = 0.9421  false alarm = 0.0086
4 of 5: detection = 0.7373  false alarm = 0.0005
simulated 3 of 5 detection = 0.9405

In robotics

Debouncing and voting

Bumpers, cliff sensors, fiducial detectors, “person present” classifiers and loop-closure candidates are all confirmed by some k-of-n rule before the robot acts on them. The binomial gives the detection and false-alarm rates of the rule, with one caution that the derivation made explicit: it assumes independent trials. Consecutive camera frames taken 30 ms apart share the same glare, the same blur and the same occlusion. Their errors come in runs, so the real rule is worse than the formula says. Either space the trials out or measure the rule's rates directly.

A belief over cells is a categorical distribution

A grid localizer stores one number per cell, non-negative and summing to 1. That is the parameter vector of a categorical distribution, and “the robot's cell” is the random variable. The histogram filter of M6-T2: Histogram Filters and Grid Localization is nothing more than two operations on this vector.

An occupancy cell is a Bernoulli variable

Each cell of an occupancy grid map is occupied or free, with a single parameter $p$. Mapping is the estimation of that parameter for every cell from range beams (M10-T1: Occupancy Grids and the Binary Bayes Filter; the SLAM course has the practical view in Occupancy Grid Mapping).

Counts in estimation algorithms

The number of inliers that RANSAC finds for a wrong model, the number of packets lost in a burst of 100, and the number of beams of a scan that return nothing are binomial-like counts. Knowing their distribution tells you what count is ordinary and what count is a symptom (see Robust Estimation and RANSAC).

Quantized sensors

A wheel encoder reports a whole number of ticks and an analogue-to-digital converter a whole number of counts. Their outputs are discrete random variables even though the quantity behind them is continuous. The next lesson deals with the continuous side.

Common misconceptions

Key takeaways

1. A random variable is a rule that assigns a number to each outcome. A discrete one has a list of possible values.
2. Its probability mass function gives the probability of each value: non-negative masses that sum to 1. The probability of any set of values is the sum of their masses.
3. Bernoulli: one yes-or-no trial. Binomial: the number of successes in n independent trials with equal probability. Categorical: one trial with several outcomes.
4. The binomial mass is (n choose k) p^k (1 − p)^(n − k): the probability of one sequence times the number of sequences.
5. A k-of-n vote trades missed detections against false alarms. The binomial quantifies the trade, and it is optimistic when the trials are not independent.

References and further reading

Each source is marked free or paid. Free to read does not mean free to reuse: the course resources page lists every source with its licence.

• J. Tsitsiklis and P. Jaillet, MIT RES.6-012 Introduction to Probability , lectures 5 to 7 (discrete random variables). Free videos and notes, licence CC BY-NC-SA 4.0.
• J. Blitzstein and J. Hwang, Introduction to Probability, 2nd edition, CRC Press, 2019 , chapter 3 (random variables and their distributions). Free to read online; the book is copyrighted.
• C. Piech, Probability for Computer Scientists (Stanford CS109 course reader) , part 2: random variables, binomial distribution. Free to read online.
• S. Thrun, W. Burgard and D. Fox, Probabilistic Robotics, MIT Press, 2005, section 2.2 (discrete and continuous random variables). Paid book.

Knowledge check

Three questions. Write an answer, then reveal the explanation. Your answers stay in your browser.

What’s next

Counts and cell indices are discrete. Distances, angles and times are not: they can take any value in a range. The next lesson shows what replaces the mass function when no single value can carry any mass.

Related content

Nothing below is required to finish this lesson.

Other courses on this site treat neighbouring topics from their own angle:

• UAV M3-T2: Gaussian distributions and covariance
• Perception P1-T5: Noise, Uncertainty, Occlusion and Ambiguity