Week 2: Counting, Conditional Probability, and Independence

Reading: Casella & Berger (C&B) §§1.2.3–1.3

Notation. $N(A)$ is the number of outcomes in a finite set $A$. $n! = n(n-1)\cdots 2 \cdot 1$ with $0! = 1$. $\binom{n}{r} = \dfrac{n!}{r!\,(n-r)!}$ (“$n$ choose $r$”). $P(A \mid B)$ is the conditional probability of $A$ given $B$.

Counting and Enumerating Outcomes

Way of thinking. Divide and conquer.

Last week we saw that if $S$ is finite and all outcomes are equally likely, then

• Computing probabilities reduces to counting.

• The method is always the same: break the job into a sequence of simple tasks, count each task, and combine.

1. The fundamental theorem of counting

Example 1.2.12 (Lottery–I). In the New York state lottery, a player picks 6 numbers from $1, 2, \dots, 44$. To compute the probability of winning, we must first count how many different tickets are possible.

Theorem 1.2.14 (Fundamental Theorem of Counting). If a job consists of $k$ separate tasks, the $i$th of which can be done in $n_i$ ways, $i = 1, \dots, k$, then the entire job can be done in $n_1 \times n_2 \times \cdots \times n_k$ ways.

Proof for $k = 2$. The first task can be done in $n_1$ ways, and for each of these there are $n_2$ ways to do the second task. So the job can be done in

ways. The general case follows by induction on $k$ (Exercise 1.15). $\square$

Key requirement. The number of ways to do task $i$ must not depend on how the earlier tasks were done (even if which choices are available does).

Example 1.2.15 (Lottery–II). Choosing the first two lottery numbers: $44 \times 43 = 1{,}892$ ways if a number cannot be repeated, and $44 \times 44 = 1{,}936$ ways if it can.

2. The four counting rules

Every counting problem raises two questions:

1. With or without replacement? Can the same object be chosen more than once?
2. Ordered or unordered? Does the order in which objects are chosen matter? (Do the tickets $12, 37, 35, 9, 13, 22$ and $9, 12, 13, 22, 35, 37$ count as the same?)

Here is each case for choosing $r = 6$ numbers from $n = 44$.

Definition 1.2.16. For a positive integer $n$, $n!$ (read $n$ factorial) is the product of all of the positive integers less than or equal to $n$. That is,

Furthermore, we define $0! = 1$.

(1) Ordered, without replacement. By the fundamental theorem,

(2) Ordered, with replacement. Each of the 6 numbers can be chosen in 44 ways:

(3) Unordered, without replacement. Each unordered set of 6 numbers appears in $6!$ different orders in case (1). Divide out the redundant orderings:

Definition 1.2.17. For nonnegative integers $n$ and $r$, where $n \ge r$, we define the symbol $\binom{n}{r}$, read $n$ choose $r$, as

• In the lottery example, the number of possible tickets (unordered, without replacement) is $\binom{44}{6}$.
• In general, $\binom{n}{r}$ counts the ways to choose $r$ objects from $n$ when order does not matter.
• These numbers are also called binomial coefficients, for reasons that will become clear in Chapter 3.

(4) Unordered, with replacement (stars and bars). This is the hardest case.

  | M |   | M M | M |   | ... | M | M |   |   |
    1   2    3    4   5   ...  41  42  43  44

Table 1.2.1. Number of possible arrangements of size $r$ from $n$ objects:

Multinomial coefficients. The number of distinct orderings of $k$ objects, where there are $m$ distinct types repeated $k_1, \dots, k_m$ times ($k_1 + \cdots + k_m = k$), is

(Arrange all $k$ objects in $k!$ ways, then divide by the $k_j!$ rearrangements of identical objects of each type.) For example, the letters of MISSISSIPPI can be arranged in $\dfrac{11!}{1!\,4!\,4!\,2!} = 34{,}650$ ways. With $m = 2$ types this reduces to $\binom{k}{k_1}$.

Example (Is the drive to buy a lottery ticket riskier than the ticket?). A popular saying claims: “You’re more likely to die on your way to buy a lottery ticket than to win.”

Lottery odds come straight from the counting rules (unordered, without replacement). Powerball draws 5 of 69 white balls and 1 of 26 red balls; Canada’s 6/49 draws 6 of 49:

Driving risk. NHTSA reports 1.26 traffic deaths per 100 million vehicle miles traveled in 2023, so a trip of $d$ miles carries a risk of roughly $d \times 1.26 \times 10^{-8}$.

