Probability

Sample Spaces and Events

A sample space S is the set of all possible outcomes of an experiment. An event E is any subset of the sample space.

Equally Likely Formula

When every outcome in the sample space has the same probability:

Three steps to apply:

1. Define the sample space and verify outcomes are equally likely
2. Count total outcomes in S
3. Count favorable outcomes in E

Mutually Exclusive Events

Two events E and F are mutually exclusive if they cannot both happen: E ∩ F = ∅. When events are mutually exclusive:

For n mutually exclusive events:

Inclusion-Exclusion Principle

When events can overlap, simple addition double-counts shared outcomes:

For three events:

The pattern: add singles, subtract pairs, add triples, subtract quadruples…

Definition

A conditional probability states: "what is the chance of E happening given that I have already observed F?" When you condition on F, you enter a universe where F has occurred—F becomes your new sample space.

The Conditional Paradigm

When you condition on an event G, you enter the universe where G has taken place. In that new universe, all the laws of probability still hold:

AND with Independent Events

If events are independent, the probability of and is simple multiplication:

For n mutually independent events:

AND with Dependent Events: The Chain Rule

For events that are not independent, we rearrange the definition of conditional probability:

Equivalently: P(E and F) = P(F|E) · P(E)

The chain rule generalizes to more than two events:

Any event E can be split into two parts: the part in F, and the part not in F. Since F and F^C are mutually exclusive and cover the sample space:

Applying the chain rule to each term:

Generalized: If you can divide your sample space into mutually exclusive events B₁, B₂, …, B_n that cover all outcomes:

Derivation

Start with the definition of conditional probability and the chain rule:

This lets you "flip" a conditional—when you know P(E|F) but need P(F|E):

Using the Law of Total Probability for the denominator:

Key Terminology

Prior P(B)

Your initial belief before observing evidence

Likelihood P(E|B)

Probability of the evidence given your belief is true

Posterior P(B|E)

Your updated belief after accounting for evidence

Normalizer P(E)

Ensures the result is a valid probability

When to Use Bayes' Theorem

Bayes' theorem is essential when you can easily compute P(Evidence|State) but need P(State|Evidence):

• Medical testing: Know test accuracy given disease status; find disease probability given positive test
• Student assessment: Know answer patterns given knowledge; infer understanding from responses
• Spam filtering: Know word frequency in spam vs ham; classify new emails
• Cell phone location: Know signal strength given distance; find location given signal

The pattern: an unobservable belief (B) causes observable evidence (E). We observe E and want to infer B.

Example: Bacteria Evolution

10% of bacteria in a population have a mutation that makes them resistant to antibiotics. The probability that a bacterium with the mutation survives a course of antibiotics is 20%. Without the mutation, the survival probability is 1%.

A log probability is simply log P(E). Since 0 ≤ P(E) ≤ 1, log probabilities are always ≤ 0:

Why Use Log Probabilities?

1. Products become sums: log(P(E) · P(F)) = log P(E) + log P(F). Computers are faster at addition than multiplication.
2. Numerical stability: Python cannot represent probabilities smaller than ~2.225 × 10⁻³⁰⁸. But log(2.225 × 10⁻³⁰⁸) ≈ −307.65, which is easy to store.

Flip a coin n times, where each flip lands heads with probability p. This thought experiment is the basis for much of probability theory—it goes far beyond coins.

Warmups

P(all n heads)? Each flip is independent, so:

P(first k heads, then n−k tails)?

Exactly k Heads

What if we don't care where the heads appear, just that there are exactly k of them?

Any specific ordering with k heads and n−k tails has probability p^k · (1−p)^n−k. The key question: how many such orderings are there?

This is equivalent to: "how many distinct orderings of k H's and (n−k) T's?" — a permutations with repetition problem from Session 01:

Since the orderings are mutually exclusive:

More Than k Heads

Since the events "exactly i heads" for different values of i are mutually exclusive:

Enigma Machine (p. 62)

How many unique configurations does the WWII Enigma machine have? Combines the product rule, combinations, and overcounting correction. Answer: ≈ 159 × 10¹⁸ settings.

Random Shuffles (p. 66)

