"There is a 70% chance of rain tomorrow." "This coin lands heads with probability 1/2." "There is a 1 in 10 chance this patch introduces a regression." All three sentences use the same word, but they don’t obviously mean the same thing. Tomorrow happens only once, so what could "70% of the time" mean? A coin can be tossed again and again. A patch either has a bug or it doesn’t; the uncertainty is in your head, not in the code.

Before computing anything, it pays to know what a probability is.

There are two classic interpretations, and you will use both.

Frequentist (long-run frequency). The probability of an event is the fraction of times it happens when you repeat the experiment many, many times under the same conditions. Toss a fair coin 10 times and you might get 7 heads. Toss it 10,000 times and the fraction of heads will be very close to 0.5. The probability is the number that fraction settles down to.

Bayesian (degree of belief). The probability of an event is a number between 0 and 1 measuring how strongly you believe it, given what you know. "70% chance of rain" means the forecaster is about as confident of rain as of drawing a red ball from an urn with 7 red and 3 blue. This reading makes sense for one-off events (tomorrow’s weather, whether a patch is buggy) and, crucially, tells you how beliefs should change when evidence arrives. That change is Bayes' theorem, coming later in Section 29.9.

The good news: both interpretations obey exactly the same rules. Whatever probability "really" is, the arithmetic in this chapter applies to it. Statisticians argue about interpretation (we return to the argument in Chapter 31); they don’t argue about the rules.

To say anything precise you need to pin down what can happen. "Roll two dice; what is the probability of a total of 8?" requires a list of everything that could happen, and a way to pick out the cases that count as "total of 8". Set language from Chapter 21 does exactly this.

Because events are sets, all the set operations you know become ways of combining events. The translation table is worth memorising, because every probability word problem is written in the left-hand column and every calculation happens in the right-hand one.

Roll a red die and a blue die. An outcome is a pair \((r, b)\) with \(r, b \in \{1, \ldots, 6\}\), so by the product rule (Chapter 24) the sample space has \(6 \times 6 = 36\) outcomes. Picture them as a grid: Try it: Two-dice events on a grid.

Let \(A\) = "total is 8" \(= \{(2,6), (3,5), (4,4), (5,3), (6,2)\}\), and \(D\) = "doubles" \(= \{(1,1), (2,2), \ldots, (6,6)\}\). Then

Notice how the question "how many outcomes?" is already doing most of the work. Probability, in the simplest setting, is counting.

We need rules that every assignment of probabilities must obey, whether the numbers come from counting, from long-run frequencies or from belief. Remarkably, three rules suffice, and everything else in this chapter is derived from them.

These match intuition for frequencies. A fraction of trials can’t be negative; the fraction of trials in which something happens is 1; and if \(A\) and \(B\) never happen together, the fraction of trials in which one of them happens is the fraction for \(A\) plus the fraction for \(B\).

The complement rule. \(A\) and \(A^c\) are disjoint and together make up \(\Omega\). So

and therefore \(P(A^c) = 1 - P(A)\). As special cases, \(P(\varnothing) = 1 - P(\Omega) = 0\), and since \(P(A^c) \ge 0\), \(P(A) \le 1\).

The addition rule (general). If \(A\) and \(B\) overlap, adding \(P(A) + P(B)\) counts the overlap \(A \cap B\) twice. Split the union into three disjoint pieces: "\(A\) only", "\(B\) only", "both". Then

This is inclusion–exclusion from Chapter 24, with probabilities in place of counts.

Example 1 (complement). What is the probability of at least one six in four rolls of a die? "At least one" has many cases (exactly one six, exactly two, …). The complement, "no sixes", is one case. Each roll avoids six in 5 of 6 ways, so by counting, \(P(\text{no sixes}) = \frac{5^4}{6^4} = \frac{625}{1296}\). Then

Slightly better than even. This was one of the bets that sparked the Pascal–Fermat letters.

Example 2 (addition rule). In a codebase, 30% of files have no tests, 20% have a lint warning, and 8% have both. What fraction of files have at least one of these problems?

So 58% of files are clean.

For fair dice, shuffled cards and random selections, every outcome in a well-chosen sample space has the same probability. Then probability reduces to counting. But the counts can be large, which is why Chapter 24 came first.

