Combinatorics • Topic 19

Basic Probability

For finite sample spaces where all outcomes are equally likely, probability is a simple ratio of counting.

Definition

Theorem (Naive Definition of Probability)

If a random experiment has a finite sample space

S

where every outcome is equally likely, then the probability of an event

E

is:

P (E) = \frac{Number of outcomes in E}{Total outcomes in S} = \frac{∣ E ∣}{∣ S ∣}

Axioms of Probability

For more general spaces, probability

P

is a function satisfying:

$0 \leq P (E) \leq 1$ .
$P (S) = 1$ .
Additivity: If $A$ and $B$ are disjoint ( $A \cap B = \emptyset$ ), then $P (A \cup B) = P (A) + P (B)$ .

Applications with Combinatorics

Most Olympiad probability problems are just two counting problems in disguise: count the good cases, count the total cases, and divide.

Example (Poker Hand)

What is the probability of being dealt a "Four of a Kind" in a 5-card poker hand?

Proof. Total outcomes ( $∣ S ∣$ ): $(5 52) = 2, 598, 960$ . Outcomes in $E$ :

Choose the rank for the quad: $(1 13)$ .
Choose the 4 cards of that rank: $(4 4) = 1$ .
Choose the 5th "kicker" card from remaining 48: $(1 48)$ .

∣ E ∣ = 13 \times 1 \times 48 = 624

P (E) = \frac{624}{2 , 598 , 960} \approx 0.00024

∎

Practice Problems

Exercise (Problem 1)

If 3 distinct integers are chosen from

{1, \dots, 100}

, what is the probability that their sum is even?

Exercise (Problem 2)

Two friends agree to meet between 2 PM and 3 PM. Each waits 15 minutes for the other before leaving. What is the probability they meet? (Geometric Probability).

Exercise (Problem 3)

Find the probability that a random arrangement of the letters in "GOOGLE" has the two O's together.