Introduction to Probability

Events are sets, and probability counts them

An experiment is any procedure whose result is uncertain. The set of all possible results is the sample space, written $S$, and one element of $S$ is an outcome. An event is any subset of the sample space:

That single word, subset, is the whole level-up. Once events are sets, the set operations you know already become the ways of combining events, and they translate straight into English:

• $A^{c}$, the complement, is everything in $S$ that is not in $A$. In words, ”$A$ does not happen”.
• $A \cup B$, the union, is everything in $A$ or in $B$ or in both. In words, ”$A$ happens or $B$ happens”.
• $A \cap B$, the intersection, is everything in both. In words, ”$A$ and $B$ both happen”.
• $\emptyset$, the empty set, is the impossible event, and $S$ itself is the certain event.

Now attach a number to each set. Write $\lvert A \rvert$ for the number of outcomes in $A$. If the sample space is finite and its outcomes are equally likely, then

Three facts fall out immediately, with no work. Since $0 \le \lvert A \rvert \le \lvert S \rvert$, every probability satisfies $0 \le P(A) \le 1$. The impossible event has $P(\emptyset) = 0$ because $\lvert \emptyset \rvert = 0$. The certain event has $P(S) = 1$ because the quotient $\lvert S \rvert / \lvert S \rvert$ equals $1$.

What “equally likely” actually claims

Read that definition again and notice where the mathematics stops. The formula does not prove that a coin is fair; it assumes it. “Equally likely” is a claim about the world, not a theorem, and no amount of algebra can establish it. A physical die might be weighted, a shuffled deck might be badly shuffled, and a “random” sample of people might quietly exclude everyone without a phone. What mathematics gives you is a conditional promise: if the outcomes of $S$ are equally likely, then $P(A)$ is the fraction of them lying in $A$. Checking the if is your job, and it is done with physics, with care in the design of the experiment, or with data.

The assumption is also delicate, because the same experiment has many sample spaces and usually only one of them is equally likely. Roll two dice and record the sum. The possible results are

which has $11$ outcomes. If you now “count and divide” you get $P(\text{sum} = 2) = \tfrac{1}{11}$, and that is simply wrong. The eleven sums are not equally likely: only $(1,1)$ makes a $2$, while six different rolls make a $7$. The sample space that is equally likely is the set of $36$ ordered pairs, because each die is fair. The multiplication principle from the previous lesson counts $6 \times 6 = 36$ of them. So $P(\text{sum} = 2) = \tfrac{1}{36}$. Choosing the right sample space is the modelling step, and it is where most probability errors are born.

One note on notation before we start. In this chapter the letter $P$ is taken: $P(A)$ means the probability of the event $A$. So we write combinations as $\binom{n}{k}$, exactly as in the binomial theorem, and we spell permutation counts out as products such as $10 \times 9 \times 8$ rather than overloading $P$.

A picture to hold on to

Every rule below is a statement about how the sets overlap, so draw the sets. Take a single card drawn from a standard $52$-card deck. Let $A$ be “the card is a heart” ($13$ cards) and let $B$ be “the card is a face card”, meaning a jack, queen, or king ($12$ cards). Three cards are in both: the jack, queen, and king of hearts.

The complement rule

The first rule is the cheapest and the most useful.

The rule is worth more than its size suggests, because of one recurring phrase: at least one. The event “at least one success” is a sprawling union of many cases (exactly one, exactly two, and so on up). But its complement is a single tidy event: “no successes at all”. Counting the tidy one and subtracting from $1$ is called complementary counting, and for “at least one” problems it is almost always the short road.

The addition rule

Now the union. The naive guess, $P(A \cup B) = P(A) + P(B)$, is wrong in general, and the Venn diagram above shows exactly why: adding $13$ hearts to $12$ face cards counts the three face-card hearts twice. Fixing that overcount is the entire content of the rule.

The familiar “just add them” rule is not a second rule; it is this one with a zero in it. Call $A$ and $B$ mutually exclusive (or disjoint) when they cannot both happen, which is to say when the intersection is empty, $A \cap B = \emptyset$. Then $P(A \cap B) = 0$, the correction term vanishes, and