Suppose \(\Omega\) has \(N\) outcomes, all equally likely, each with probability \(p\). The outcomes are disjoint and together make up \(\Omega\), so by axioms 2 and 3, \(Np = 1\) and \(p = 1/N\). An event \(A\) with \(|A|\) outcomes is the disjoint union of those outcomes, so

What is the probability that a 5-card hand dealt from a shuffled 52-card deck contains exactly two aces? Try it: Two aces, computed.

Step 1. Outcomes: unordered 5-card hands, all equally likely.

Step 2. \(|\Omega| = \binom{52}{5} = 2\,598\,960\).

Step 3. Build a favourable hand in two stages: choose 2 of the 4 aces, then 3 of the 48 non-aces.

Step 5. \(P(A) = \frac{103\,776}{2\,598\,960} \approx 0.0399\), about 4%.

A batch of 20 chips has 3 defective ones. You test 4 chosen at random. What is the probability you catch at least one defective chip? Try it: Defective batch sampler.

Counting "at least one" directly means cases 1, 2 and 3. The complement, "no defectives", is one case: all 4 chosen from the 17 good chips.

Testing 4 of 20 chips gives only about a coin-flip’s chance of spotting a problem that affects 15% of the batch. Quality-control sampling plans are designed with exactly this calculation.

Roll two dice. The probability that the total is 8 is \(5/36 \approx 0.139\). Now a friend peeks at the red die and tells you "it’s even". Should your probability for "total is 8" change? Intuitively yes: an even red die rules out some ways of getting 8 (such as \((3,5)\)) and keeps others (such as \((2,6)\)). But by how much?

Before the hint, any of 36 outcomes could be the true one. After "the red die is even", only the 18 outcomes with \(r \in \{2, 4, 6\}\) are still possible. The other 18 are ruled out. Nothing has changed about the relative chances of the outcomes that remain: they were equally likely before, and nothing in the hint favours one over another, so they are still equally likely. The new sample space is just smaller. Try it: Watch conditioning shrink the world.

Among the 18 survivors, the totals of 8 are \((2,6)\), \((4,4)\), \((6,2)\): three of them. So the updated probability is \(3/18 = 1/6 \approx 0.167\). The hint made "total is 8" a little more likely.

That’s all conditioning is: restrict attention to the outcomes consistent with what you know, and re-measure the event as a fraction of that restricted world.

In the dice example the calculation was

Divide top and bottom by \(|\Omega| = 36\):

That last form doesn’t mention counting at all, so it makes sense even when outcomes aren’t equally likely. It becomes the definition.

Read the formula as an instruction: zoom in on \(B\), then measure \(A\)'s share of it. The division by \(P(B)\) is a rescaling so that the new, smaller world has total probability 1 again. You can check that \(P(\cdot \mid B)\) satisfies all three axioms: it is a genuine probability, just on a smaller world.

Real data often arrives as a table of counts, and then conditioning is literally "restrict to a row or column". Here are 1,000 deploys of a service, classified by whether they were made on a Friday and whether they caused an incident:

Check the definition gives the same thing: \(P(\text{incident} \cap \text{Friday}) / P(\text{Friday}) = 0.024 / 0.2 = 0.12\). ✓

Friday deploys are more than twice as likely to cause incidents. (Whether Fridays cause incidents is a different question; see correlation versus causation in Chapter 31.)

A family has two children. Assume each child is independently a boy or a girl with probability 1/2. Given that at least one is a girl, what is the probability that both are girls?

Sample space (ordered by birth, so equally likely): \(\{BB, BG, GB, GG\}\).

Not 1/2, which is most people’s first answer. The information "at least one girl" removes only \(BB\), leaving three equally likely worlds, and only one of them is \(GG\). If instead you’re told "the elder child is a girl", the world shrinks to \(\{GB, GG\}\) and the answer is 1/2. Different information, different restricted world, different answer. Conditioning is sensitive to exactly what you learned.

Often you know conditional probabilities and want a joint one. A bag holds 5 red and 3 blue marbles. Draw two without replacement. What’s the chance both are red? The second draw depends on the first.

Multiply both sides of the definition of conditional probability by \(P(B)\):

