Outcomes and events

Three rules survived the previous lesson: probabilities lie between zero and one, the alternatives sum to one, and disjoint alternatives add. Rules need something to be rules about, and this lesson builds it. The construction is set theory of the plainest kind, and by the end of it a handful of genuinely useful formulas will have been proved rather than asserted.

The list of everything that can happen

Start with the experiment, meaning any procedure with an uncertain result. Its sample space $Ω$ is the set of all its possible outcomes, chosen so that exactly one of them occurs on each run: no two can happen together, and none can be left out.

For one roll of a die, $Ω = {1, 2, 3, 4, 5, 6}$ . For two dice distinguished by colour, $Ω$ is the set of ordered pairs $(i, j)$ , so it has $36$ elements. That choice is not forced, and the alternative is instructive: you could take $Ω$ to be the $11$ possible totals, from $2$ to $12$ , and the definition would still be satisfied, since exactly one total occurs. What you lose is symmetry. The $36$ pairs are interchangeable and the $11$ totals are not, so only the first choice lets you count. Choosing a sample space fine enough to be symmetric is the single most useful habit in the subject.

Sample spaces need not be finite. Toss a coin until the first head appears and record how many tosses it took: $Ω = {1, 2, 3, \dots}$ , countably infinite, with no upper bound on how long you might wait. Measure the lifetime of a light bulb in hours and $Ω$ is the set of non-negative real numbers, uncountable. All three kinds appear in this course.

An event is a subset of $Ω$ : any collection of outcomes you might want to speak about as a unit. "The die shows an even number" is the subset ${2, 4, 6}$ . "The two dice total seven" is a subset of six pairs. An event occurs when the outcome that happened is one of its members. Individual outcomes give the one-element events, $Ω$ itself is the certain event, and the empty set $\emptyset$ is the impossible one.

Or, and, not

Putting events in a set makes ordinary logical words into set operations, and this is the whole reason for the construction.

" $A$ or $B$ ", meaning at least one of them, is the union $A \cup B$ . " $A$ and $B$ ", meaning both, is the intersection $A \cap B$ . "Not $A$ " is the complement $A^{c} = Ω ∖ A$ . Two events with $A \cap B = \emptyset$ cannot both occur and are called disjoint or mutually exclusive. A family of events that are pairwise disjoint and whose union is all of $Ω$ is a partition: exactly one of them happens.

Set algebra now supplies identities for free, including the two of De Morgan:

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

Read in words, the first says that "neither happened" is the same statement as "not the first and not the second", and the second says that "they did not both happen" is the same as "at least one failed to". These are not probability facts, they are facts about sets, and they will convert several awkward calculations into easy ones. The trick that solved de Méré's dice problem in the previous lesson was exactly the first identity: "at least one six" is the complement of "no sixes", and the second is far easier to count.

Three axioms

Kolmogorov's 1933 axioms assign to each event $A$ a number $P (A)$ subject to three demands.

P (A) \geq 0 for every event A

P (Ω) = 1

P (A_{1} \cup A_{2} \cup \dots) = P (A_{1}) + P (A_{2}) + \dots for pairwise disjoint A_{i}

The third is countable additivity, and the word countable is doing real work: it holds for infinite sequences of disjoint events, not merely for finitely many. That extension is what allows the coin-until-heads space to be handled, where the probabilities $1 / 2, 1 / 4, 1 / 8, \dots$ must sum to $1$ over infinitely many outcomes, which they do by the geometric series.

One honest caveat. On an uncountable sample space, such as a dart landing anywhere on a metre rule, it is not possible to assign a sensible probability to every subset: there are subsets so pathological that any assignment contradicts the axioms. The repair is to declare in advance a family of subsets that count as events, closed under complement and countable union, and demand nothing about the rest. That family is called a $σ$ -algebra, and for everything in this course it can be ignored, because every set anyone would write down is in it. It is mentioned here only so that the word is not a surprise elsewhere.

What follows at once

Everything below is proved from the three axioms and nothing else.

The complement rule comes first. $A$ and $A^{c}$ are disjoint and their union is $Ω$ , so $P (A) + P (A^{c}) = P (Ω) = 1$ , giving

P (A^{c}) = 1 - P (A)

Take $A = Ω$ and this gives $P (\emptyset) = 0$ : the impossible event has probability zero. The converse fails, and it will matter later. An event of probability zero need not be impossible, as the lesson on continuous variables shows.

Next, if $A \subseteq B$ , split $B$ into the disjoint pieces $A$ and $B ∖ A$ . Then $P (B) = P (A) + P (B ∖ A)$ , and since the last term cannot be negative,

A \subseteq B ⟹ P (A) \leq P (B)

so probability is monotone. Combined with $P (Ω) = 1$ this bounds every probability above by one, which the axioms never stated directly. The rearrangement $P (B ∖ A) = P (B) - P (A)$ is the difference rule, valid when $A$ sits inside $B$ and not otherwise.

Example. In a group, $70$ percent own a bicycle and $40$ percent own a bicycle and a car. What can be said about the percentage owning a bicycle but no car?

"Bicycle and car" is a subset of "bicycle", so the difference rule applies exactly: $P (bicycle, no car) = 0.70 - 0.40 = 0.30$ . Note that nothing was assumed about how the two ownerships relate. The subset relation did all the work.

