Outcomes, events and counting

The opening note defined the probability of an event, when all outcomes are equally likely, as a ratio of two counts: $P(A) = |A| / |\Omega|$. The definition is simple and the counting is not. The birthday problem already needed a product of 23 fractions, and a careless choice of what counts as an outcome gives wrong answers with full confidence. This note sets up the language of outcomes and events and the four counting rules that every later calculation uses.

Notation. $\Omega$ is the sample space, the set of all outcomes of an experiment; an event is a subset $A \subseteq \Omega$. $A \cup B$ is ”$A$ or $B$”, $A \cap B$ is ”$A$ and $B$”, $A^c = \Omega \setminus A$ is “not $A$”. $n! = 1 \cdot 2 \cdots n$, with $0! = 1$, and $\binom{n}{k} = \frac{n!}{k!\,(n-k)!}$.

Outcomes and events#

An outcome is one complete result of the experiment; the sample space $\Omega$ lists all of them. For two rolls of a die, an outcome is an ordered pair, $\Omega = \{(1,1), (1,2), \dots, (6,6)\}$, with $|\Omega| = 36$. An event is any set of outcomes: “the sum is 7” is $\{(1,6), (2,5), (3,4), (4,3), (5,2), (6,1)\}$, so $P = 6/36 = 1/6$.

Set operations are logical operations on events. “At least one six” is the union of “first is six” and “second is six”; “both are six” is their intersection; “no six” is the complement of the first. Two events are disjoint if they cannot happen together, $A \cap B = \varnothing$. De Morgan’s laws translate between “and” and “or” through negation, $(A \cup B)^c = A^c \cap B^c$, which is often the quickest way to a count: “at least one six” has $36 - 25 = 11$ outcomes, because “no six” has $5 \cdot 5 = 25$.

Choosing outcomes that are equally likely#

The formula $|A| / |\Omega|$ is correct only if the outcomes really are equally likely, and that depends on how they are written down. Toss two coins and record the number of heads: $\Omega = \{0, 1, 2\}$ has three outcomes, but “one head” is not one third likely. Writing the coins in order, $\{\mathrm{HH}, \mathrm{HT}, \mathrm{TH}, \mathrm{TT}\}$, gives four equally likely outcomes, and “one head” has two of them: $P = 1/2$. The mistake is old enough to have a name, after d’Alembert, who argued for $2/3$ for “at least one head” in the 18th century; the right answer is $3/4$.

The safe rule: write outcomes so that the physical experiment treats them symmetrically. Usually that means keeping track of order and of which object is which, even when the question does not care, and counting the event inside that larger, symmetric space.

The multiplication rule#

If an outcome is built in $k$ stages, with $n_1$ choices at the first stage, $n_2$ at the second whatever happened at the first, and so on, the number of outcomes is

$$n_1 \cdot n_2 \cdots n_k .$$

Two dice: $6 \cdot 6 = 36$. A password of 8 characters from 62 letters and digits: $62^8 = 218{,}340{,}105{,}584{,}896$, about $2.2 \cdot 10^{14}$. Arranging $n$ different objects in a row: $n \cdot (n-1) \cdots 1 = n!$. The rule needs only that the number of choices at each stage does not depend on the earlier choices; which choices are available may.

Four ways to choose $k$ out of $n$#

Most counting problems are a choice of $k$ items from $n$, and two questions decide the formula: does the order of the choices matter, and can an item be chosen again?

Order	Replacement	Number of choices	$n = 4$, $k = 2$
ordered	with	$n^k$	16
ordered	without	$\dfrac{n!}{(n-k)!} = n (n-1) \cdots (n-k+1)$	12
unordered	without	$\dbinom{n}{k}$	6
unordered	with	$\dbinom{n+k-1}{k}$	10

The figure draws the four cases in the same order, 16, 12, 6 and 10:

Figure

Four ways to choose 2 items out of 4

Three of the formulas follow from the multiplication rule. Ordered with replacement: $n$ choices at each of $k$ stages. Ordered without replacement: one fewer choice at each stage. Unordered without replacement: every unordered set of $k$ items appears in $k!$ orders, so $\binom{n}{k} = \frac{n!}{(n-k)!\,k!}$. The fourth, unordered with replacement, counts the ways to put $k$ identical marks into $n$ boxes (“stars and bars”): a row of $k$ stars and $n - 1$ bars has $\binom{n+k-1}{k}$ arrangements. For $n = 4$, $k = 2$ the row has two stars and three bars, five symbols in all, and the bars split it into four boxes: ★|★|| is one mark in box 1 and one in box 2, the selection $\{1, 2\}$; ★★||| is both marks in box 1, the selection $\{1, 1\}$; ||★|★ is $\{3, 4\}$. Every selection is one choice of 2 star positions among the 5, so there are $\binom{5}{2} = 10$ of them.

The fourth count is a count of distinct results, not of equally likely outcomes. Two dice give 21 unordered results, but $\{1, 2\}$ has probability $2/36$ and $\{1, 1\}$ only $1/36$. The binomial coefficient $\binom{n}{k}$, by contrast, does count equally likely outcomes when $k$ items are drawn at random without replacement, because every unordered set arises from the same number $k!$ of ordered draws.

