Skip to content
Tutorials Center
My learning

Topics

Lesson 37 of 68 ยท Counting

Discrete Probability

Learn sample spaces, events, conditional probability, independence, Bayes' theorem and expected value, with exact fractions and seeded Monte Carlo in Python.

Probability is counting with a denominator. If every outcome of an experiment is equally likely, the chance of an event is the number of outcomes that make it happen divided by the total number of outcomes. So everything you learned about counting principles, permutations and combinations and binomial coefficients now turns into chances: how likely is a flush, a shared birthday, a false alarm?

Discrete probability deals with experiments that have a finite or countable list of outcomes: dice, cards, coin flips, test results. In this lesson you will define sample spaces and events, compute conditional probabilities, use independence and Bayes' theorem, and find expected values. We use Python's fractions.Fraction so that answers are exact rather than rounded, and finish with a seeded Monte Carlo simulation that estimates probabilities by sampling.

The vocabulary

Sample space Every possible outcome.
Event A subset of outcomes we care about.
Probability Favorable outcomes over all outcomes.

This formula needs equally likely outcomes.

1 / 2

Sample spaces and events

The sample space S is the set of all possible outcomes of an experiment. Rolling two dice gives 36 outcomes, the Cartesian product {1,...,6} ร— {1,...,6}. An event is any subset of the sample space, such as "the sum is 7". If all outcomes are equally likely:

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

Three basic rules follow from counting. Probabilities lie between 0 and 1. P(S) = 1. And for any events A and B, P(A โˆช B) = P(A) + P(B) - P(A โˆฉ B), which is inclusion-exclusion divided by |S|. The complement rule is P(not E) = 1 - P(E), handy for "at least one" questions.

Python Events on two dice, with exact fractions

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Conditional probability

Sometimes you learn something about the outcome before asking the question. The conditional probability of A given B restricts the sample space to the outcomes where B holds:

P(A | B) = P(A โˆฉ B) / P(B), provided P(B) > 0.

Example: two children, each equally likely to be a boy or a girl. Given that at least one is a boy, what is the probability that both are boys? The four equally likely families are BB, BG, GB and GG. Only the first three have a boy, so the sample space shrinks to three outcomes and the answer is 1/3, not the 1/2 many people expect. A short enumeration settles such debates.

Independence

Events A and B are independent when learning that one occurred does not change the probability of the other: P(A โˆฉ B) = P(A) ยท P(B), equivalently P(A | B) = P(A). Two coin flips are independent. Be careful: "disjoint" and "independent" are different ideas. Disjoint events with positive probabilities are never independent, because if one happens, the other is impossible.

Python Conditional probability and independence by enumeration

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The sum 7 is independent of the first die's parity: whatever the first die shows, exactly one value of the second die makes the sum 7. The sum 8 is not independent, since a first die of 1 makes it impossible.

Bayes' theorem

Conditional probability works in both directions: P(A โˆฉ B) = P(A | B) ยท P(B) = P(B | A) ยท P(A). Equating them gives Bayes' theorem:

P(A | B) = P(B | A) ยท P(A) / P(B)

and the denominator is often expanded with the law of total probability: P(B) = P(B | A) ยท P(A) + P(B | not A) ยท P(not A).

Bayes' theorem lets you reverse the direction of a conditional. Medical tests are the classic case. Suppose 1 in 100 people has a condition, the test is positive for 99% of people who have it (sensitivity), and also positive for 5% of people who do not (false-positive rate). If your test is positive, what is the chance you have the condition?

Most people guess about 95%, but the real answer is far lower. Out of 10,000 people, 100 have the condition and 99 of them test positive; of the 9,900 healthy people, 495 also test positive. Among the 594 positive results, only 99 are real, so the probability is 99/594 = 1/6. The rarity of the condition outweighs the accuracy of the test.

Python Bayes' theorem: the medical test

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Expected value

The expected value (or mean) of a numerical outcome X is the probability-weighted average:

E[X] = ฮฃ x ยท P(X = x)

A fair die has E = (1 + 2 + ... + 6)/6 = 7/2. Expected value does not need to be a possible outcome. The most useful fact is linearity of expectation: E[X + Y] = E[X] + E[Y], even when X and Y are dependent. The expected sum of two dice is therefore 7/2 + 7/2 = 7 with no need to enumerate 36 cases.