The two risks are equal at a round trip of only about $0.27$ miles for Powerball, but about $5.7$ miles for 6/49.

Caveat. The 1.26 rate averages over all drivers, roads, and times, including drunk and nighttime driving. The relevant quantity is the conditional probability of a crash given this particular short daytime trip, which is smaller.

3. Equally likely outcomes

If $S = \lbrace s_1, \dots, s_N \rbrace$ and each outcome has probability $1/N$, then by Axiom 3,

Example 1.2.18 (Poker). Deal 5 cards from a well-shuffled 52-card deck. Since no event below depends on the order of the cards, take $S$ = all unordered 5-card hands, so $N(S) = \binom{52}{5} = 2{,}598{,}960$, each equally likely.

• Four aces: What is $P(\text{four aces})$?

  Show solution

  If four of the cards are aces, the fifth card can be any of the other 48, so $P(\text{four aces}) = \dfrac{48}{2{,}598{,}960}$, less than 1 in 50,000.

• Four of a kind: What is $P(\text{four of a kind})$?

  Show solution

  Choose the denomination (13 ways), then the fifth card (48 ways): $P(\text{four of a kind}) = \dfrac{13 \times 48}{2{,}598{,}960} = \dfrac{624}{2{,}598{,}960}$.

• Exactly one pair: What is $P(\text{exactly one pair})$ (not two pairs, no three of a kind, etc.)?

  Show solution

  Build the hand task by task:

  \[\underbrace{13}_{\text{pair's denomination}} \times \underbrace{\binom{4}{2}}_{\text{pair's suits}} \times \underbrace{\binom{12}{3}}_{\text{other 3 denominations}} \times \underbrace{4^3}_{\text{their suits}} = 1{,}098{,}240,\]

  so $P(\text{exactly one pair}) = \dfrac{1{,}098{,}240}{2{,}598{,}960} \approx 0.42$.

• Follow-up: In the one-pair count, why $\binom{12}{3}$ and not $12 \times 11 \times 10$?

  Show answer

  The other three cards form an unordered set. Choosing “king, then 7, then 3” gives the same hand as “3, then king, then 7.” Counting them in order would count each hand $3! = 6$ times.

Example 1.2.19 (Sampling with replacement). Draw $r = 2$ items from $\lbrace 1, 2, 3 \rbrace$ with replacement.

• The 9 ordered outcomes are equally likely; the 6 unordered ones are not.
• Use the unordered formula to enumerate outcomes, but count ordered outcomes to compute probabilities.
• As C&B put it, probabilities should be determined by the sampling mechanism, not by whether the objects happen to be distinguishable.

Example 1.2.20 (Calculating an average). Draw 4 numbers with replacement from $\lbrace 2, 4, 9, 12 \rbrace$. There are $4^4 = 256$ equally likely ordered samples. The unordered sample $\lbrace 2, 4, 4, 9 \rbrace$ arises from $\dfrac{4!}{1!\,2!\,1!} = 12$ of them, so it has probability $12/256$, not $1/\binom{7}{4} = 1/35$. This calculation is an elementary version of the bootstrap, which we will meet in later courses.

Example (birthday problem). In a room of $n$ people with birthdays independent and uniform over 365 days (ignore leap years), what is the probability that at least two share a birthday? Ordered samples with replacement give $N(S) = 365^n$. It is easier to count the complement, all birthdays different (ordered, without replacement):

For $n = 23$ this is about $0.507$; for $n = 50$ it is about $0.970$. When “at least one” is hard to count, count the complement.

Check your understanding.

1. How many 5-card hands are a full house (three of one denomination and two of another)? (Answer: $13 \binom{4}{3} \cdot 12 \binom{4}{2} = 3{,}744$.)
2. Explain why $\binom{n}{r} = \binom{n}{n-r}$ without using the formula.
3. Prove Pascal’s rule $\binom{n}{r} = \binom{n-1}{r-1} + \binom{n-1}{r}$ by a counting argument. (Fix one object: is it chosen or not?)

Conditional Probability and Independence

Way of thinking. Conditioning on $B$ means shrinking the sample space to $B$.

1. Conditional probability

Example 1.3.1 (Four aces). Deal 4 cards from a well-shuffled deck. The probability that they are the four aces is $1/\binom{52}{4} = 1/270{,}725$. We can also compute it by updating after each card:

The factor $3/51$ is a conditional probability: the chance the second card is an ace given that the first one was.

Definition 1.3.2. If $A$ and $B$ are events in $S$, and $P(B) > 0$, then the conditional probability of $A$ given $B$, written $P(A \mid B)$, is