Worked examples#

Shared birthdays. For $n$ people, ordered with replacement gives $365^n$ equally likely lists of birthdays; the lists with all birthdays different are ordered without replacement, $365!/(365-n)!$. For $n = 23$:

$$P(\text{all different}) = \frac{365 \cdot 364 \cdots 343}{365^{23}} = 0.4927 ,$$

so a shared birthday has probability $0.5073$, the number of the opening note.

A lottery. Six numbers out of 49, unordered and without replacement: $\binom{49}{6} = 13{,}983{,}816$ possible tickets. One ticket wins the jackpot with probability one in about 14 million.

Two aces in a hand of five. A hand is an unordered set of 5 of 52 cards: $\binom{52}{5} = 2{,}598{,}960$ hands. Hands with exactly two aces choose 2 of the 4 aces and 3 of the 48 other cards:

$$P = \frac{\binom{4}{2} \binom{48}{3}}{\binom{52}{5}} = \frac{6 \cdot 17{,}296}{2{,}598{,}960} = 0.0399 .$$

This is the hypergeometric count, the distribution of the number of special items in a sample drawn without replacement; the discrete distributions note puts it next to the binomial.

With and without replacement. An urn holds 3 red and 2 blue balls; draw two. Without replacement, $P(\text{both red}) = \frac{3}{5} \cdot \frac{2}{4} = 0.30$; with replacement, $\left(\frac{3}{5}\right)^2 = 0.36$. The difference shrinks as the urn grows, which is why a sample from a large population can be treated as drawn with replacement.

What changed#

	Listing outcomes by hand	Counting rules
Two dice	36 outcomes, written out	$6^2$
Hands of 5 cards	impossible to list	$\binom{52}{5} = 2{,}598{,}960$
Equally likely?	must be argued for the list	holds for ordered draws and for $\binom{n}{k}$ samples; fails for unordered draws with replacement

Limitations#

• Only equally likely outcomes. Counting gives probabilities only when the outcomes are symmetric; a loaded die or a biased coin needs the general rules of the next note.
• Only finite sample spaces. A random point on a segment or the waiting time until a bus have infinitely many outcomes; ratios of counts are meaningless there.
• Easy to double count. Most counting errors are a hidden order (counting $(a, b)$ and $(b, a)$ twice) or a hidden identity (treating identical objects as different). Checking a count on a small case, by listing or by simulation, catches most of them.

What you should remember#

• Outcomes are the complete results of an experiment; events are sets of outcomes; “or”, “and” and “not” are union, intersection and complement.
• Write outcomes so that they are equally likely, usually by keeping order and identity, and count the event inside that space.
• Multiplication rule: $n_1 n_2 \cdots n_k$ outcomes for $k$ stages.
• Choosing $k$ of $n$: $n^k$, $n!/(n-k)!$, $\binom{n}{k}$, $\binom{n+k-1}{k}$ for ordered with replacement, ordered without, unordered without and unordered with replacement; the last counts results, not equally likely outcomes.

Code#

Every count of the note, checked by enumeration with itertools:

import itertools, math

items = 'abcd'
print(len(list(itertools.product(items, repeat=2))),                # 16  ordered, with replacement
      len(list(itertools.permutations(items, 2))),                  # 12  ordered, without replacement
      len(list(itertools.combinations(items, 2))),                  # 6   unordered, without replacement
      len(list(itertools.combinations_with_replacement(items, 2)))) # 10  unordered, with replacement

dice = list(itertools.product(range(1, 7), repeat=2))
print(round(sum(a + b == 7 for a, b in dice) / 36, 4), sum(6 in d for d in dice))   # 0.1667 11

# two coins: "exactly one head" among the ordered outcomes HH, HT, TH, TT
coins = list(itertools.product('HT', repeat=2))
print(sum(c.count('H') == 1 for c in coins) / len(coins))                 # 0.5

print(round(math.perm(365, 23) / 365**23, 4), math.comb(49, 6))           # 0.4927 13983816

hands = math.comb(52, 5)
two_aces = math.comb(4, 2) * math.comb(48, 3)
print(two_aces, hands, round(two_aces / hands, 4))                        # 103776 2598960 0.0399

# urn with 3 red and 2 blue balls, two draws: both red
print(3 / 5 * 2 / 4, (3 / 5) ** 2)                                        # 0.3 0.36

Next#

Counting needs equally likely outcomes and a finite sample space. A loaded die breaks the first condition; a random point on a segment and a waiting time break the second. The next note replaces counting by three axioms that any probability must satisfy, explains why a probability is assigned to some sets of outcomes and not to all, and derives the rules (complements, unions, inclusion–exclusion) that counting used without proof.

References#

• J. K. Blitzstein, J. Hwang. Introduction to Probability, 2nd ed. CRC Press, 2019. Chapter 1 (naive definition, counting, the four ways of sampling).
• W. Feller. An Introduction to Probability Theory and Its Applications, Vol. 1, 3rd ed. Wiley, 1968. Chapter II (elements of combinatorial analysis, occupancy problems).
• A. N. Shiryaev. Probability-1, 3rd ed. Springer, 2016. Chapter 1, §1 (classical models and combinatorics).