This is the multiplication rule: the chance that both happen is the chance that the first happens times the chance the second happens given the first. For three events it chains: \(P(A \cap B \cap C) = P(A)\,P(B \mid A)\,P(C \mid A \cap B)\).

For the marbles, with \(R_1\) = "first is red", \(R_2\) = "second is red":

Check by counting: \(\binom52 / \binom82 = 10/28 = 5/14\). ✓ Two different methods, same answer.

A tree diagram draws the multiplication rule. Each level is a stage of the experiment; each branch carries the conditional probability of that branch given the path so far. The probability of a complete path is the product of the probabilities along it, and the probability of an event is the sum of the paths that make it up.

For the marbles, "exactly one red" consists of two paths, RB and BR:

And \(P(\text{BB}) = \frac38 \times \frac27 = \frac{6}{56}\). The four paths sum to \(\frac{20 + 15 + 15 + 6}{56} = 1\). ✓

A tree diagram is the right tool whenever an outcome happens in stages. Everyday: the chance of being dealt two aces from a shuffled deck is \(\tfrac{4}{52}\times\tfrac{3}{51} = \tfrac{12}{2652} = \tfrac{1}{221}\), about 0.45%, which is why poker players treat it as a once-in-an-evening event. Science: a diagnostic pathway (screen, then confirm, then treat) is a tree, as is a multi-stage chemical synthesis whose overall yield is the product of the stage yields. Computing: a funnel in product analytics (visit, then sign up, then pay) multiplies conditional conversion rates; 20% sign up and 10% of those pay gives \(0.2\times 0.1 = 2\%\) of visitors paying.

Sometimes learning \(B\) tells you nothing about \(A\). Knowing the red die shows 3 says nothing about the blue die. Knowing it rained in Tokyo says nothing about a coin toss in London. We need a word for this, because it simplifies calculations enormously, and because wrongly assuming it causes some of the worst mistakes in applied probability.

\(A\) and \(B\) are independent if conditioning on \(B\) doesn’t change the probability of \(A\): \(P(A \mid B) = P(A)\). Substituting the definition of conditional probability and multiplying by \(P(B)\) gives the symmetric form usually taken as the definition.

In the dice example, "total is 8" and "red is even" are dependent: \(P(A \mid B) = 1/6 \ne 5/36 = P(A)\). In the deploy table, "incident" and "Friday" are dependent: \(0.12 \ne 0.064\).

By contrast, let \(C\) = "total is 7" and \(B\) = "red is even". The totals of 7 with even red are \((2,5), (4,3), (6,1)\), so \(P(C \mid B) = 3/18 = 1/6\), and \(P(C) = 6/36 = 1/6\). Equal, so \(C\) and \(B\) are independent. Independence is a numerical fact, not always something you can see in advance.

Independence is how engineers compute reliability. Suppose each of three servers is up 99% of the time, independently. Try it: Build your own reliability diagram; Three replicas in parallel; Three servers in series.

A factory has two production lines. Line 1 makes 60% of the chips and 2% of its chips are defective; line 2 makes 40% and 5% of its chips are defective. What fraction of all chips is defective? You know the defect rate conditional on each line; you want the overall rate.

The lines split the sample space into disjoint pieces that cover everything. Every defective chip came from exactly one line, so

The overall defect rate is 3.2%, a weighted average of the line rates with weights equal to each line’s share.

The law is a "divide and conquer" strategy: when \(P(A)\) is hard, split the world into cases where it’s easy, and recombine with weights.

A disease affects 1% of people. A test for it has a 99% true-positive rate (if you have the disease, it’s positive 99% of the time) and a 5% false-positive rate (if you don’t, it’s still positive 5% of the time). You test positive. What is the probability you have the disease? Try it: The test as 1,000 people.

Most people, including, in published studies, most doctors, answer something like 95% or 99%. The true answer is about 17%. Let’s see why, two ways.

Imagine 10,000 people taking the test. Replace each probability with a count: Try it: Medical test as frequencies.

You are one of the 594 positives. Of those, 99 are sick. So

The test is good, but the disease is rare. Healthy people are 99 times as numerous as sick ones, so even a small false-positive rate among the healthy produces five times as many false alarms as true alarms. Conditioning on "positive" restricts you to the 594 positives, and in that restricted world, sick people are a minority. This is the base-rate fallacy: ignoring how common the condition was in the first place (its base rate or prior).