Keep that as a consequence, not as a separate fact to memorise. The general rule is the one to hold, and the special case is what it collapses to when the circles do not touch.

Conditional probability: shrink the sample space

Here is the idea that makes probability powerful rather than merely tidy. Suppose you learn that the event $B$ has happened. That information does not change the experiment, but it changes what is still possible: every outcome outside $B$ is now ruled out. So throw them away. Your sample space is no longer $S$; it is $B$.

Inside this smaller world, which outcomes still make $A$ happen? Exactly the ones that were in $A$ and in $B$, that is, the outcomes of $A \cap B$. The outcomes of $B$ were equally likely before and nothing has disturbed them, so count and divide as always:

Read $P(A \mid B)$ as “the probability of $A$ given $B$”. To turn that count into probabilities, divide the top and the bottom by $\lvert S \rvert$, which changes nothing:

That is the definition of conditional probability, and it was forced on us: it is what “shrink the sample space to $B$” says in the language of $P$. It also comes with a condition. The formula divides by $P(B)$, so it requires

That is not a technicality to shrug at. Conditioning on an impossible event is meaningless, because “given $B$” means “restrict attention to the outcomes of $B$”, and there are none to restrict to.

The multiplication rule and independence

Multiply both sides of the conditional definition by $P(B)$ and you have a rule for intersections:

This is the multiplication rule, and it says something obvious once you hear it. For both events to happen, $B$ must happen (probability $P(B)$), and then, in the world where it did, $A$ must happen (probability $P(A \mid B)$). It is how you handle any experiment done in stages, such as drawing two cards one after the other.

Now ask a sharper question. What if learning $B$ tells you nothing at all about $A$? Then the conditional probability is no different from the plain one:

Substitute that into the multiplication rule and the conditional vanishes:

We take this last equation as the definition: $A$ and $B$ are independent exactly when $P(A \cap B) = P(A)P(B)$. Two reasons to prefer the product form. It is symmetric in $A$ and $B$, so it cannot pretend that independence is a one-way street: if $B$ says nothing about $A$ then $A$ says nothing about $B$. And it still makes sense when $P(B) = 0$, where $P(A \mid B)$ is not even defined.

Independence is a numerical condition. You do not decide it by staring at the two events and feeling that they seem unrelated; you compute both sides and compare.

Independence can also show up where you did not expect it. Draw one card and let $A$ be “the card is a heart” and $B$ be “the card is a king”. Then $A \cap B$ is the single king of hearts, so

They match, so suit and rank are independent. The reason is visible in the deck itself: every rank comes in exactly one card of each suit. So learning the rank leaves the four suits in the same proportions as before. Knowing you hold a king tells you nothing about the suit.

Mutually exclusive is not the same as independent

Two events, two relations, and they get confused constantly. They are not the same relation, and they are not even close: in the interesting cases they are near opposites.

• Mutually exclusive is a statement about sets: $A \cap B = \emptyset$, the circles do not touch.
• Independent is a statement about numbers: $P(A \cap B) = P(A)P(B)$, knowing one changes nothing about the other.

Now watch what mutual exclusivity actually does to your information. If $A$ and $B$ cannot both happen and someone tells you that $B$ happened, you have learned a great deal about $A$. You have learned that $A$ definitely did not happen. Far from being uninformative, $B$ is as informative as an event can be. That is the exact opposite of independence, and the algebra confirms it.

So the two relations do not merely differ; for events that can actually happen, each one rules the other out. The picture is the fastest way to remember it: mutually exclusive events are drawn as separate circles. Independent events of positive probability are drawn as overlapping ones, with the overlap sized so that $P(A \cap B) = P(A)P(B)$.

Make it concrete with one card. Let $A$ be “the card is a heart” and $B$ be “the card is a spade”. A card cannot be both, so they are mutually exclusive, and $P(A \cap B) = 0$. But