A surprising use ties back to derangements: in a random permutation of n items, each position is a fixed point with probability 1/n, so the expected number of fixed points is n ยท (1/n) = 1, for every n. Averaging over all permutations confirms it.

Python Expected values, exactly

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Random variables, variance, total probability and covariance

A random variable X is a function from outcomes to numbers: "the sum of two dice" assigns 7 to the outcomes (1,6), (2,5), and so on. Its distribution lists P(X = k). The expected value above tells you where the distribution is centered. The variance tells you how spread out it is:

TEXT
Var(X) = E[(X - ฮผ)ยฒ] = E[Xยฒ] - (E[X])ยฒ

Useful rules: Var(aX + b) = aยฒ ยท Var(X) (shifting does nothing, scaling squares), and for independent X and Y, Var(X + Y) = Var(X) + Var(Y). For dependent variables there is an extra term, the covariance:

TEXT
Cov(X, Y) = E[XY] - E[X]ยทE[Y]
Var(X + Y) = Var(X) + Var(Y) + 2ยทCov(X, Y)

The covariance is positive when X and Y tend to be large together, negative when one is large as the other is small, and zero for independent variables (the reverse is not always true). Dividing by both standard deviations gives the correlation, a number between -1 and 1.

The law of total probability

If events Bโ‚, ..., B_k partition the sample space (exactly one of them always occurs), then for any event A:

TEXT
P(A) = ฮฃ P(A | B_i) ยท P(B_i)

You split a hard question into cases, solve each, and weight by how likely each case is. The same idea works for expected values: E[X] = ฮฃ E[X | B_i] ยท P(B_i). A parts supplier with three factories is the classic setting: the overall defect rate is the weighted average of the factories' rates.

Python Variance, covariance and total probability, exactly

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The sum of two independent dice has variance 35/6, exactly twice that of one die. The cases Cov(X, X + Y) and Cov(X, 7 - X) show positive and negative covariance. The |2X - 7| example shows the warning: the distance from the middle is completely determined by X, yet the covariance is 0, because the dependence is not "straight-line".

Monte Carlo simulation

When counting is awkward, you can estimate a probability by running the experiment many times and recording how often the event happens. The more trials you run, the closer the relative frequency gets to the true probability. This is the Monte Carlo method. Always fix the random seed so that your results can be reproduced, and compare against an exact answer whenever you have one.

The birthday paradox is a good test. In a group of n people, the probability that at least two share a birthday is 1 - (365 ยท 364 ยท ... ยท (365 - n + 1)) / 365โฟ, using the complement rule and permutations. With just 23 people it passes 50%.

Python Birthday paradox: exact versus simulated

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The simulated values land close to the exact ones, and the dice estimate usually improves as the number of trials grows, though the error is random, not guaranteed to shrink at every step.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Two fair dice are rolled. What is the probability that the sum is 9?

    The sum 9 occurs for (3,6), (4,5), (5,4) and (6,3): 4 outcomes out of 36, which is 1/9.
  2. 2. A coin is flipped 3 times. What is the probability of getting at least one head?

    Use the complement. P(no heads) = (1/2)^3 = 1/8, so P(at least one head) = 1 - 1/8 = 7/8.
  3. 3. Events A and B each have positive probability and cannot both happen. Are they independent?

    Independence requires P(A and B) = P(A) P(B). For disjoint events with positive probabilities, the left side is 0 and the right side is positive.
  4. 4. In a Bayes problem, why is P(disease given positive test) often much lower than the test's accuracy?

    When few people are sick, even a small false-positive rate applied to the large healthy group produces many false alarms compared with the few real cases.
  5. 5. What is the expected value of the sum of three fair dice?

    By linearity of expectation, 3 x 3.5 = 10.5. The expected value need not be a possible outcome.

Summary

  • With equally likely outcomes, P(E) = |E| / |S|, so probability reduces to counting; the complement rule 1 - P(E) handles "at least one".
  • Conditional probability P(A | B) = P(A โˆฉ B) / P(B) shrinks the sample space to B; independence means P(A โˆฉ B) = P(A) P(B).
  • Bayes' theorem reverses a conditional, and the law of total probability supplies the denominator; the prior (base rate) matters a lot.
  • Expected value is the weighted average of outcomes and is linear, even for dependent variables.
  • Monte Carlo estimates probabilities by repeated random trials; use a fixed seed and compare with exact results when possible.

Next: Graphs: Terms and Representations, where we move from counting to relationships between objects.