Interpretation. $B$ becomes the new sample space: $P(B \mid B) = 1$, and each event is “rescaled” by how much of it lies in $B$. In particular, if $A$ and $B$ are disjoint, then $P(A \mid B) = P(B \mid A) = 0$.

Fact (Exercise 1.35; not a numbered theorem in C&B). If $P$ is a probability function and $P(B) > 0$, then $P(\,\cdot \mid B)$ satisfies the Kolmogorov axioms.

Proof sketch. $P(A \mid B) \ge 0$ since it is a ratio of nonnegative numbers. $P(S \mid B) = P(B)/P(B) = 1$. If $A_1, A_2, \dots$ are pairwise disjoint, so are $A_1 \cap B, A_2 \cap B, \dots$, and $\left( \bigcup_i A_i \right) \cap B = \bigcup_i (A_i \cap B)$ by the distributive law. Countable additivity of $P$ then gives $P\left( \bigcup_i A_i \mid B \right) = \sum_i P(A_i \mid B)$. $\square$

So every result from Week 1 holds for conditional probabilities, for example $P(A^c \mid B) = 1 - P(A \mid B)$.

Example 1.3.3 (Continuation of Example 1.3.1). Since $\lbrace 4 \text{ aces in 4 cards} \rbrace \subset \lbrace i \text{ aces in first } i \text{ cards} \rbrace$,

For $i = 1, 2, 3$ this is $0.00005$, $0.00082$, and $0.02041$.

2. The multiplication rule

Rearranging (1.3.1):

and, by symmetry,

Applying this repeatedly gives the chain rule:

provided the conditioning events have positive probability. Example 1.3.1 is exactly this, with $A_i$ = “card $i$ is an ace.”

3. A cautionary tale: the three prisoners

Example 1.3.4 (Three prisoners). Prisoners A, B, and C are on death row. The governor picks one at random to pardon and tells the warden, who must keep it secret. A asks the warden to name one of B or C who will be executed. The warden says “B.”

• A’s reasoning: “Now either A or C is pardoned. My chance has risen from $1/3$ to $1/2$.”
• Warden’s reasoning: “At least one of B and C will be executed anyway, so I gave A no information.”

Let $A, B, C$ be the events that each prisoner is pardoned, each with probability $1/3$, and let $W$ = “the warden says B will die.” If A is pardoned, assume the warden names B or C with equal probability. Then

so $P(W) = \frac{1}{6} + \frac{1}{3} = \frac{1}{2}$ and

The warden is right. A’s mistake is conditioning on the wrong event: A computes $P(A \mid B^c) = \frac{1/3}{2/3} = \frac{1}{2}$, but the information received is $W$, which is a subset of $B^c$, not $B^c$ itself.

Lesson: condition on exactly what you observed, including how it was observed. (Exercise 1.37 explores variations, and the Monty Hall problem is a close relative.)

Example (Monty Hall problem). On the game show Let’s Make a Deal, hosted by Monty Hall, a car is behind one of three doors and a goat is behind each of the other two. You pick Door 1. The host, who knows where the car is, opens one of the other doors, say Door 3, and shows a goat. He then offers to let you switch to Door 2. Should you switch?

The host follows these rules: he never opens your door, he always shows a goat, and when both other doors hide goats he picks one of them at random. (Steve Selvin posed the problem in The American Statistician in 1975. When Marilyn vos Savant answered “switch” in Parade magazine in 1990, thousands of readers, many of them PhDs, wrote in to say she was wrong.)

• Question 1: Let $C_i$ = “the car is behind door $i$,” with $P(C_i) = 1/3$, and let $H$ = “the host opens Door 3.” Find $P(C_1 \mid H)$ and $P(C_2 \mid H)$. Should you switch?

  Show solution

  List the possibilities, as in the three prisoners table:

  Car behind	Host opens	Probability
  Door 1	Door 2	$1/6$
  Door 1	Door 3	$1/6$
  Door 2	Door 3	$1/3$
  Door 3	Door 2	$1/3$

  So $P(H) = \frac{1}{6} + \frac{1}{3} = \frac{1}{2}$, and

  \[P(C_1 \mid H) = \frac{P(C_1 \cap H)}{P(H)} = \frac{1/6}{1/2} = \frac{1}{3}, \qquad P(C_2 \mid H) = \frac{P(C_2 \cap H)}{P(H)} = \frac{1/3}{1/2} = \frac{2}{3}.\]

  Switch: it doubles your chance of winning the car. Your own door’s probability does not change. The probability $1/3$ that was on Door 3 moves to Door 2.