If you shuffle a deck of cards 7 times, what's the probability your ordering has never occurred in all of human history? Uses equally likely outcomes, independence, and log probabilities. Answer: essentially 1.

Set Diversity & Gini Impurity (p. 71)

What is the probability that two randomly chosen objects from a set are different? Connects counting to the Gini Impurity measure used in Decision Trees and Random Forests.

Bacteria Evolution (p. 74)

How does antibiotic resistance spread? Uses LOTP and Bayes' theorem to show how natural selection works at the probability level.

Definition

Two events are independent if knowing one occurred doesn't change your belief about the other:

Equivalently (via the chain rule): P(E and F) = P(E) · P(F)

Key Properties

• Symmetry: If E is independent of F, then F is independent of E
• Complements: If E and F are independent, so are E and F^C
• Generalized: Events E₁, …, E_n are independent if for every subset, the joint probability equals the product

How to Establish Independence

Independence is either:

1. Proven mathematically by showing P(E|F) = P(E)
2. Declared as a modeling assumption when one event shouldn't influence belief about another

Conditional Independence

Events can be independent when conditioned on some event F, even if they are not unconditionally independent (and vice versa):

Properties of a Random Variable

Random Variables vs Events

An event is a scenario (an outcome or set of outcomes). A random variable is more like an experiment—it will take on an outcome eventually. Probabilities are over events, so to talk about probability in the context of an RV, you construct an event using relational operators: <, ≤, >, ≥, =, ≠

Two Types of Random Variables

• Discrete — can only take on integer values (e.g., number of heads, number of errors, class label)
• Continuous — can take on decimal values (e.g., height, weight, time, temperature)

We develop our intuitions using discrete random variables first, then extend to continuous.

In empirical research and system evaluation, random variables let you talk precisely about two things:

Once you have this language, you can reason under uncertainty:

• Forward reasoning: “If my classifier has accuracy p = 0.8 and I test on n = 100 samples, how many correct?”
• Backward reasoning: “I observed 80/100 correct. What can I conclude about true accuracy?”

Probabilities Must Sum to 1

For X to be a proper random variable:

Why? Each value is a mutually exclusive event, and X must take on some value. These mutually exclusive cases define the entire sample space.

From Data to Histograms to PMFs

A dataset is itself an approximation of a PMF. If you simulate summing two dice 10,000 times, the normalized histogram (count of each value / n) approximates the true PMF. By the empirical definition of probability, as n grows, the approximation improves.

Properties of Expectation

Standard Deviation

Variance has squared units (points², dollars²). Standard deviation is in the same units as X, making it more interpretable. “The spread of this grader is 7.2 points” is easier to understand than “the variance is 52 points².”

Properties of Variance

Adding a constant b shifts the distribution but doesn't change the spread. Multiplying by a scales the spread by a².

There are classic, commonly-seen random variable types in probability. If you can recognize that a random variable fits one of these types, you can use its pre-derived PMF, expectation, variance, and other properties. Think of them like classes in programming—you provide parameters and get all the properties for free.

Bernoulli Distribution

The simplest parametric distribution: a single binary outcome.

Examples: coin flip, whether a disk drive crashed, whether a user clicks an ad, whether a classifier is correct on a given instance.

Indicator Random Variable

An indicator variable I is a Bernoulli RV that is 1 when an event A occurs and 0 otherwise. Key property: E[I] = P(A). This converts events into numbers—very useful for decomposing complex problems.

Binomial Distribution

The number of successes in n independent trials, each with probability p.

A binomial is the sum of n independent Bernoulli indicators: X = Σ Y_i where each Y_i ∼ Bern(p).

Examples: # of heads in n coin flips, # of 1’s in a random bit string, # of disk drives crashed in a cluster, # of correct predictions out of n test instances.

Binomial in Python

from scipy import stats

# P(X = 2) for X ~ Bin(n=5, p=0.6)
p_x = stats.binom.pmf(2, n=5, p=0.6)
print(f'P(X = 2) = {p_x:.4f}')  # 0.2304

# Generate 100 random samples from Bin(n=10, p=0.3)
samples = stats.binom.rvs(n=10, p=0.3, size=100)
print(samples)

