Difficulty: Intermediate | Prerequisites: Counting principles (product rule, binomial coefficients), basic set operations (union, intersection, complement).
Probability builds on the counting techniques from the companion notes. Once you can count outcomes, you can compute how likely an event is. This material covers discrete probability fundamentals: symmetry arguments, the inclusion-exclusion principle, the binomial distribution, and Bayes' theorem. These tools are essential across computer science, from algorithm analysis to machine learning. You should be comfortable with combinations and basic set notation before diving in.
Use inclusion-exclusion when computing P(A or B) to avoid double-counting. The binomial distribution handles "exactly k successes in n trials." Bayes' theorem flips conditional probabilities, letting you go from P(evidence | hypothesis) to P(hypothesis | evidence). Symmetry arguments can shortcut problems elegantly.
Sample space
The set of all possible outcomes of an experiment. For a fair coin flipped 5 times, the sample space has 2^5 = 32 elements.
Think of it as: the complete list of everything that could happen.
Event
A subset of the sample space. "More heads than tails in 5 flips" is an event containing all sequences with 3, 4, or 5 heads.
In simple terms: the specific thing you are asking about the probability of.
Inclusion-exclusion principle
P(A ∪ B) = P(A) + P(B) - P(A ∩ B). Corrects for the overlap when two events can both occur.
Think of it as: add both, then subtract what you counted twice.
Conditional probability
P(A | B) = P(A ∩ B) / P(B). The probability of A given that B has occurred.
In simple terms: once you know B happened, how likely is A within that narrower world?
Bayes' theorem
P(H | E) = P(E | H) * P(H) / P(E). Lets you reverse a conditional probability: from "how likely is the evidence given the hypothesis" to "how likely is the hypothesis given the evidence."
Think of it as: updating your belief about a cause after observing its effect.
Binomial distribution
The probability of exactly k successes in n independent trials, each with success probability p: P(X = k) = C(n, k) * p^k * (1 - p)^(n - k).
In simple terms: how likely is it that something happens exactly k times out of n tries?
Symmetry argument
A reasoning technique that pairs outcomes with their "opposites" to show that a set of outcomes accounts for exactly half (or some other fraction) of the total.
Think of it as: if every outcome has a mirror image, the two halves must be equal in size.
Consider n >= 5 fair coin flips. What is the probability that the first 5 tosses have more heads than tails?
Key insight: every sequence (e.g. HTHTH) has an "opposite" (THTHT) formed by swapping all heads and tails.
If the original has more heads, the opposite has more tails, and vice versa.
This pairing is one-to-one, so exactly half the sequences have more heads than tails.
Answer: 1/2.
Note: the condition n >= 5 is there so that additional flips beyond the first 5 exist, but they do not affect the first 5. The first 5 flips are independent of anything after them.
Problem: roll a fair die twice. What is P(at least one roll is a 1)?
Let R1 = "first roll is 1" and R2 = "second roll is 1."
P(R1 ∪ R2) = P(R1) + P(R2) - P(R1 ∩ R2).
P(R1) = 1/6, P(R2) = 1/6, and since the rolls are independent, P(R1 ∩ R2) = 1/6 x 1/6 = 1/36.
P(R1 ∪ R2) = 6/36 + 6/36 - 1/36 = 11/36.
Without inclusion-exclusion, you would double-count the outcome (1, 1).
Among the first 125 positive integers (1 through 125), there are 63 odd and 62 even.
P(randomly chosen integer is odd) = 63/125 = 0.504.
Why not 0.5? Because 125 is odd, there is one more odd number than even in the range.
17 people at a party, 2 dressed as skeletons (a skeleton witch and a skeleton warrior). 2 winners are chosen at random.
P(at least one skeleton wins) uses inclusion-exclusion.
Total ways to choose 2 from 17: C(17, 2) = 136.
Ways including the witch: C(16, 1) = 16 (pick one more from the remaining 16).
Ways including the warrior: also 16.
Ways including both: 1 (only one way to pick both skeletons).
P(at least one skeleton) = (16 + 16 - 1) / 136 = 31/136.
Roll a fair die 10 times. P(exactly 5 sixes)?
This is a binomial distribution problem: n = 10 trials, k = 5 successes, p = 1/6.
P(X = 5) = C(10, 5) * (1/6)^5 * (5/6)^5 = 0.0130.
C(10, 5) = 252. The (1/6)^5 accounts for the 5 sixes, and (5/6)^5 for the 5 non-sixes.
Setup: 8% of astronauts are imitators (P(I) = 0.08). Imitators act dubiously 98% of the time (P(D|I) = 0.98). Non-imitators act dubiously 9% of the time (P(D|not I) = 0.09).
Question: given that an astronaut is acting dubiously, what is P(I|D)?
Apply Bayes' theorem:
Numerator: P(D|I) * P(I) = 0.98 x 0.08 = 0.0784.
Denominator: P(D|I) * P(I) + P(D|not I) * P(not I) = 0.0784 + 0.09 x 0.92 = 0.0784 + 0.0828 = 0.1612.
P(I|D) = 0.0784 / 0.1612 = 0.471, or 47.1%.
Key takeaway: even though imitators almost always act dubiously (98%), the low base rate (8%) means a dubious astronaut is still more likely to be innocent than guilty. This is the base rate fallacy in action.
P(A \cup B) = P(A) + P(B) - P(A \cap B)P(X = k) = \binom{n}{k} p^k (1-p)^{n-k}P(H \mid E) = \frac{P(E \mid H) \cdot P(H)}{P(E \mid H) \cdot P(H) + P(E \mid \neg H) \cdot P(\neg H)}P(A \mid B) = \frac{P(A \cap B)}{P(B)}Inclusion-exclusion is used in network reliability calculations: what is the probability that at least one of several redundant links is operational? The same logic applies to quality control, where you want P(at least one defect).
Bayes' theorem is the foundation of spam filters, medical diagnostic tests, and machine learning classifiers. The imitator problem in the quiz is structurally identical to asking: "Given a positive test result, what is the probability the patient has the disease?"
The binomial distribution models anything with fixed independent trials and two outcomes: manufacturing defect rates, A/B testing conversion rates, or clinical trial success counts.
Students forget to subtract P(A ∩ B) when using inclusion-exclusion, leading to double-counted outcomes. If both events can happen simultaneously, you must subtract the overlap.
In Bayes' theorem problems, students often confuse P(D|I) with P(I|D). These are different quantities. The whole point of Bayes' theorem is to convert one into the other.
The base rate fallacy: students assume that if the test is highly accurate (98% detection rate), a positive result almost certainly means the hypothesis is true. When the base rate is low (8% imitators), the posterior can still be well under 50%.
For the binomial distribution, students sometimes forget the C(n, k) coefficient, computing only p^k * (1 - p)^(n - k). The coefficient accounts for which specific trials are the successes.
Inclusion-exclusion is almost guaranteed to appear. Know the formula cold and practise identifying when events overlap.
Bayes' theorem problems typically give you three numbers (prior, true positive rate, false positive rate) and ask for the posterior. Set up the formula methodically.
The binomial distribution question format is standard: "n trials, probability p, exactly k successes." Identify n, k, and p, then plug in.
Symmetry arguments are elegant but tricky to spot. If the problem involves a fair coin or a symmetric setup, consider whether a pairing argument works before computing anything.
True or false: P(A ∪ B) = P(A) + P(B) always holds, even when A and B can both occur.
Answer: False. You must subtract P(A ∩ B) unless A and B are mutually exclusive.
Fill in the blank: in the binomial distribution formula, the C(n, k) term accounts for ___.
Answer: The number of ways to choose which k trials are the successes.
True or false: P(D|I) and P(I|D) are the same thing.
Answer: False. Bayes' theorem relates the two, but they are generally different.
Fill in the blank: for a fair coin flipped 5 times, the probability of more heads than tails is ___.
Answer: 1/2, by the symmetry argument.
True or false: if a disease test has a 99% detection rate and the disease prevalence is 1%, a positive result means there is a 99% chance of having the disease.
Answer: False. This is the base rate fallacy. The posterior depends on the false positive rate and the prevalence.
Q: You roll two fair dice. What is the probability that at least one die shows a 6?
A: P(R1 ∪ R2) = 1/6 + 1/6 - 1/36 = 11/36. Same structure as the "at least one 1" problem.
Q: A fair die is rolled 8 times. What is the probability of getting exactly 3 fives?
A: C(8, 3) * (1/6)^3 * (5/6)^5 = 56 * (1/216) * (3125/7776) ≈ 0.1042.
Q: At a party of 20 people, 3 are wearing red. If 2 winners are chosen at random, what is P(at least one wears red)?
A: Total pairs = C(20, 2) = 190. Pairs with at least one red: use inclusion-exclusion or complement. Complement method: pairs with no red = C(17, 2) = 136. P(at least one red) = 1 - 136/190 = 54/190 = 27/95 ≈ 0.284.
Q: 5% of emails are spam. A spam filter catches 95% of spam and incorrectly flags 3% of legitimate emails. An email is flagged. What is P(spam | flagged)?
A: P(S|F) = (0.95 x 0.05) / (0.95 x 0.05 + 0.03 x 0.95) = 0.0475 / (0.0475 + 0.0285) = 0.0475 / 0.076 ≈ 0.625.
Q: Explain why P(imitator | dubious) is only 47.1% when imitators act dubiously 98% of the time.
A: Because the prior probability of being an imitator is low (8%). Although imitators almost always look dubious, the large non-imitator population (92%) contributes a substantial number of false alarms (9% of 92% = 8.28%). The evidence from dubious behaviour is diluted by the low base rate.
The counting principles from the companion notes (product rule, C(n, k)) are the raw material for the probability calculations here. Every probability in this document has a counting step in its denominator.
Bayes' theorem connects to machine learning: Naive Bayes classifiers, prior and posterior distributions in Bayesian inference, and the expectation-maximisation algorithm all build on this foundation.
The binomial distribution is a special case of the broader family of discrete distributions. It generalises to the multinomial distribution (more than two outcomes per trial) and connects to the normal distribution via the central limit theorem when n is large.
Probability, discrete probability, inclusion-exclusion principle, union of events, conditional probability, Bayes' theorem, Bayes' rule, posterior probability, prior probability, base rate fallacy, binomial distribution, binomial coefficient, fair coin, symmetry argument, sample space, event, independent events, complementary counting, P(A or B), P(A given B), imitator problem, Among Us probability, CS182, foundations of computer science, discrete mathematics, Purdue CS182 Quiz 9