Difficulty: Intermediate | Prerequisites: Combinatorics and counting principles (see companion study notes), factorials, basic fractions.
Probability is the formal language for reasoning about uncertainty. In computer science it underpins algorithm analysis, machine learning, networking, and cryptography. This set of notes covers the core probability tools you need for a CS 182 exam: basic probability via counting, conditional probability, the complement rule, the binomial distribution, and sequential coin-toss problems. You should already be comfortable computing combinations C(n, k) and understanding sample spaces.
TL;DR: Most exam-level probability problems follow one pattern: define the sample space, count the favourable outcomes using combinatorics, and divide. Conditional probability adjusts the sample space. The complement rule lets you count what you want by subtracting what you do not want. The binomial distribution handles repeated independent trials.
Sample space (S)
The set of all possible outcomes of an experiment. In simple terms, it is the complete list of everything that could happen.
Event
A subset of the sample space. An event "occurs" when the actual outcome falls within that subset. Think of it as the collection of outcomes you care about.
Probability of an event, P(E)
When all outcomes are equally likely: P(E) = |E| / |S|, where |E| is the number of favourable outcomes and |S| is the total number of outcomes. In simple terms, it is the fraction of the time this event happens if you repeat the experiment many times.
Conditional probability, P(A | B)
The probability of event A given that event B has already occurred: P(A | B) = P(A ∩ B) / P(B). Think of it as shrinking the sample space to only those outcomes where B is true, then asking how often A also holds.
Complement rule
P(E) = 1 - P(E'), where E' is the complement of E (everything not in E). In simple terms, if a direct count is hard, count the opposite and subtract from 1.
Binomial distribution
The probability of getting exactly k successes in n independent trials, each with success probability p: P(X = k) = C(n, k) · p^k · (1 - p)^(n - k). Think of it as the go-to model for "flip a coin n times, how likely is exactly k heads?"
Cumulative binomial probability
The probability of getting at most k successes: P(X ≤ k) = Σ from i = 0 to k of C(n, i) · p^i · (1 - p)^(n - i). In simple terms, sum the individual binomial probabilities from 0 up to k.
When the sample space is finite and all outcomes are equally likely, probability reduces to a counting exercise.
Total outcomes for drawing 2 cards from a 52-card deck: C(52, 2)
Favourable outcomes for both cards being aces: C(4, 2), since there are 4 aces and you need 2 of them
Probability both are aces: C(4, 2) / C(52, 2) = 6 / 1326 = 1/221
The denominator is always the size of the sample space. The numerator is the number of outcomes matching your event. Get both counts right and the probability follows.
Conditional probability is used when you have partial information. The sample space shrinks to only those outcomes consistent with what you already know.
Example: You are dealt 2 cards. You reveal the first and it is an ace. What is the probability the second is also an ace?
After seeing one ace, there are 51 cards remaining in the deck, of which 3 are aces.
P(second is ace | first is ace) = 3/51 = 1/17.
This can also be derived from the formula: P(A ∩ B) / P(B), but the direct counting approach (shrink the deck) is usually faster and less error-prone for card problems.
Note that revealing both cards simultaneously vs. revealing one first are different framings of the same physical deal, but they set up different probability questions. Simultaneous reveal asks for P(both aces) = C(4,2)/C(52,2). Sequential reveal with a known first card asks for P(second ace | first ace) = 3/51.
When it is easier to count the outcomes you do not want, use the complement.
Example: Roll a fair 6-sided die three times. What is the probability that the maximum of the three rolls is ≥ 5?
Direct count: the max is 5 or 6. This requires inclusion-exclusion or careful case analysis.
Complement: the max is ≤ 4, meaning every roll is 1, 2, 3, or 4. Each roll has 4 favourable values out of 6.
P(max ≤ 4) = (4/6)³ = 64/216
P(max ≥ 5) = 1 - 64/216 = 152/216 = 19/27
The complement rule is especially powerful for "at least one" type questions. "At least one 6 in four rolls" = 1 - P(no sixes) = 1 - (5/6)⁴.
Use the binomial distribution when you have n independent trials, each with the same probability of success p, and you want the probability of a specific number of successes.
Example: A biased coin has P(heads) = 0.7. Toss it 100 times. What is the probability of getting ≤ 50 heads?
X ~ Binomial(n = 100, p = 0.7)
P(X ≤ 50) = Σ from k = 0 to 50 of C(100, k) · (0.7)^k · (0.3)^(100 - k)
This sum does not simplify to a neat closed form; in practice you would use a calculator, a table, or a normal approximation. For an exam, writing out the summation formula with the correct bounds is what earns full marks.
Key conditions for the binomial to apply:
Fixed number of trials (n)
Each trial is independent
Each trial has exactly two outcomes (success/failure)
The probability of success (p) is constant across trials
Some problems ask you to keep performing trials until a specific pattern occurs, then find the probability of a side condition.
Example: Toss a fair coin until four consecutive heads appear. What is the probability that exactly one tail is shown?
This requires careful enumeration of the sequences that end with HHHH and contain exactly one T.
Think about where the single tail can appear, given that the sequence must end with four consecutive heads:
The sequence is THHHH (tail first, then four heads). Length 5. This works: after the tail, four heads in a row ends the game.
The sequence is HTHHHH (head, tail, then four heads). Length 6. This also works: the first H does not start a run of four, the T resets, then four heads end it. But wait, does the game end earlier? After the first H, we have only 1 consecutive head. After T, we reset. After HHHH, we have four consecutive heads, so the game ends. Valid.
We also need to verify that HHTHHHH is not valid, because the game does not end early. After HH, the T resets the counter. Then HHHH gives four consecutive heads. This sequence has length 7 and exactly one tail, so it is also valid.
Similarly, HHHTHHHH has length 8, one tail, and ends with four consecutive heads.
For each candidate, we must confirm:
The sequence contains exactly one T
No earlier substring of the sequence has four consecutive H's (otherwise the game would have stopped before the T appeared)
The valid sequences are:
THHHH: no heads before the T, so no early termination. Probability: (1/2)⁵
HTHHHH: only 1 head before the T, no run of 4. Probability: (1/2)⁶
HHTHHHH: only 2 heads before the T. Probability: (1/2)⁷
HHHTHHHH: 3 heads before the T, still not 4. Probability: (1/2)⁸
If there were 4 or more heads before the T, the game would have already ended, so no further cases exist.
Total probability: (1/2)⁵ + (1/2)⁶ + (1/2)⁷ + (1/2)⁸ = 15/256
Basic probability: P(E) = |E| / |S|
Conditional probability: P(A | B) = P(A ∩ B) / P(B)
Complement rule: P(E) = 1 - P(E')
Binomial probability: P(X = k) = C(n, k) · p^k · (1 - p)^(n - k)
Cumulative binomial: P(X ≤ k) = Σ (i = 0 to k) C(n, i) · p^i · (1 - p)^(n - i)
Conditional probability is the foundation of Bayesian reasoning, which powers spam filters, medical diagnostics, and recommendation engines. The complement rule is used constantly in reliability engineering: the probability a system fails is 1 minus the probability every component works. The binomial distribution models quality control (how many defective items in a batch), A/B testing in tech, and network packet loss.
Students often confuse P(A and B) with P(A | B). Joint probability counts both events happening together across the full sample space. Conditional probability restricts the sample space to outcomes where B already occurred.
Forgetting that the complement rule requires the complement to cover all remaining outcomes. P(max ≥ 5) = 1 - P(max ≤ 4) only works because "≤ 4" and "≥ 5" are exhaustive and mutually exclusive.
Assuming the binomial applies when trials are not independent. If you draw cards without replacement, the trials are dependent and the hypergeometric distribution (not the binomial) applies.
In sequential coin-toss problems, students often miss that the game may end before the tail appears. You must verify that no prefix of your proposed sequence already triggers the stopping condition.
⚠️ Card-drawing problems test both counting and conditional probability. Be ready to set up C(n, k) expressions for the numerator and denominator.
⚠️ The complement rule saves time on almost every "at least" or "at most" question. If you are computing many cases directly, pause and ask whether the complement is simpler.
⚠️ The binomial distribution formula is likely to appear. Know the three conditions (fixed n, independent trials, constant p) and be ready to set up the sum, even if you do not compute it.
⚠️ Sequential-pattern problems (like tossing until four consecutive heads) reward careful enumeration. Write out each valid sequence explicitly.
True or False: P(A | B) = P(B | A) in general.
Fill in the blank: The probability of drawing 2 aces from a 52-card deck is C(4, 2) / ___.
True or False: If P(at least one head in 3 flips) is hard to compute directly, you can use 1 - P(no heads) = 1 - (1/2)³.
Fill in the blank: For a Binomial(n, p) distribution, the expected number of successes is ___.
True or False: When tossing a fair coin until HHHH, the sequence HHHH (no tails) is a valid outcome.
Q: Two cards are drawn from a 52-card deck. What is the probability both are aces?
A: C(4, 2) / C(52, 2) = 6 / 1326 = 1/221.
Q: The first card drawn is an ace. What is the probability the second card is also an ace?
A: 3/51 = 1/17. After removing one ace, 3 aces remain among 51 cards.
Q: You roll a fair die three times. What is the probability that the maximum roll is at least 5?
A: Use the complement. P(max ≤ 4) = (4/6)³ = 64/216. So P(max ≥ 5) = 1 - 64/216 = 152/216 = 19/27.
Q: A biased coin (P(H) = 0.7) is tossed 100 times. Write the formula for P(≤ 50 heads).
A: P(X ≤ 50) = Σ from k = 0 to 50 of C(100, k) · (0.7)^k · (0.3)^(100 - k).
Q: You toss a fair coin until four consecutive heads. What is the probability of exactly one tail?
A: The valid sequences are THHHH, HTHHHH, HHTHHHH, HHHTHHHH. Total probability: (1/2)⁵ + (1/2)⁶ + (1/2)⁷ + (1/2)⁸ = 15/256.
Probability connects directly to combinatorics (the companion notes): every probability calculation here uses counting as its engine. Conditional probability leads into Bayes' theorem, which is central to machine learning and statistical inference. The binomial distribution generalises to the multinomial distribution (multiple outcome categories) and connects to the Poisson distribution for rare events. Sequential stopping problems relate to Markov chains and expected-value calculations covered later in the course.
probability, sample space, event, conditional probability, Bayes rule, complement rule, complement method, binomial distribution, binomial probability, cumulative distribution, independent trials, card probability, dice probability, coin toss, consecutive heads, geometric probability, CS 182, CS182, Purdue, foundations of computer science, discrete maths, discrete probability