Now you. In the same group, $55$ percent own a car. What percentage own a car but no bicycle?

Answer

$0.55 - 0.40 = 0.15$ , again by the difference rule, since car-and-bicycle is a subset of car.

Adding events that overlap

The third axiom adds probabilities only for disjoint events, and most interesting pairs overlap. Fix it by splitting.

Write $A \cup B$ as the two disjoint pieces $A$ and $B ∖ (A \cap B)$ . Additivity gives $P (A \cup B) = P (A) + P (B ∖ (A \cap B))$ , and since $A \cap B \subseteq B$ the difference rule turns the second term into $P (B) - P (A \cap B)$ . Hence

P (A \cup B) = P (A) + P (B) - P (A \cap B)

This is inclusion and exclusion. The subtraction is bookkeeping: adding the two probabilities counts the overlap twice, so it comes off once. For three events the same argument, applied twice, gives

P (A \cup B \cup C) = P (A) + P (B) + P (C) - P (A \cap B) - P (A \cap C) - P (B \cap C) + P (A \cap B \cap C)

The pattern continues, alternating in sign, with all singles added, all pairs subtracted, all triples added, and so on.

Dropping the subtractions leaves an inequality that holds always, since the terms removed are non-negative:

P (A_{1} \cup A_{2} \cup \dots \cup A_{n}) \leq P (A_{1}) + P (A_{2}) + \dots + P (A_{n})

This is the union bound, or Boole's inequality. It is crude, it needs no information at all about how the events relate, and it is used constantly, because "at least one of these bad things happens" is bounded by the sum of the individual risks whether or not they are connected. When the sum exceeds one it says nothing, which is the honest signal that the events overlap too much for it to help.

Example. A whole number is drawn at random from $1$ to $1000$ , each equally likely. What is the probability it is divisible by $2$ , by $3$ or by $5$ ?

Count each set: $500$ multiples of $2$ , $333$ of $3$ , $200$ of $5$ . Subtract the pairs, counted by the least common multiples: $166$ multiples of $6$ , $100$ of $10$ , $66$ of $15$ . Add back the $33$ multiples of $30$ . The union has

500 + 333 + 200 - 166 - 100 - 66 + 33 = 734

members, so the probability is $0.734$ . The union bound would have offered only $\leq (500 + 333 + 200) / 1000 = 1.033$ , which is no information at all.

Now you. Two fair dice are rolled. Let $A$ be "at least one die shows a five", which contains $11$ of the $36$ pairs, and $B$ be "the total is eight", which contains $5$ . Their intersection contains $2$ . Find $P (A \cup B)$ .

Answer

$P (A \cup B) = 11 / 36 + 5 / 36 - 2 / 36 = 14 / 36 \approx 0.3889$ .

When the outcomes are equally likely

Suppose $Ω$ is finite with $N$ outcomes and all of them carry the same probability $p$ . Additivity over the $N$ one-element events gives $N p = P (Ω) = 1$ , so $p = 1 / N$ , and for any event $A$ containing $| A |$ outcomes,

P (A) = \frac{| A |}{N}

The classical rule of the previous lesson is recovered, no longer as a definition but as a theorem about one particular assignment among many. The axioms are silent about whether the outcomes deserve equal probability; that is a modelling decision made outside the mathematics, justified by symmetry when there is symmetry and by measurement when there is not.

Nothing forces uniformity. A loaded die might carry $P (6) = 0.25$ with the other five faces sharing the remaining $0.75$ equally, at $0.15$ each, and every rule above still applies unchanged. The infinite space is the sharper case: for the coin tossed until the first head, $P (n) = 2^{- n}$ , which sums to $1$ but assigns different probabilities to different outcomes, and no uniform assignment on ${1, 2, 3, \dots}$ is even possible, since equal positive values summing to one over infinitely many outcomes cannot exist.

Example. A die is loaded so that $P (6) = 0.25$ and the other five faces are equally likely. What is the probability of an even number?

The other five faces share $1 - 0.25 = 0.75$ , so each has $0.15$ . The even faces are $2$ , $4$ and $6$ , disjoint one-element events, so $P (even) = 0.15 + 0.15 + 0.25 = 0.55$ . On a fair die it would be $0.5$ , and the loading has shifted it.

Now you. For the same loaded die, find the probability that the result is at least $4$ .

Answer

The outcomes $4$ , $5$ and $6$ have probabilities $0.15$ , $0.15$ and $0.25$ , so the answer is $0.55$ as well. The two events differ but happen to share a probability.

What the axioms do not give you

Three axioms and some set algebra have produced the complement rule, monotonicity, the difference rule, inclusion and exclusion in any number of events, and the union bound. That is a working toolkit, and it is worth being clear about what it is not.

The axioms never say what number to attach to any particular event. They constrain assignments to be consistent with one another; they cannot manufacture one out of nothing. Every calculation in this lesson began from probabilities that were either handed over or justified by a symmetry argument outside the theory, and this is not a defect to be repaired later. It is the permanent division of labour: modelling supplies the inputs, the axioms police the consequences.

The other gap is practical. Once symmetry does apply, $P (A) = | A | / N$ reduces every question to two counts, and the sets that arise are rarely small enough to list. How many five-card hands contain two pairs? How many ways can twenty-three birthdays fall so that no two coincide? Answering questions like these is a discipline of its own, and it is the subject of the next lesson.