9.1 Sample Spaces and Counting Probability

Chapter 6 taught us to count objects without listing them one by one. Chapter 8 then used choices that should be hard to predict, such as selecting secret primes or randomized padding in real cryptographic systems. We can now ask a new kind of question:

> When several outcomes are possible but we do not know which one will occur, how can counting measure uncertainty?

Probability begins with a precise description of the possible outcomes. Only after that description is complete do we attach numbers to events.

Random experiments and outcomes

A random experiment is a repeatable process whose result is not known in advance. Rolling a die, drawing a card from a shuffled deck, or choosing a server uniformly at random are experiments. The word random does not mean “without rules.” We must specify the rules carefully.

One complete result of an experiment is an outcome. If a six-sided die is rolled once, the outcomes are the face values $1,2,3,4,5,6$.

The sample space is the set of every possible outcome. We denote it by the Greek capital letter $Omega$, pronounced “omega.” For one die,

The braces remind us that $Omega$ is a set. Every actual roll produces exactly one member of this set.

A sample space depends on what we record. Suppose we toss a coin twice.

• If order matters, then $HT$ and $TH$ are different outcomes, so

• If we record only the number of heads, then

These sample spaces answer different questions. In $Omega'$, the three outcomes are not equally likely: one head can occur as $HT$ or $TH$, while zero heads can occur only as $TT$. Choosing a convenient-looking sample space without checking its probabilities is a common mistake.

Events are sets of outcomes

An event is a set of outcomes that share a property. Therefore, an event is a subset of the sample space. We write

For a die roll, let $A$ be the event “the result is even.” Then

The event occurs when the observed outcome belongs to $A$. A one-outcome event such as $\{4\}$ is called a simple event. An event with several outcomes is a compound event.

Two boundary events are useful:

• the impossible event is $\varnothing$, the empty set, because it contains no outcome;
• the certain event is $Omega$, because some outcome in the sample space must occur.

Probability assigns a number to an event

The probability of event $A$ is written $P(A)$. It is a number from $0$ to $1$:

The endpoints have clear meanings:

A larger probability represents a more likely event. Probability $1/2$ does not promise that the event happens on every second trial. It describes the long-run balance predicted by the model.

For a finite sample space whose individual outcomes are equally likely, we have the classical probability model (also called the finite equally likely model). Probability then becomes a counting ratio:

Here $|A|$ means the number of outcomes in $A$, and $|\Omega|$ means the number of outcomes in the entire sample space. The assumptions matter: the space must be finite, and its outcomes must have equal probability.

For the even die event,

The numerator counts favorable outcomes; the denominator counts all possible outcomes.

A reliable counting-probability procedure

When outcomes are equally likely, use four steps:

1. State exactly what one outcome records. 2. Build or count the sample space $Omega$. 3. Describe the event $A$ and count its outcomes. 4. Form $|A|/|\Omega|$ and simplify.

The first step prevents most errors. If order matters in the experiment, it must also matter in the outcomes you count.

Build a two-stage experiment from coins, dice, or spinners. The lab turns the Cartesian product into an outcome floor: every cell is one ordered pair. Paint an event by selecting cells and watch its set, size, and exact probability change together.

Multi-stage experiments use the product principle

Now roll a blue die and a gold die. An outcome must record both results, so it is an ordered pair $(b,g)$. The sample space is

The multiplication sign here denotes a Cartesian product, introduced in Chapter 1. By the product principle from Chapter 6,

Let $S$ be the event “the sum is at least $10$.” List by the first coordinate:

Therefore,

Notice why the ordered pairs matter. The outcomes $(4,6)$ and $(6,4)$ are different because the blue and gold dice exchanged results.

Combining events with set operations

Because events are sets, the operations from Chapter 1 have probability meanings.

• $A\cup B$ means “$A$ occurs or $B$ occurs, or both.”
• $A\cap B$ means “both $A$ and $B$ occur.”
• $A^c=\Omega\setminus A$ is the complement of $A$: “$A$ does not occur.”

Since $A$ and $A^c$ divide the sample space into two non-overlapping parts,

This is often easier than counting $A$ directly. For two dice, let $R$ be “at least one die shows $6$.” Its complement is “neither die shows $6$.” Each die then has $5$ allowed faces, so

and hence

For a union, adding $P(A)$ and $P(B)$ counts outcomes in $A\cap B$ twice. Inclusion–exclusion corrects that overlap:

This is the same structural idea as the counting formula from Chapter 6; only the measured quantity has changed from counts to probabilities.

Theoretical probability and observed frequency

The fraction computed from a model is a theoretical probability. An experiment also produces data. If event $A$ occurs $N_A$ times in $N$ trials, its relative frequency is

The hat distinguishes the observed estimate $\widehat P_N(A)$ from the model value $P(A)$.

For a fair die, $P(6)=1/6$. After $12$ rolls, we might see four sixes and obtain

That does not prove the die is unfair. Small samples can fluctuate. With many repeated trials under the same conditions, relative frequency tends to settle near the theoretical probability. This long-run behavior is called the law of large numbers. We use only its intuition here; a formal theorem requires ideas beyond this section.

Two cautions are essential:

1. More trials reduce typical fluctuation, but they do not force exact equality. 2. A simulation tests the model you programmed. It cannot repair an incorrect sample space or an unjustified equal-likelihood assumption.

Run a probability carnival with a configurable prize wheel. Launch trials in bursts, inspect the path of cumulative relative frequency, and then rebuild the wheel to see whether the observed path follows the new theoretical target.

Section checklist

Before solving a finite probability problem, ask:

• What does one outcome record?
• Does the sample space include every possible outcome exactly once?
• Are the outcomes genuinely equally likely?
• Which subset represents the event?
• Can a complement, product count, or inclusion–exclusion avoid a long list?
• Am I distinguishing a theoretical probability from an observed frequency?

So far, every probability was measured inside the original sample space. Sometimes new information tells us that only part of that space is still possible. Section 9.2 develops the rule for probability after such a restriction.