M1-T2 — Events, Sample Spaces and the Rules of Probability

Learning objectives

After this lesson, you should be able to:

• Describe an uncertain situation with a sample space of mutually exclusive, exhaustive outcomes.
• Express a question about a robot as an event, a set of outcomes.
• State the three axioms of probability and say what each means physically.
• Derive and use the complement rule, the addition rule for overlapping events and the union bound.

The intuition

Think of probability as one unit of belief that has to be shared out among everything that could happen. Nothing can receive a negative share, and the shares must use up exactly the whole unit, because something happens.

Take Rover's drive to the dock from the previous lesson. Watching 200 runs, the team sorted each one into exactly one of five bins:

Three ideas are already in this picture.

• The five bins are the outcomes. They do not overlap (a run cannot be both “left” and “short” if we define the bins carefully), and together they cover every run. One and only one of them happens.
• A question with a yes or no answer is an event: a set of outcomes. “Missed sideways” is the set {left, right}. “Did not dock” is {left, right, short, long}.
• The probability of an event is the total share of its outcomes. That is all “adding probabilities” means, and it is safe exactly when the pieces being added do not overlap.

Most mistakes with probability are mistakes about overlap: adding the probabilities of events that can happen together, or forgetting an outcome so that the shares no longer use up the whole unit.

Definitions

Experiment

Any process whose result is not known in advance: one drive to the dock, one range reading, switching the robot on at an unknown place.

Outcome $\omega$

One complete result of the experiment, at the level of detail you chose to record.

Sample space $\Omega$

The set of all outcomes. Its members must be mutually exclusive (no two happen together) and exhaustive (one of them always happens).

Event $A$

A subset of $\Omega$. The event “happens” when the outcome is one of its members.

$A^{c}$ (complement)

Everything in $\Omega$ that is not in $A$: “$A$ does not happen”.

$A \cup B$ (union)

Outcomes in $A$ or in $B$ or in both: “at least one happens”.

$A \cap B$ (intersection)

Outcomes in both: “both happen”. If $A \cap B = \varnothing$ the events are disjoint (mutually exclusive).

Partition

A collection of events that are pairwise disjoint and whose union is $\Omega$. The outcomes themselves are the finest partition.

A probability $P$ assigns a number to every event and satisfies three axioms (due to Kolmogorov, 1933):

What each one says about a robot:

Notice what the axioms do not say: they do not tell you what the numbers are. Whether the probability of docking is 0.62 comes from data (a frequency) or from a model (a belief). The axioms only guarantee that whatever numbers you use are consistent with each other.

Derivation: the rules that follow from the axioms

Four rules are used constantly. None needs to be memorized as a separate fact: each follows from the axioms in a few steps.

The complement rule

1. $$A \cup A^{c} = \Omega, \qquad A \cap A^{c} = \varnothing$$

   By definition the complement holds exactly the outcomes that $A$ does not. Together they are everything, and they share nothing.

2. $$P(A) + P(A^{c}) = P(A \cup A^{c})$$

   Axiom 3, because the two events are disjoint.

3. $$P(A) + P(A^{c}) = P(\Omega) = 1$$

   Their union is the sample space, and axiom 2 gives its probability.

4. $$P(A^{c}) = 1 - P(A)$$

   Rearranged. It is often much easier to compute the probability that something does not happen.

Two quick consequences: taking $A = \Omega$ gives $P(\varnothing) = 0$, and since $P(A^{c}) \ge 0$ every probability satisfies $P(A) \le 1$.

A larger event is at least as probable

1. $$A \subseteq B \;\Rightarrow\; B = A \cup (B \cap A^{c})$$

   Split $B$ into the part inside $A$ and the part outside. The two parts are disjoint.

2. $$P(B) = P(A) + P(B \cap A^{c}) \ge P(A)$$

   Axiom 3, then axiom 1 for the second term. This property is called monotonicity.

The addition rule for events that may overlap

1. $$A \cup B = A \,\cup\, (B \cap A^{c})$$

   The union is all of $A$ plus the part of $B$ that lies outside $A$. These are disjoint.

2. $$P(A \cup B) = P(A) + P(B \cap A^{c})$$

   Axiom 3, because the two parts are disjoint.

3. $$B = (B \cap A) \,\cup\, (B \cap A^{c}) \;\Rightarrow\; P(B \cap A^{c}) = P(B) - P(A \cap B)$$

   Split $B$ the same way and apply axiom 3 again.

4. $$P(A \cup B) = P(A) + P(B) - P(A \cap B)$$

   Substitute. When the events are disjoint the last term is zero and the rule reduces to axiom 3.

The union bound

Since $P(A \cap B) \ge 0$, dropping it can only make the right-hand side larger. Repeating the argument for more events gives:

Add probabilities only for events that cannot happen together. For events that can, subtract the overlap, or use the sum as a safe upper bound.

A worked example

Part 1: questions about a run. Use the outcome probabilities of the figure: docked 0.62, left 0.14, right 0.16, short 0.05, long 0.03. They are non-negative and sum to 1.00, so they form a valid probability.

1. Missed sideways. $A = \{\text{left}, \text{right}\}$. The outcomes are disjoint, so $P(A) = 0.14 + 0.16 = 0.30$.
2. Did not dock. The direct way adds four outcomes. The complement rule is shorter: $P(\text{docked}^{c}) = 1 - 0.62 = 0.38$.
3. Stopped at the wrong distance. $P(\{\text{short}, \text{long}\}) = 0.05 + 0.03 = 0.08$. Check: sideways 0.30 plus wrong distance 0.08 is 0.38, the same as “did not dock”, because those two events partition it.

