Discrete Math › Section D · Counting › Topic D.7

Counting and probability

When every outcome is equally likely, a probability is just one count divided by another. Everything this section has built, from the product principle to inclusion-exclusion, becomes a tool for measuring chance.

Probability as a ratio of counts

An experiment is any process with an uncertain result, such as dealing a hand of cards or generating a random bit string. Its sample space \(S\) is the set of all possible outcomes, and an event \(E\) is a subset of \(S\). If every outcome is equally likely, the probability of \(E\) is

P(E) = \frac{|E|}{|S|}

Every probability, equally likely or not, obeys three axioms: \(P(E) \ge 0\), \(P(S) = 1\), and \(P(A \cup B) = P(A) + P(B)\) for disjoint events. A loaded die simply gives its faces unequal probabilities. The statistics course builds the same ideas in "Probability terminology". Here \(|E|\) and \(|S|\) are usually far too large to list, so this section's counting principles do the work.

Equally likely is an assumption

The formula needs a sample space whose outcomes really are equally likely, and choosing it is the first and most important step. With two fair dice, the 36 ordered pairs such as (2, 5) and (5, 2) are equally likely, but the 11 possible sums are not. Recall from "Counting multisets (stars and bars)" that three identical dice show 56 different multisets, yet \(\{1, 1, 1\}\) arises from one of the 216 ordered rolls and \(\{1, 2, 3\}\) from six. The safe habit is to imagine the objects as distinguishable, even when they look identical, and count ordered outcomes or labelled sets. Probabilities do not depend on whether you can tell the dice apart.

Worked example: a full house

Five cards are dealt from a well-shuffled 52-card deck. What is the probability of a full house, three cards of one rank and two of another? 1. Sample space: all hands, \(|S| = \binom{52}{5} = 2{,}598{,}960\), equally likely. 2. Build a full house in stages: the rank of the three, 13 ways; which three of its 4 suits, \(\binom{4}{3} = 4\); the rank of the pair, 12 ways (any other rank); which two suits, \(\binom{4}{2} = 6\). 3. By the product principle, \(|E| = 13 \cdot 4 \cdot 12 \cdot 6 = 3744\). 4. \(P = \frac{3744}{2{,}598{,}960} \approx 0.00144\), about 1 hand in 694. The order of ranks matters here: three kings and two fives is a different hand from three fives and two kings.

The complement and union rules

