Difficulty: Intermediate | Prerequisites: Chapter 6 (counting, permutations, combinations)
Tags: probability, sample space, event, complement, union, independent events, conditional probability, Bayes theorem, Bernoulli trials, random variable, expected value, variance, probability distribution, uniform distribution, Monty Hall, birthday problem, CS182, discrete math, Purdue
Discrete probability quantifies uncertainty over finite or countable sample spaces. Every time you estimate how likely a cyberattack is, calculate the expected number of comparisons in a randomised algorithm, or assess whether a test result is a false positive, you are doing discrete probability. This chapter builds directly on counting (Chapter 6), adding the notion of likelihood. You need to be fluent with combinations, permutations, and the product/sum rules before starting.
Probability assigns a number between 0 and 1 to each event, measuring how likely it is. For equally likely outcomes, p(E) = |E| / |S|. Complements, unions, conditional probability, and independence give you tools to combine and decompose probabilities. Bayes' theorem reverses conditional probabilities. Expected value gives the long-run average of a random variable.
Experiment
A procedure that yields one outcome from a set of possible outcomes.
Sample space (S)
The set of all possible outcomes of an experiment.
Event (E)
A subset of the sample space. An event occurs if the actual outcome is in E.
Probability of an event
If S is a finite sample space with equally likely outcomes and E is an event, then p(E) = |E| / |S|.
Probability distribution
A function p that assigns to each outcome s in S a probability p(s), where all probabilities are between 0 and 1 and sum to 1.
Uniform distribution
Every outcome has the same probability. For |S| = n, each outcome has probability 1/n.
Complement
The complement of E is Eᶜ = S - E. p(Eᶜ) = 1 - p(E). In simple terms, the probability of E not happening is one minus the probability of E happening.
Union of events
p(A ∪ B) = p(A) + p(B) - p(A ∩ B). This avoids double-counting the overlap.
Independent events
Events A and B are independent if p(A ∩ B) = p(A) × p(B). Equivalently, p(A | B) = p(A). In simple terms, knowing B happened tells you nothing about A.
Conditional probability
p(E | F) = p(E ∩ F) / p(F). The probability of E given that F has occurred.
Bayes' theorem
P(m | s) = P(s | m) × P(m) / P(s). Reverses the direction of conditioning.
Bernoulli trial
An experiment with exactly two outcomes: success (probability p) and failure (probability q = 1 - p).
Random variable
A function from the sample space to the real numbers, assigning a numerical value to each outcome.
Expected value (E(X))
The weighted average of all values a random variable can take: E(X) = Σ x × p(X = x). Also called the mean.
Variance (V(X))
A measure of how spread out the values are: V(X) = E((X - E(X))²).
For a finite sample space S with equally likely outcomes:
p(E) = |E| / |S|
p(S) = 1, p(∅) = 0
0 <= p(E) <= 1 for every event E
Complement: p(Eᶜ) = 1 - p(E). Often easier to count what you do not want and subtract.
Union: p(A ∪ B) = p(A) + p(B) - p(A ∩ B).
Independent events: p(A ∩ B) = p(A) × p(B).
|S| = C(52, 5) = 2,598,960
Easier to count the complement: hands with no aces = C(48, 5) = 1,712,304
p(at least one ace) = 1 - 1,712,304 / 2,598,960 ≈ 0.341
Choose 5 kinds from 13: C(13, 5). For each kind, choose 1 of 4 suits: 4⁵.
|E| = C(13, 5) × 4⁵ = 1,317,888
p = 1,317,888 / 2,598,960 ≈ 0.507
p(single roll < 5) = 4/6 = 2/3
Rolls are independent: p(all 10 rolls < 5) = (2/3)¹⁰ = 1024/59,049 ≈ 0.0173
|S| = 36 (6 × 6 outcomes)
Count pairs (i, j) with i + j <= 7: there are 21 such pairs.
p = 21/36 = 7/12
A royal flush is {10, J, Q, K, A} of one suit. There are 4 royal flushes.
p = 4 / C(52, 5) = 4 / 2,598,960 ≈ 0.0000015
You pick a door. The host opens a door with a goat. You can switch or stay.
p(win by staying) = 1/3
p(win by switching) = 2/3
Always switch.
p(initial choice correct) = 1/5, so p(stay and win) = 1/5 = 3/15
p(initial choice wrong) = 4/5. The host opens 3 goat doors, leaving one other door.
p(switch and win) = (4/5) × (1/3) = 4/15
p(switch and lose) = (4/5) × (2/3) = 8/15
Check: 3/15 + 4/15 + 8/15 = 15/15 = 1. Switching is still better.
E₁ (sum odd): 18 outcomes. E₂ (product odd): 9 outcomes.
These are disjoint (if the product is odd, both dice are odd, so the sum is even).
p(E₁ ∪ E₂) = 18/36 + 9/36 = 27/36 = 3/4
|S| = 2¹⁰ = 1024
Count outcomes with 3 to 7 heads: C(10,3) + C(10,4) + C(10,5) + C(10,6) + C(10,7) = 120 + 210 + 252 + 210 + 120 = 912
p = 912/1024 ≈ 0.8906
|S| = 13³ = 2,197 (each variable chosen independently from {0,...,12})
|E| = C(14, 2) = 91 (stars and bars for non-negative integer solutions)
p = 91/2,197 ≈ 0.0414
When outcomes are not equally likely, assign probabilities directly.
Example: a weighted die where 3 appears twice as often as other numbers.
p(3) = 2/7, p(1) = p(2) = p(4) = p(5) = p(6) = 1/7
p(odd number) = p(1) + p(3) + p(5) = 1/7 + 2/7 + 1/7 = 4/7
p(E | F) = p(E ∩ F) / p(F).
Example: a random 4-bit string. E = contains two consecutive 0s. F = first bit is 0.
E ∩ F = {0000, 0001, 0010, 0011, 0100}: 5 strings
p(E ∩ F) = 5/16
p(F) = 8/16 = 1/2
p(E | F) = (5/16) / (1/2) = 5/8
Example: family with two children, probability both are boys given at least one is a boy.
S = {BB, BG, GB, GG}. F = at least one boy = {BB, BG, GB}. E = both boys = {BB}.
p(E | F) = (1/4) / (3/4) = 1/3
Each trial has two outcomes: success (p) and failure (q = 1 - p).
The probability of exactly k successes in n independent trials: C(n, k) × pᵏ × qⁿ⁻ᵏ.
Example: biased coin with p(H) = 2/3, flipped 7 times. Probability of exactly 4 heads:
C(7, 4) × (2/3)⁴ × (1/3)³ = 35 × 16/81 × 1/27 = 35 × 16/2187 = 560/2187
A random variable X assigns a real number to each outcome. Its distribution lists each value r and p(X = r).
Example: coin flipped 3 times, X = number of heads.
p(X=0) = 1/8, p(X=1) = 3/8, p(X=2) = 3/8, p(X=3) = 1/8
E(X) = 0(1/8) + 1(3/8) + 2(3/8) + 3(1/8) = 12/8 = 3/2
Linearity of expectation: E(X + Y) = E(X) + E(Y), regardless of whether X and Y are independent.
Bayes' theorem: P(m | s) = P(s | m) × P(m) / P(s). Used to update beliefs given new evidence.
Variance: V(X) = E((X - E(X))²). Measures spread around the mean.
How many people are needed so that the probability of at least two sharing a birthday exceeds 1/2?
Assume 366 possible birthdays (including Feb 29).
pₙ = (365/366)(364/366)...(367-n)/366 is the probability all n people have different birthdays.
1 - pₙ > 1/2 when n = 23.
p(E) = |E| / |S| (equally likely outcomes)
p(Eᶜ) = 1 - p(E)
p(A ∪ B) = p(A) + p(B) - p(A ∩ B)
p(A ∩ B) = p(A) × p(B) (if independent)
p(E | F) = p(E ∩ F) / p(F)
Bernoulli: p(k successes in n trials) = C(n,k) pᵏ qⁿ⁻ᵏ
E(X) = Σ x × p(X = x)
E(X + Y) = E(X) + E(Y)
V(X) = E((X - E(X))²)
The Monty Hall problem illustrates how conditional probability defies intuition, which matters in game theory and decision-making. Bernoulli trials model any repeated binary experiment (coin flips, pass/fail tests, packet transmission success). Expected value is used in finance (expected return), operations research (expected queue length), and machine learning (expected loss). Bayes' theorem is the foundation of spam filters, medical diagnostics, and Bayesian inference.
"If I switch in Monty Hall, it is 50/50." It is not. Switching gives 2/3. The host's action gives you information.
"Independent events cannot happen at the same time." Independence means one event does not affect the probability of the other. They can absolutely both occur.
"Expected value must be a possible outcome." E(X) = 3/2 for three coin flips, but you cannot flip 1.5 heads. Expected value is a long-run average, not necessarily a realisable outcome.
"The birthday problem needs 183 people for a 50% match." It only takes 23 people, which surprises most students. The rapid growth comes from the number of pairs: C(23, 2) = 253.
⚠️ Master the complement technique. If "at least one" appears in a problem, compute the complement ("none") and subtract from 1.
⚠️ For Bernoulli trial problems, identify n, k, p, and q before plugging into the formula.
⚠️ Know how to set up conditional probability problems: identify E, F, E ∩ F.
⚠️ Be able to compute expected value from a probability distribution table.
⚠️ The Monty Hall problem (including the 5-door variant) is a common exam question. Know the reasoning, not just the answer.
Fill in the blank: p(Eᶜ) = ______.
True or False: p(A ∪ B) = p(A) + p(B) always.
Fill in the blank: The probability of exactly 3 successes in 5 independent Bernoulli trials with p = 0.5 is ______.
True or False: E(X + Y) = E(X) + E(Y) only if X and Y are independent.
Fill in the blank: In the birthday problem, ______ people are needed for a >50% probability of a shared birthday.
Answers: 1. 1 - p(E). 2. False (only if A and B are disjoint; otherwise subtract p(A ∩ B)). 3. C(5,3)(0.5)³(0.5)² = 10/32 = 5/16. 4. False (linearity holds regardless of independence). 5. 23.
Q: What is the probability that a 5-card poker hand is a flush (all one suit)?
A: Choose a suit: 4 ways. Choose 5 from 13 cards of that suit: C(13, 5). Total flush hands: 4 × C(13, 5) = 5,148. But subtract the 40 straight flushes if the problem asks for non-straight flushes. For any flush: p = 5,148 / 2,598,960 ≈ 0.00198.
Q: A fair die is rolled twice. What is p(sum is odd or sum > 8)?
A: E₁ (sum odd): 18/36 = 1/2. E₂ (sum > 8): outcomes summing to 9,10,11,12 = 4+3+2+1 = 10/36 = 5/18. E₁ ∩ E₂ (sum odd AND > 8): sums 9 and 11 = 4+2 = 6/36 = 1/6. p = 1/2 + 5/18 - 1/6 = 9/18 + 5/18 - 3/18 = 11/18.
Q: A biased coin has p(H) = 2/3. What is the expected number of heads in 7 flips?
A: By linearity, E(X) = 7 × (2/3) = 14/3 ≈ 4.67.
Q: What is p(E | F) if p(E ∩ F) = 0.3 and p(F) = 0.6?
A: p(E | F) = 0.3 / 0.6 = 0.5.
Probability is built on counting (Chapter 6): every probability calculation requires counting |E| and |S|. It connects to algorithm analysis (Chapter 3) when analysing expected-case runtime. Random variables and expected value appear in the study of randomised algorithms. Bayes' theorem is foundational to machine learning and statistics courses.
discrete probability, sample space, event, probability distribution, uniform distribution, complement rule, union rule, inclusion-exclusion, independent events, conditional probability, Bayes theorem, Bernoulli trials, binomial probability, random variable, expected value, mean, variance, Monty Hall problem, birthday problem, poker probability, dice probability, coin flip, CS 182, Purdue, discrete math