Part 2: two sensors that can fire together. On a test course, in any one minute, Rover's bumper fires with probability 0.08 and its cliff sensor with probability 0.05. When Rover reaches a ledge with a raised lip, both fire: that happens with probability 0.02. The safety logic stops the robot if either fires. How often does it stop?

1. Wrong. $0.08 + 0.05 = 0.13$. This adds events that are not disjoint and counts the “both” minutes twice.
2. Right. $P(A \cup B) = 0.08 + 0.05 - 0.02 = 0.11$.
3. No stop. By the complement rule, $P(\text{neither}) = 1 - 0.11 = 0.89$.
4. If the overlap were unknown. The union bound still says the stop probability is at most 0.13, and monotonicity says it is at least 0.08 (the larger single event). The true 0.11 lies between.

from robotprob import Discrete

# Discrete checks the axioms: no negative share, total exactly 1.
runs = Discrete({'docked': 0.62, 'left': 0.14, 'right': 0.16, 'short': 0.05, 'long': 0.03})
print('P(missed sideways) =', round(runs.prob({'left', 'right'}), 2))
print('P(did not dock)    =', round(1 - runs.p('docked'), 2))
print('P(wrong distance)  =', round(runs.prob({'short', 'long'}), 2))
print('P(not long)        =', round(runs.prob(lambda o: o != 'long'), 2))

p_bumper, p_cliff, p_both = 0.08, 0.05, 0.02
p_either = p_bumper + p_cliff - p_both          # addition rule
print('P(bumper or cliff) =', round(p_either, 2))
print('P(neither)         =', round(1 - p_either, 2))
print('union bound        =', round(p_bumper + p_cliff, 2))

P(missed sideways) = 0.3
P(did not dock)    = 0.38
P(wrong distance)  = 0.08
P(not long)        = 0.97
P(bumper or cliff) = 0.11
P(neither)         = 0.89
union bound        = 0.13

In robotics

A localization grid is a sample space

Divide a corridor into 100 cells of 10 cm. “Rover is in cell $i$” for $i = 1 \dots 100$ are mutually exclusive and exhaustive outcomes, provided Rover is in the corridor. A belief is a list of 100 non-negative numbers that sum to 1. Axiom 2 is the reason every filter in this course ends its update with a normalization step: after new evidence is multiplied in, the numbers are rescaled so that they again sum to 1. M6-T2: Histogram Filters and Grid Localization builds this filter.

The same example shows the weak point of axiom 2. If someone carries Rover out of the corridor, the true outcome is not in the sample space, and the filter will still report a confident belief over 100 cells that sums to 1. This is the kidnapped robot problem. The cure is to make the sample space honest, for example by reserving some probability for “somewhere I have no model for” (M9-T4: Monte Carlo Localization in Practice).

Occupancy is a two-outcome sample space

A cell of an occupancy grid map is either occupied or free. By the complement rule only one number has to be stored: $P(\text{free}) = 1 - P(\text{occupied})$. M10-T1: Occupancy Grids and the Binary Bayes Filter builds the whole map from that one number per cell.

Safety budgets use the union bound

A hazard analysis lists the ways a system can fail dangerously: the estimator diverges, a sensor freezes, the brake command is late. The failures are not disjoint and their overlaps are rarely known. The union bound gives a guaranteed ceiling: if the three failure modes have probabilities of at most $10^{-4}$, $2 \times 10^{-4}$ and $5 \times 10^{-5}$ per hour, the probability of at least one is at most $3.5 \times 10^{-4}$ per hour. The UAV course applies this in fault tree analysis.

Defining the event is engineering work

“The grasp succeeded”, “the robot is localized”, “the landing was safe” are events only once someone has said precisely which outcomes they contain. Two teams that report a 95% success rate with different definitions of success have measured different events. Write the definition down before you count.

Common misconceptions

Key takeaways

1. A sample space is a list of outcomes that are mutually exclusive and exhaustive. An event is a set of outcomes; a yes-or-no question about the robot is an event.
2. The three axioms: probabilities are non-negative, the whole sample space has probability 1, and probabilities of disjoint events add.
3. Complement rule: P(not A) = 1 − P(A). Use it whenever the opposite event is easier to compute.
4. Addition rule: P(A or B) = P(A) + P(B) − P(A and B). The sum alone is an upper bound (the union bound).
5. Normalization means “one of the listed outcomes is true”. A filter that normalizes over an incomplete list of outcomes is confidently wrong.

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 , lecture 1 (probability models and axioms). 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 1. Free to read online; the book is copyrighted.
• S. Thrun, W. Burgard and D. Fox, Probabilistic Robotics, MIT Press, 2005, section 2.2 (Basic Concepts in Probability). Paid book.
• A. N. Kolmogorov, Foundations of the Theory of Probability, 1933 (English translation, Chelsea, 1950). The original statement of the axioms. Paid book.
• C. Piech, Probability for Computer Scientists (Stanford CS109 course reader) , part 1. Free to read online.

Knowledge check

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

What’s next

The axioms say how probabilities must fit together, not how to find them when no formula is at hand. The next lesson finds them by experiment: simulate the robot many times and count.

Related content

Nothing below is required to finish this lesson.

• Before
  M1-T1: Why Robots Need Probability

  Name the sources of uncertainty in a robot and explain why a single best guess is not enough to act safely.

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

• Physical AI: State, observation, belief
• SLAM M2-T4: Probability and Uncertainty