• Question 2: How does this problem match Example 1.3.4? Which prisoner plays the role of your door, and which plays the role of Door 2?

  Show answer

  Three prisoners	Monty Hall
  Prisoner A asks the warden	You pick Door 1
  The warden names B as one to be executed	The host opens Door 3 and shows a goat
  If A is pardoned, the warden names B or C at random	If the car is behind Door 1, the host opens Door 2 or 3 at random
  $P(A \mid W) = 1/3$, unchanged	$P(C_1 \mid H) = 1/3$, unchanged
  $P(C \mid W) = 2/3$	$P(C_2 \mid H) = 2/3$

  The two problems have the same probability model. The difference is that prisoner A cannot trade places with C, but you can switch doors, so the calculation becomes a decision.

• Question 3: Suppose instead the host does not know where the car is. He opens Door 2 or Door 3 at random, and it happens to show a goat. Now what are $P(C_1 \mid G)$ and $P(C_2 \mid G)$, where $G$ = “the host opens Door 3 and it shows a goat”?

  Show solution

  Now the host opens Door 3 with probability $1/2$ no matter where the car is, and $G$ fails if the car is behind Door 3. So

  \[P(C_1 \cap G) = \tfrac{1}{3} \cdot \tfrac{1}{2} = \tfrac{1}{6}, \qquad P(C_2 \cap G) = \tfrac{1}{3} \cdot \tfrac{1}{2} = \tfrac{1}{6}, \qquad P(C_3 \cap G) = 0,\]

  so $P(G) = \frac{1}{3}$ and $P(C_1 \mid G) = P(C_2 \mid G) = \frac{1}{2}$. Switching no longer helps.

  You see the same thing as before, a goat behind Door 3, but the answer changes, because the way the information was produced has changed. This is the lesson of the three prisoners again.

• Question 4: Give an intuitive argument for switching in the original game.

  Show answer

  • Switching flips the outcome. If you always switch, you win exactly when your first pick was a goat, which happens with probability $2/3$.
  • 100 doors. Suppose there are 100 doors, you pick one, and the host knowingly opens 98 goat doors, leaving one other door closed. Your door still has probability $1/100$. The one door he carefully avoided opening has the other $99/100$.

4. The law of total probability and Bayes’ rule

Law of total probability If $A_1, A_2, \dots$ is a partition of $S$ with each $P(A_i) > 0$, then for any event $B$,

Proof. By Theorem 1.2.11(a), $P(B) = \sum_i P(B \cap A_i)$, and each term equals $P(B \mid A_i) P(A_i)$ by the multiplication rule. $\square$

This is the partition idea from Week 1, put to work: break $B$ into pieces according to which $A_i$ occurred.

Bayes’ rule, simple form. Equating the two expressions for $P(A \cap B)$:

This “turns around” a conditional probability.

Theorem 1.3.5 (Bayes’ Rule). Let $A_1, A_2, \dots$ be a partition of the sample space, and let $B$ be any set. Then, for each $i = 1, 2, \dots$,

(C&B say “any set”; implicitly $P(B) > 0$, so that $P(A_i \mid B)$ is defined.)

Proof. Apply (1.3.5) with $A = A_i$, and expand the denominator $P(B)$ by the law of total probability. $\square$

Vocabulary. $P(A_i)$ is the prior probability, $P(B \mid A_i)$ is the likelihood of the observation $B$ under $A_i$, and $P(A_i \mid B)$ is the posterior probability.

Example 1.3.6 (Coding). In Morse code, dots and dashes are sent in proportion $3 : 4$, so $P(\text{dot sent}) = 3/7$. Each symbol is flipped in transmission with probability $1/8$. If a dot is received, how sure can we be that a dot was sent?

Example (screening test). A disease has prevalence 1%. A test has sensitivity $P(+ \mid D) = 0.95$ and specificity $P(- \mid D^c) = 0.95$. What is the probability that a person who tests positive has the disease?

Even with an accurate test, most positives are false positives, because the disease is rare. Confusing $P(+ \mid D) = 0.95$ with $P(D \mid +) \approx 0.16$ is the base-rate fallacy (recall the “Always verify” list in the Week 0 notes).

5. Independence

Sometimes learning $B$ tells us nothing about $A$: $P(A \mid B) = P(A)$. By (1.3.5) this implies $P(B \mid A) = P(B)$, and by the multiplication rule $P(A \cap B) = P(A) P(B)$. We take the symmetric version as the definition.