Nothing new is needed; Bayes' theorem is the definition of conditional probability, used twice. The multiplication rule gives \(P(A \cap B)\) two ways:

Set them equal and divide by \(P(B)\):

The denominator \(P(B)\) is usually not given directly, so expand it with the law of total probability over \(A\) and \(A^c\):

That’s Bayes' theorem. It "inverts" a conditional probability: from \(P(B \mid A)\) (which a lab can measure: how does the test behave on sick people?) to \(P(A \mid B)\) (which the patient wants: given my result, am I sick?).

With \(D\) = disease and \({ + }\) = positive test: \(P(D) = 0.01\), \(P(D^c) = 0.99\), \(P( + \mid D) = 0.99\), \(P( + \mid D^c) = 0.05\).

Same answer as the tree, because the tree is the formula: 99 is \(10\,000 \times 0.0099\) and 594 is \(10\,000 \times 0.0594\).

What if you take a second, independent test and it’s also positive? Use the posterior as the new prior: \(P(D) = 1/6\). Try it: The second positive test; Add a second test.

Two positives take you from 1% to about 80%. Evidence accumulates; this is why doctors confirm a positive screening test with a second, different test (which also helps ensure the "independent" assumption is reasonable).

The simulation does exactly what conditioning means: it throws away every simulated patient who tested negative and asks what fraction of the rest are sick.

Bayes' theorem is even simpler in odds. Divide the Bayes formula for \(H\) by the one for \(H^c\); the awkward denominator \(P(E)\) cancels:

For the test: prior odds \(1{:}99\); likelihood ratio \(0.99/0.05 = 19.8\); posterior odds \(19.8{:}99 = 1{:}5\), i.e. probability \(1/6\). ✓ A second positive multiplies by 19.8 again: \(19.8{:}5 \approx 4{:}1\), about 80%. ✓

In a game show there are three doors: a car behind one, goats behind the other two. You pick a door, say door 1. The host, who knows where the car is, opens one of the other doors to reveal a goat (if both hide goats he picks one at random), and offers you the chance to switch to the remaining closed door. Should you? Try it: Play Monty Hall.

The almost universal first reaction is "two doors left, so it’s 50–50; switching doesn’t matter". That’s wrong: switching wins with probability 2/3.

Argument 1: what your first pick tells you. Your first pick is right with probability 1/3 and wrong with probability 2/3. The host’s action never changes that: he can always open a goat door, whatever you picked. If you were right (prob. 1/3), switching loses. If you were wrong (prob. 2/3), the host has been forced to reveal the other goat, so the remaining door must hide the car, and switching wins. Switching wins exactly when your first pick was wrong: probability 2/3.

Argument 2: Bayes. Let \(C_i\) = "car behind door \(i\)" and \(O_3\) = "host opens door 3". You picked door 1. Priors: \(P(C_i) = 1/3\). Likelihoods of the host’s action:

The host’s choice carries information because it is constrained: he will never open the car’s door. The intuition "50–50" would be right if the host opened a door at random and happened to reveal a goat; that’s a different experiment (try it in the simulation below).

In Chapter 24 you counted the ways for \(n\) people to have distinct birthdays. Now read the same calculation as a chain of conditional probabilities. Ignore leap years and assume all 365 days equally likely. Add people one at a time. Given that the first \(k\) people all have different birthdays, person \(k + 1\) avoids all of them with probability \((365 - k)/365\). By the multiplication rule,

For \(n = 23\) this gives \(0.507\): better than even. The surprise is resolved by counting pairs, not people: 23 people make \(\binom{23}{2} = 253\) pairs, and each pair matches with probability \(1/365\). Try it: Birthday problem calculator.

An approximation (optional, uses \(e\) from Chapter 12). For small \(x\), \(1 - x \approx e^{-x}\). Each factor is \(1 - k/365 \approx e^{-k/365}\), so the product is about

The exponent \(n(n-1)/2\) is the number of pairs. For \(n = 23\), \(1 - e^{-253/365} \approx 0.500\). Setting the probability to 1/2 and solving gives \(n \approx 1.18\sqrt{365} \approx 22.5\). In general, with \(N\) equally likely values, a repeat becomes likely after about \(\sqrt{N}\) draws.

