Introduction to Probability

Events are sets, and probability counts them

Roll a fair six-sided die. There are six possible results, and every one of them is equally likely because the die is fair. Suppose you care whether the roll comes up even: that is three of the six results, namely $2$, $4$, and $6$. Since three of the six equally likely results fit what you asked about, the probability of an even roll is $\tfrac{3}{6} = \tfrac{1}{2}$.

Every idea in this lesson is a more careful version of that one calculation, so here is the vocabulary for it. An experiment is any procedure whose result is uncertain, such as rolling the die. The set of all possible results is the sample space, written $S$; for the die, $S = \{1, 2, 3, 4, 5, 6\}$. One element of $S$ is an outcome. An event is any subset of the sample space, such as $A = \{2, 4, 6\}$, “the roll is even”:

Every member of $A$ is also a member of $S$, so $A \subseteq S$: an event is just the part of the sample space you are asking about. 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 can be described with more than one sample space, and not every one of those descriptions has equally likely outcomes. 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 modeling step, and it is where most probability errors are born.

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 memorize. 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 for any two events that can actually happen, they cannot both hold at once, as the proof below shows precisely.

• 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 that $A$ definitely did not happen: its probability dropped straight to $0$. That is a large effect on $A$, not the “changes nothing” that independence requires, and the algebra below confirms it exactly.

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 behavior.

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 in the first place, which is not a useful case to build examples from. For any two events that can actually occur, the two conditions exclude each other.

Probability when the counts get big

This section is an application, not a new rule: it reuses favorable-over-total on sample spaces built from combinations, so the formula does not feel limited to small counts.

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, written $\binom{n}{k}$ exactly as in the previous lesson. One note on notation: the letter $P$ is already taken here, since $P(A)$ means the probability of the event $A$, so permutation counts below are spelled out as products such as $10 \times 9 \times 8$ instead.

The birthday problem

This is an extended application of the complement rule you already learned, on a famous example where intuition usually gets it wrong. It does not introduce a new probability rule.

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}$. Give every pair its own small “share” of $\tfrac{1}{365}$ toward a match, and add up the $253$ shares: $253 \times \tfrac{1}{365} \approx 0.69$. Adding shares like that is always allowed, no matter how the pairs relate to each other, because you are only totaling how much each pair contributes, not asking whether an event happened. Read the total carefully, though, because it is not a probability. It is a count, called the expected number of matching pairs: roughly how many a room of $23$ would turn up on average, a later course’s full topic but honest to name here. 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 below 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 to get the answer, 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$ “no match” probabilities either, and the reason is more subtle. Take any two of the $253$ events by themselves, say “Ann and Bob match” and “Bob and Cara match”. Those two, on their own, really are independent: knowing one tells you nothing about the other. The trouble only shows up once you look at all $253$ together. If Ann and Bob match and Bob and Cara match, then Ann and Cara are forced to match too, so the third event is decided the moment the first two happen. A collection of truly independent events can never do that to each other. So it is the whole collection that fails to be independent, not any two events you might pick out of it: pairwise independence (any two, checked alone) does not force mutual independence (the whole collection, checked together), and that gap is enough to break the multiplication shortcut.

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