Skills101

AdvancedDiscrete Mathematics · Lesson 13 of 14 · Updated ·

Discrete Probability — Sample Spaces, Conditional Probability, Independence, Bayes' Theorem and Expected Value

Probability in a discrete maths course is counting with a fraction at the end. You already know how to count from the counting lesson. Here we turn counts into probabilities, learn how new information changes a probability (conditional probability and Bayes' theorem), and find the average outcome of a random process (expected value). These ideas are used in algorithm analysis (average-case running time, hashing, randomised quicksort) and in machine learning (naive Bayes).

We use Python's Fraction so every answer is exact, like a hand calculation, instead of a rounded decimal.

1. Sample spaces and events

  • An experiment is something with an uncertain result: rolling two dice.
  • The sample space S is the set of all possible outcomes: the 36 pairs (first die, second die).
  • An event E is a subset of S: "the sum is 7".

When every outcome is equally likely:

P(E) = |E| / |S|

Three rules follow directly:

RuleFormula
Range0 ≤ P(E) ≤ 1, P(S) = 1
ComplementP(not E) = 1 − P(E)
UnionP(E ∪ F) = P(E) + P(F) − P(E ∩ F)

The complement rule is the most useful trick: "at least one six" is hard to count directly, but "no six" is just 5 × 5 = 25 outcomes, so P(at least one 6) = 1 − 25/36 = 11/36.

A 6 by 6 grid of two-dice sums: the six cells with sum 7 lie on a diagonal and are orange, and the eleven cells containing at least one 6 are in the last row and last column

2. Conditional probability and independence

Conditional probability answers: "given that F happened, how likely is E?" We throw away every outcome outside F and count again:

P(E | F) = P(E ∩ F) / P(F) (when P(F) > 0)

Example: given that the first die is even, what is the chance the sum is 8? The first die is even in 18 outcomes; of these, (2,6), (4,4), (6,2) have sum 8. So P = 3/18 = 1/6.

Two events are independent when knowing one does not change the other:

E and F are independent ⇔ P(E ∩ F) = P(E) × P(F)

from fractions import Fraction
from itertools import product

S = list(product(range(1, 7), repeat=2))          # sample space: 36 equally likely outcomes

def P(event, given=lambda o: True):
    space = [o for o in S if given(o)]
    return Fraction(sum(1 for o in space if event(o)), len(space))

print("|S| =", len(S))
print("P(sum = 7)            =", P(lambda o: sum(o) == 7))
print("P(at least one 6)     =", P(lambda o: 6 in o))
print("P(no 6), via 1 - P    =", 1 - P(lambda o: 6 in o))
print("P(sum = 8 | first even) =", P(lambda o: sum(o) == 8, given=lambda o: o[0] % 2 == 0))

A = lambda o: o[0] % 2 == 0          # first die even
B = lambda o: sum(o) == 7            # sum is 7
C = lambda o: sum(o) == 8            # sum is 8
both = lambda e, f: (lambda o: e(o) and f(o))
print("A, B independent?", P(both(A, B)) == P(A) * P(B))
print("A, C independent?", P(both(A, C)) == P(A) * P(C), "-", P(both(A, C)), "vs", P(A) * P(C))
|S| = 36
P(sum = 7)            = 1/6
P(at least one 6)     = 11/36
P(no 6), via 1 - P    = 25/36
P(sum = 8 | first even) = 1/6
A, B independent? True
A, C independent? False - 1/12 vs 5/72

The result surprises many students. "Sum is 7" is independent of "first die is even": whatever the first die shows, exactly one value of the second die makes 7. "Sum is 8" is not independent of it: if the first die is 1, a sum of 8 is impossible. Never guess independence; check the formula.

Do not confuse independent with mutually exclusive (P(E ∩ F) = 0). Two mutually exclusive events with non-zero probabilities are never independent: if one happens, the other certainly did not.

3. Total probability and Bayes' theorem

A factory has two machines. In this example, M1 makes 60% of the bolts and 2% of its bolts are defective; M2 makes 40% and 5% of its bolts are defective. (These numbers are chosen for the example.)

Law of total probability. Split by which machine made the bolt:

P(D) = P(M1)·P(D | M1) + P(M2)·P(D | M2) = 0.6 × 0.02 + 0.4 × 0.05 = 0.012 + 0.020 = 0.032

Bayes' theorem turns the condition around. We picked a defective bolt. Which machine probably made it?

P(M2 | D) = P(M2)·P(D | M2) / P(D) = 0.020 / 0.032 = 5/8

Tree diagram: the bolt comes from M1 with probability 0.6 or M2 with probability 0.4; M1's bolts are defective with probability 0.02 giving 0.012, M2's with 0.05 giving 0.020; so P(M2 given defective) = 0.020 / 0.032 = 5/8

from fractions import Fraction as F

# a factory: machine M1 makes 60% of the bolts, M2 makes 40%
prior = {"M1": F(60, 100), "M2": F(40, 100)}
defect_rate = {"M1": F(2, 100), "M2": F(5, 100)}

# total probability: P(D) = sum over machines of P(M) * P(D | M)
p_d = sum(prior[m] * defect_rate[m] for m in prior)
print("P(defective) =", p_d, "=", float(p_d))

# Bayes: P(M | D) = P(M) * P(D | M) / P(D)
for m in prior:
    post = prior[m] * defect_rate[m] / p_d
    print(f"P({m} | defective) = {post} = {float(post):.4f}")
P(defective) = 4/125 = 0.032
P(M1 | defective) = 3/8 = 0.3750
P(M2 | defective) = 5/8 = 0.6250

M2 makes fewer bolts, but because its defect rate is higher it is responsible for most defective ones. The two posterior probabilities add up to 1, which is a quick check on your arithmetic.

4. Random variables and expected value

A random variable X gives a number to each outcome, like "the sum of the two dice". Its expected value is the probability-weighted average:

E[X] = Σ x · P(X = x)

The most useful fact is linearity of expectation: E[X + Y] = E[X] + E[Y], always, even when X and Y are not independent. That lets you split a hard average into easy pieces.

The binomial formula counts successes in n independent trials, each with success probability p:

P(exactly k successes) = C(n, k) · pᵏ · (1 − p)ⁿ⁻ᵏ

from fractions import Fraction as F
from itertools import permutations, product
from math import comb

die = range(1, 7)
E_die = sum(F(x, 6) for x in die)
E_two = sum(F(a + b, 36) for a, b in product(die, repeat=2))
print("E[one die] =", E_die, "  E[sum of two dice] =", E_two, "= 2 * E[one die]?", E_two == 2 * E_die)

# binomial: exactly k heads in n fair coin tosses
n = 5
for k in range(n + 1):
    print(f"P({k} heads in {n}) = {comb(n, k)}/{2 ** n}")

# expected number of people who get their own hat back (fixed points of a random permutation)
for n in [3, 4, 5]:
    perms = list(permutations(range(n)))
    fixed = sum(sum(p[i] == i for i in range(n)) for p in perms)
    print(f"n = {n}: average fixed points = {F(fixed, len(perms))}")
E[one die] = 7/2   E[sum of two dice] = 7 = 2 * E[one die]? True
P(0 heads in 5) = 1/32
P(1 heads in 5) = 5/32
P(2 heads in 5) = 10/32
P(3 heads in 5) = 10/32
P(4 heads in 5) = 5/32
P(5 heads in 5) = 1/32
n = 3: average fixed points = 1
n = 4: average fixed points = 1
n = 5: average fixed points = 1

The last result is a classic. n people throw their hats in a pile and each picks one at random. How many, on average, get their own hat back? Let Xᵢ = 1 if person i gets their own hat. Each person does so with probability 1/n, so E[Xᵢ] = 1/n. By linearity, the expected total is n × 1/n = 1, for every n. The Xᵢ are not independent, but linearity does not care. (The derangements count the opposite case: nobody gets their own hat.)

Common mistakes

  • Using |E| / |S| when outcomes are not equally likely. For the sum of two dice, the 11 possible sums (2 to 12) are not equally likely; count the 36 pairs instead.
  • Adding probabilities of overlapping events without subtracting P(E ∩ F).
  • Mixing up P(E | F) and P(F | E). P(defective | M2) = 0.05, but P(M2 | defective) = 5/8. Bayes' theorem converts one into the other.
  • Treating "mutually exclusive" as "independent". They are almost opposites.
  • Believing linearity of expectation needs independence. It does not; only E[XY] = E[X]E[Y] needs independence.

Quick recap

  • Equally likely outcomes: P(E) = |E| / |S|. Complement: 1 − P(E).
  • P(E | F) = P(E ∩ F) / P(F). Independent ⇔ P(E ∩ F) = P(E)P(F).
  • Total probability: P(D) = Σ P(Mᵢ) P(D | Mᵢ). Bayes: P(Mᵢ | D) = P(Mᵢ) P(D | Mᵢ) / P(D).
  • E[X] = Σ x P(X = x); E[X + Y] = E[X] + E[Y] always.
  • Binomial: C(n, k) pᵏ (1 − p)ⁿ⁻ᵏ.

Practice what you learned

📝 Quiz: Discrete Probability5 questions · instant answers & explanations · +10 XP · counts towards your free certificateTake the quiz →