Counting rules turn directly into probability rules by dividing by \(|S|\). The complement \(\overline{E}\), written \(E'\) in the statistics course, gives \(P(\overline{E}) = 1 - P(E)\). It is the quick route to "at least" questions. Flip a fair coin 8 times: the 256 sequences are equally likely, and "fewer than two heads" means 0 heads (1 sequence) or 1 head (8 sequences). So the probability of at least two heads is \(1 - \frac{9}{256} = \frac{247}{256}\). Inclusion-exclusion becomes

P(A \cup B) = P(A) + P(B) - P(A \cap B)

A number chosen at random from 1 to 300 is a multiple of 3, 5 or 7 with probability \(\frac{162}{300} = 0.54\), using the count from "Overlaps and inclusion-exclusion".

Worked example: a random committee

Four people are chosen at random from 6 women and 5 men. What is the probability that exactly two are women? 1. Sample space: all 4-person committees, \(\binom{11}{4} = 330\), each equally likely. 2. Favourable committees: choose 2 of the 6 women, \(\binom{6}{2} = 15\), and 2 of the 5 men, \(\binom{5}{2} = 10\), so 150. 3. \(P = \frac{150}{330} = \frac{5}{11} \approx 0.455\). 4. Sense check: the expected share of women is \(\frac{6}{11}\) of 4, about 2.2, so two women should be the most common result, and indeed the other counts, 5, 60, 100 and 15 committees with 0, 1, 3 and 4 women, are all smaller.

Conditional probability

Sometimes partial information arrives first. The probability of \(A\) given \(B\) is

P(A \mid B) = \frac{P(A \cap B)}{P(B)}

defined when \(P(B) > 0\). With equally likely outcomes, this is \(\frac{|A \cap B|}{|B|}\): the new sample space is \(B\). For example, a 5-bit string is chosen at random, and you learn that its weight is 2. The 10 strings of weight 2 are equally likely, and 4 of them start with 1 (place the other 1 in any of the remaining 4 positions). So the probability of starting with 1, given weight 2, is \(\frac{4}{10} = 0.4\), lower than the unconditional \(\frac{1}{2}\). Bayes' theorem reverses a condition:

P(A \mid B) = \frac{P(B \mid A)\,P(A)}{P(B)}

The statistics topic "Bayes' theorem as learning from evidence" develops it.

Independent events

Events \(A\) and \(B\) are independent when \(P(A \cap B) = P(A) \cdot P(B)\). When \(P(B) > 0\), that is the same as \(P(A \mid B) = P(A)\): learning \(B\) does not change the chance of \(A\). Independence must be checked, not assumed, and it can be surprising. Pick a random 4-bit string, and let \(A\) be "first bit is 1" and \(B\) be "weight is even". Then \(|A| = 8\) and \(|B| = 8\) of the 16 strings, and \(|A \cap B| = 4\), since the last three bits must then have odd weight. So \(P(A \cap B) = \frac{4}{16} = \frac{1}{4} = \frac{1}{2} \cdot \frac{1}{2}\): independent, although both events involve the first bit.

Worked example: the Monty Hall problem

A prize is behind one of three doors. You pick door 1. The host, who knows where the prize is, always opens a different door with no prize behind it and offers you a switch. Should you switch? 1. Your first pick is right with probability \(\frac{1}{3}\); then switching loses. 2. With probability \(\frac{2}{3}\) your pick is wrong. The host must then open the only other empty door, and switching lands on the prize. 3. So switching wins with probability \(\frac{2}{3}\), and staying wins with \(\frac{1}{3}\). 4. A computer simulation of 100,000 games gives a switching win rate close to 0.667. The common answer of one half wrongly treats the two closed doors as equally likely.

Common mistakes to avoid

First, dividing counts from a sample space whose outcomes are not equally likely, such as dice sums or multisets of identical dice. Second, counting the event and the sample space in different ways, for example ordered hands in one and unordered hands in the other; both must use the same kind of outcome. Third, adding probabilities of overlapping events without subtracting \(P(A \cap B)\). Fourth, confusing \(P(A \mid B)\) with \(P(B \mid A)\). Fifth, assuming independence, or assuming that events sharing some feature cannot be independent: check the product rule with actual counts.

Key takeaways

With equally likely outcomes, \(P(E) = \frac{|E|}{|S|}\), so probability problems become two counting problems that must use the same kind of outcome. Treat identical-looking objects as distinguishable to keep outcomes equally likely. The complement rule \(P(\overline{E}) = 1 - P(E)\) handles "at least" questions, and inclusion-exclusion handles unions. Conditional probability \(P(A \mid B) = \frac{|A \cap B|}{|B|}\) shrinks the sample space to \(B\). Independence means \(P(A \cap B) = P(A)P(B)\), and it must be verified.

Flashcards

Flashcard

Sample space S

The set of all possible outcomes of an experiment

An event is a subset of S.

Test your understanding

Question 1 of 5

A 3-person committee is chosen at random from 5 women and 4 men. What is the probability that all three are women?

Question 2 of 5

A fair coin is flipped 6 times. What is the probability of at least one tail?

Question 3 of 5

Two fair dice are rolled and the sum is 8. Given this, what is the probability that both dice are even?

Question 4 of 5

A fair die is rolled. A is "even" and B is "at most 4". What is P(A ∩ B), and are A and B independent?

Question 5 of 5

In the Monty Hall problem, the host knowingly opens an empty door you did not pick. What is your chance of winning if you switch?

← Previous topicNext topic →