Poisson Distribution

The probability of a given number of events in a fixed interval of time (or space), assuming events occur at a constant mean rate and independently of time since the last event.

Other Discrete Distributions

The Geometric distribution answers: “How long until the first success?” (e.g., how many users until the first click). PMF: P(X = x) = (1 − p)^x−1 · p.

The Categorical distribution handles non-numeric outcomes (e.g., weather: sunny, cloudy, rainy, snowy). Since values aren’t numbers, there is no expectation or variance—just a PMF as a table.

From Discrete to Continuous

So far, all our random variables have been discrete—they take on integer values. But many quantities (height, weight, time, temperature) can take on any real value. These are continuous random variables.

The key difference: for continuous RVs, the probability of any exact value is zero. (What is the probability a bus arrives at exactly 2:17pm and 12.1233391 seconds? Zero.) Instead, we talk about probabilities over ranges.

Cumulative Distribution Function (CDF)

The CDF avoids solving integrals every time:

Expectation and Variance (Continuous)

For continuous RVs, sums become integrals:

All the properties of expectation (linearity, LOTUS, expectation of sums) hold for continuous RVs too.

Uniform Distribution

The simplest continuous distribution: equally likely to take on any value in a range.

Normal (Gaussian) Distribution

The most important continuous distribution. It arises naturally from the sum of many independent random variables (Central Limit Theorem, Session 04).

Standard Normal: Z ∼ N(0, 1)

Any Normal X can be converted to the standard Normal: Z = (X − μ) / σ. Then F_X(x) = Φ((x − μ) / σ).

from scipy import stats

# P(X > 0) for X ~ N(3, 16)  (mean=3, variance=16, so std=4)
p = 1 - stats.norm.cdf(0, loc=3, scale=4)
print(f'P(X > 0) = {p:.4f}')  # 0.7734

# Note: scipy uses standard deviation (scale), not variance!

Exponential Distribution

Measures the time until the next event in a Poisson process. (Poisson counts events in a fixed time; Exponential measures time between events.)

Computing exact Binomial probabilities can be hard for large n. Two key approximations:

Normal Approximation of the Binomial

For large n with moderate p, the Binomial looks like a bell curve. Match the mean and variance:

Discrete Distributions

Continuous Distributions

Part 1: Core Probability

1. A bag contains 5 red and 3 blue balls. You draw two balls without replacement. What is P(both red)? Use the chain rule.
2. A rare disease affects 1 in 10,000 people. A test has 99% sensitivity and 99% specificity. If you test positive, what's the probability you have the disease?
3. You flip a fair coin until you get heads. What is the probability it takes exactly 3 flips?
4. Events A and B have P(A) = 0.4, P(B) = 0.3, P(A or B) = 0.6. Are A and B independent?
5. In 10 fair coin flips, what is P(exactly 5 heads)? What is P(at least 8 heads)?
6. A system has 3 independent components, each working with probability 0.9. What is P(at least one works)?
7. If P(E) = 10⁻²⁰⁰ and P(F) = 10⁻¹⁵⁰, and E and F are independent, compute log P(E and F).

Part 2: Random Variables

8. A server cluster has 50 computers. Each crashes independently with probability 0.5. What is the standard deviation of the number of crashes? (Hint: identify the distribution.)
9. A machine learning classifier makes 50 binary predictions, each independently correct with probability 6/25. What is P(at least 1 correct)?
10. You are showing an ad to 30 people. Each person ignores it independently with probability 2/3. What is the expected number of ad clicks?
11. Let X ∼ N(3, 16). What is P(X > 0)? What is P(2 < X < 5)?
12. Earthquakes of magnitude 8.0+ occur at a rate of 0.002 per year. What is the probability of at least one in the next 4 years? (Hint: model the time until next event.)
13. 100 visitors see a new website design. Under the null hypothesis that each converts with probability 0.5, what is P(65 or more conversions)? Use the Normal approximation.
14. A random variable X has PMF: P(X = 1) = 0.3, P(X = 2) = 0.5, P(X = 3) = 0.2. Compute E[X], E[X²], and Var(X).