Definition 1.3.7. Two events, $A$ and $B$, are statistically independent if

This definition is symmetric in $A$ and $B$, does not require $P(B) > 0$, and extends to more than two events.

Example 1.3.8 (Chevalier de Méré). Is it a good bet that at least one six appears in 4 rolls of a die? By independence of the rolls,

De Méré also bet on at least one double six in 24 rolls of two dice, reasoning that it should be equally likely. In fact $1 - (35/36)^{24} \approx 0.491$, a losing bet. His losses prompted the Pascal–Fermat correspondence of 1654, often taken as the birth of probability theory.

Theorem 1.3.9. If $A$ and $B$ are independent events, then the following pairs are also independent:

• (a) $A$ and $B^c$,
• (b) $A^c$ and $B$,
• (c) $A^c$ and $B^c$.

Proof of (a). By Theorem 1.2.9(a) and independence,

Parts (b) and (c) are Exercise 1.40.

Independent vs. disjoint. These are very different. If $P(A) > 0$ and $P(B) > 0$ and $A, B$ are disjoint, then $P(A \cap B) = 0 \ne P(A) P(B)$, so they are dependent: learning that $A$ occurred tells you $B$ did not (Exercise 1.39).

6. Independence of several events

What should it mean for $A$, $B$, and $C$ to be independent? Two natural guesses both fail.

Guess 1: $P(A \cap B \cap C) = P(A) P(B) P(C)$ is enough. False.

Example 1.3.10 (Tossing two dice). Roll two dice, with $S$ the 36 equally likely ordered pairs. Let $A$ = “doubles,” $B$ = “the sum is between 7 and 10,” and $C$ = “the sum is 2, 7, or 8.” Then $P(A) = 1/6$, $P(B) = 1/2$, $P(C) = 1/3$, and

But $P(B \cap C) = P(\text{sum is 7 or 8}) = 11/36 \ne P(B) P(C) = 1/6$.

Guess 2: pairwise independence is enough. False.

Example 1.3.11 (Letters). Let $S$ consist of the 9 equally likely strings

and let $A_i$ = “position $i$ is occupied by $a$.” Then $P(A_i) = 1/3$ and $P(A_i \cap A_j) = 1/9$ for all $i \ne j$, so the $A_i$ are pairwise independent. But $P(A_1 \cap A_2 \cap A_3) = P(\lbrace aaa \rbrace) = 1/9 \ne 1/27$.

Definition 1.3.12. A collection of events $A_1, \dots, A_n$ are mutually independent if for any subcollection $A_{i_1}, \dots, A_{i_k}$, we have

For three events that is four equations: three pairwise conditions plus the triple one. For $n$ events it is $2^n - n - 1$ equations.

Example 1.3.13 (Three coin tosses–I). Toss a fair coin three times, with all 8 outcomes equally likely, and let $H_i$ = “toss $i$ is a head.” Then $P(H_i) = 1/2$,

and similarly for the other pairs. So $H_1, H_2, H_3$ are mutually independent, which is what “independent tosses” means.

Check your understanding.

1. If $P(A) = 0.4$, $P(B) = 0.5$, and $A$, $B$ are independent, find $P(A \cup B)$. (Answer: $0.7$.)
2. Show that if $P(B) = 1$, then $B$ is independent of every event $A$.
3. In the screening example, what is $P(D \mid +)$ if the prevalence is 10% instead of 1%? What does this say about screening in low-risk populations?

Summary of Week 2

• Counting: the fundamental theorem; the four rules in Table 1.2.1; binomial and multinomial coefficients. With replacement, unordered outcomes are not equally likely.
• Equally likely outcomes: $P(A) = N(A)/N(S)$; when “at least one” is hard to count, count the complement.
• Conditional probability: $P(A \mid B) = P(A \cap B)/P(B)$ is itself a probability function; the chain rule; the law of total probability.
• Bayes’ rule: posterior $\propto$ likelihood $\times$ prior; never confuse $P(A \mid B)$ with $P(B \mid A)$.
• Independence: $P(A \cap B) = P(A) P(B)$; preserved under complements; disjoint is not independent; mutual independence requires the product rule for every subcollection.

Practice Problems

From C&B §1.7:

• Counting: 1.15, 1.16, 1.17, 1.18, 1.20, 1.21.
• Conditional probability and Bayes’ rule: 1.33, 1.34, 1.35, 1.36, 1.37, 1.38.
• Independence: 1.39, 1.40.

Next week: random variables, cumulative distribution functions, and probability mass and density functions (§§1.4–1.6).