so they are not independent. And of course they are not: if you are told the card is a spade, the chance it is a heart drops from $\tfrac{1}{4}$ to $0$. Compare that with the heart-and-king pair from the last section, which does overlap (in the king of hearts) and is independent. Same deck, two pairs of events, opposite behaviour.

The one honest exception

Can two events be both mutually exclusive and independent? Yes, but only in a degenerate way, and it is worth stating precisely because it is the boundary case the proof above deliberately excluded.

Suppose $A$ and $B$ are mutually exclusive. Then they are independent exactly when $P(A) = 0$ or $P(B) = 0$. Both directions are quick. If they are mutually exclusive and independent, then $P(A)P(B) = P(A \cap B) = 0$, and a product of real numbers is zero only when one of its factors is zero. Conversely, if they are mutually exclusive and (say) $P(A) = 0$, then $P(A \cap B) = 0$ and $P(A)P(B) = 0 \cdot P(B) = 0$ as well, so the two sides agree and the events are independent.

In a finite sample space of equally likely outcomes, $P(A) = 0$ forces $A = \emptyset$. So the only way to be both mutually exclusive and independent is for one of the events to be impossible. That case is a fact about nothing rather than a useful example. For any two events that can actually occur, the two conditions exclude each other.

Probability when the counts get big

Nothing in $P(A) = \lvert A \rvert / \lvert S \rvert$ requires the counts to be small. When the sample space is a set of hands, committees, or arrangements, the counting principles from the previous lesson supply both the numerator and the denominator. The probability is then their quotient. A five-card hand is a set of cards, since the order you are dealt them does not change the hand, so hands are counted with combinations.

The birthday problem

Probability earns its reputation for being counter-intuitive on questions like this one. In a room of $23$ people, what is the probability that at least two of them share a birthday?

Most people guess something small, on the order of a few percent. The true answer is just over one half. Here is the full computation. Assume $365$ days, ignore leap years and seasonal effects, and take a person’s birthday to be equally likely to be any day. An outcome is an assignment of one day to each of the $23$ people, so the multiplication principle gives

and all of these are equally likely. The event “at least two share” is a nightmare to count head on: two people might share, or three, or two separate pairs might match. So take the complement, exactly as with “at least one six”. Let $D$ be the event that all $23$ birthdays are different. Counting $D$ is a one-liner, because you assign the days one person at a time and each new person must dodge every day already used:

a product of $23$ falling factors. Therefore

and the complement rule finishes the job:

Just over $50\%$, so in a room of $23$ a shared birthday is more likely than not.

Why does the answer feel so wrong? Because most people silently answer a different question: “does anyone here share my birthday?” That one really is unlikely. Among $22$ other people, the chance that none matches your day is $\left(\tfrac{364}{365}\right)^{22} \approx 0.941$, so the chance someone does is only about $5.9\%$, and your intuition was right about that.

The question actually asked is not about you. It is about every pair of people in the room, and pairs are counted with combinations:

Two hundred and fifty-three chances for a match, not twenty-two. Each pair matches with probability $\tfrac{1}{365}$, and $253 \times \tfrac{1}{365} \approx 0.69$. Read that number carefully, because it is not a probability. It is a count: roughly how many matching pairs you would expect a room of $23$ to turn up. Nothing stops such a count from passing $1$, and in a room of $30$ it already has, at $\binom{30}{2} / 365 \approx 1.19$. So it cannot be the answer, and neither of the two shortcuts will convert it into one.

The reasons the shortcuts fail are different, and this lesson is precisely about not confusing them. You cannot add the $253$ pair probabilities, because the pair events overlap: several pairs can match at once, and adding would count those rooms many times over. That is the addition rule talking, and what it demands is disjointness, which these events plainly do not have. Separately, you cannot multiply the $253$ misses either, because the pairs are not independent. If Ann and Bob share a birthday and Bob and Cara share a birthday, then Ann and Cara match automatically, so the pair events carry information about one another.

The exact count of $D$ above remains the proof. The pair count is only here to explain why a match is not the long shot it feels like. The room grows one person at a time, but the pairs grow roughly like the square of the room.

Common mistakes