Try it: Birthday bound for hashes.

The problem. Quicksort picks a pivot, partitions the array into elements smaller and larger than the pivot, and recurses. If the pivot is always the first element, a sorted input makes every partition maximally lopsided, and quicksort takes about \(n^2/2\) comparisons instead of about \(n \log n\). An adversary (or just unlucky real-world data, which is often nearly sorted) can always find the bad input for a fixed rule.

The idea. Choose the pivot uniformly at random. Now there are no bad inputs, only bad luck, and bad luck is rare: for every input, the expected number of comparisons is about \(2n \ln n \approx 1.39\, n \log_2 n\). (The derivation uses linearity of expectation; see Chapter 30.) The probability shifts from the input, which you don’t control, to the coin flips, which you do.

A Monte Carlo example: Freivalds' algorithm. Given \(n \times n\) matrices \(A\), \(B\), \(C\) (Chapter 27), is \(AB = C\)? Multiplying out costs about \(n^3\) operations. Instead, pick a random vector \(r\) of 0s and 1s and check whether \(A(Br) = Cr\): three matrix–vector products, about \(3n^2\) operations. If \(AB = C\), the check always passes. If \(AB \ne C\), one can show it fails with probability at least 1/2. After 20 independent rounds that all pass, the chance of being fooled is at most \(2^{-20} \approx 10^{-6}\), by independence of the rounds.

Choosing between them. Prefer Las Vegas when a wrong answer is unacceptable and you can tolerate variable latency (sorting, hashing with retries). Prefer Monte Carlo when a fixed time budget matters and you can make the error probability smaller than, say, the chance of a cosmic-ray bit flip (primality testing in cryptography, as in Chapter 23, is the classic case).

The problem. Decide whether an incoming message is spam from the words it contains. You have labelled history, from which you can measure how often each word appears in spam and in legitimate mail ("ham"). This is the medical test again, with words as test results. Try it: Train the spam filter.

The model. Let \(S\) = "spam". For a message containing words \(w_1, \ldots, w_k\), Bayes gives

Estimating \(P(w_1, \ldots, w_k \mid S)\) for every combination of words is hopeless: there are too many combinations. The naive assumption is that words are conditionally independent given the class:

It’s obviously false ("Nigerian" and "prince" are not independent in spam), but the classifier only needs to rank spam above ham, and it does that well. Compute an unnormalized score for each class, then divide by their sum (the law of total probability, in disguise).

Worked example. Training data: 4 spam and 6 ham messages.

Estimates (fraction of messages in the class that contain the word):

A new message contains "free" and "meeting". Scores:

Mildly spammy. "Free" alone would give \(0.3/(0.3 + 0.1) = 0.75\); the word "meeting" pulled it back towards ham.

Try it: Fix it with smoothing; See the zero-count problem.

The problem. You want a compact set that answers "have I seen this URL / key / username before?" using far less memory than storing the items. You can accept occasional false positives ("probably yes" when the answer is no) but never false negatives. Databases use this to skip disk reads; browsers once used it to check URLs against malware lists. Try it: Bloom filter explorer.

The data structure. A Bloom filter is an array of \(m\) bits, all 0, plus \(k\) hash functions. To add an item, hash it \(k\) ways and set those \(k\) bits to 1. To query, check the \(k\) bits: if any is 0, the item was definitely never added; if all are 1, it probably was.

The probability. Insert \(n\) items. Treat each hash as a uniformly random, independent position. Focus on one particular bit. (The last step uses \((1 - \tfrac1m)^m \approx e^{-1}\), an optional fact from Chapter 12.)

So a bit is 1 with probability about \(1 - e^{-kn/m}\). A query for a new item gives a false positive when all \(k\) of its bits happen to be 1. Treating those as independent:

There’s a tradeoff in \(k\): more hashes give each query more chances to find a 0, but also fill the array faster. The best choice turns out to be \(k \approx (m/n)\ln 2\). With \(m/n = 10\) bits per item, \(k \approx 6.9\), and the false-positive rate is under 1%.

The independence assumptions in the derivation are not exactly true, but measurement agrees with prediction to within the noise. That’s a pattern worth noticing: a model built on slightly false assumptions can still be extremely useful, provided you check it.