Stanford · Probability for AI · Week 1 / PAI001
Axioms of Probability: Complement, OR and Independence
My first week of Stanford's Probability for AI (PAI) covered the ground floor of probability: three axioms that every other rule is built on, the two rules that follow from them for "not" and "or", conditional probability, and independence, the idea that makes many AI calculations possible. Before the concepts, this note starts with something I needed first myself: the symbols, and how to read them aloud.
- section
- key term
- reading note
ELLE · READING COMPANIONTake a moment to connect the ideas
A few foundations, with Elle
Tap a concept to explore it, then try three short questions. You can change any answer.
Sample space and event
The sample space S is the set of every possible outcome; an event is a subset of it. For one die roll, S = {1, …, 6} and "even" is the event {2, 4, 6}.
Mutually exclusive
Two events that cannot happen together: E ∩ F = ∅. Only then can P(E or F) be found by simply adding P(E) and P(F).
Conditional probability
P(E | F), read "the probability of E given F": the share of outcomes in F that are also in E, P(E and F) / P(F).
Independence
Knowing that F happened does not change the probability of E: P(E | F) = P(E), so P(E and F) = P(E) · P(F). It can appear or disappear once you condition on a third event.
The big picture: from three axioms to independence
Start at the top left with the notation row: the probability of an event, and the three words NOT, OR and AND in blue. Below are Kolmogorov's three axioms in purple and the OR rule with its two branches. The sticky note at the top names the three ideas to keep: complement, mutually exclusive and independence. The right half is independence: the product rule, the circled meaning in red, conditional probability and the chain rule, and the red loop showing that the two definitions say the same thing. The red stars at the bottom right are the three points I starred in class, and my takeaway is in the corner.
Tidied up from my handwritten page, with the axioms corrected and short examples added.
Tap a region to jump to that part of the note; use ⤢ Enlarge to see the full picture.
Notation first: probability symbols and how to read them
Probability formulas are short, but each symbol carries a precise meaning. Being able to read a formula aloud is the first step to understanding it. The examples below use one roll of a fair six-sided die, with E = "an even number" = {2, 4, 6} and F = "more than 3" = {4, 5, 6}.
Events and probabilities
| Symbol | Read aloud | Meaning | Example (one die roll) |
|---|---|---|---|
| S (also Ω) | "S", the sample space; Ω is "omega" | The set of all possible outcomes | S = {1, 2, 3, 4, 5, 6} |
| E, F | "event E", "event F" | An event: a subset of S | E = {2, 4, 6} |
| P(E) | "P of E", "the probability of E" | A number from 0 to 1 | P(E) = 3/6 = 0.5 |
| |E| | "the size of E" | How many outcomes are in E | |E| = 3 |
| Eᶜ (also Ē, E′, ¬E) | "E complement", "not E" | E does not happen | Eᶜ = {1, 3, 5} |
| E ∪ F | "E union F", "E or F" | At least one of them happens | E ∪ F = {2, 4, 5, 6} |
| E ∩ F, EF | "E intersection F", "E and F" | Both happen | E ∩ F = {4, 6} |
| P(E, F) | "the joint probability of E and F" | The same as P(E ∩ F): the comma means "and" | P(E, F) = 2/6 |
| P(E | F) | "the probability of E given F" | The probability of E once we know F happened. The bar is "given", not division | P(E | F) = 2/3 |
| Fᵢ, P(Fᵢ) | "F sub i", "the probability of F sub i" | Event number i in a list F₁, F₂, … | F₁ = "roll a 1" |
| P(E | Fᵢ) | "the probability of E given F sub i" | The probability of E once we know Fᵢ happened | P(even | roll a 2) = 1 |
| ∅ | "the empty set" | No outcomes: an impossible event | E ∩ Eᶜ = ∅ |
| ⊆ | "is a subset of" | Every outcome of the first is in the second | {4, 6} ⊆ E, so P({4, 6}) ≤ P(E) |
| E ⊥ F | "E is independent of F" | P(E ∩ F) = P(E) · P(F) | two separate dice rolls |
| E ⊥ F | G | "E and F are conditionally independent given G" | Independent once G is known | see the last section |
Common math symbols
| Symbol | Read aloud | Example |
|---|---|---|
| = | "equals", "is equal to" | P(S) = 1 |
| ≠ | "is not equal to" | P(E | F) ≠ P(E) |
| > / < | "is greater than" / "is less than" | P(E | F) > P(E) |
| ≥ / ≤ | "is greater than or equal to" / "is less than or equal to" | 0 ≤ P(E) ≤ 1 |
| ≈ | "is approximately equal to" | 1/3 ≈ 0.33 |
| ∈ | "is an element of", "belongs to", "is in" | 2 ∈ E |
| ∀ | "for all" | ∀ E: P(E) ≥ 0 |
| ∃ | "there exists" | ∃ an outcome in E ∩ F |
| ∼ | "follows", "is distributed as" (statistics) | X ∼ Bernoulli(0.5) |
| Σ | "the sum of", "summation"; the letter is "sigma" | Σ P(outcome) over S = 1 |
| ∏ | "the product of"; the letter is "pi" | 1 − ∏ (1 − pᵢ) |
| n! | "n factorial" | 3! = 3 × 2 × 1 = 6 |
| (n k), also C(n, k) | "n choose k" | (5 choose 2) = 10 |
Subscripts, superscripts and Greek letters
These come up constantly in statistics and machine learning courses.
| Symbol | Read aloud | Usually means |
|---|---|---|
| Xᵢ | "X sub i" | Item number i |
| Xᵢⱼ | "X sub i j" | Row i, column j |
| X² / X³ | "X squared" / "X cubed" | Powers |
| Xⁿ | "X to the power of n", "X to the n" | Power n |
| X̄ | "X bar" | The sample mean of X |
| β̂ | "beta hat" | An estimate of β from data |
| μ | "mu" | A mean |
| σ / σ² | "sigma" / "sigma squared" | Standard deviation / variance |
| θ | "theta" | A model parameter |
The same bar means different things: over an event, Ē is the complement ("not E"); over a variable, X̄ is the mean. Read it as "bar" in both cases and tell them apart from context.
Reading a whole formula aloud
The OR rule (inclusion–exclusion)
P(E ∪ F) = P(E) + P(F) − P(E ∩ F)
"The probability of E union F equals the probability of E plus the probability of F minus the probability of E intersection F."
Conditional probability
P(E | F) = P(E ∩ F) / P(F)
"The probability of E given F equals the probability of E intersection F divided by the probability of F."
Bayes' theorem (later in the course)
P(Fᵢ | E) = P(E | Fᵢ) P(Fᵢ) / P(E)
"The probability of F sub i given E equals the probability of E given F sub i times the probability of F sub i, divided by the probability of E."
The law of total probability (later in the course; F₁ … Fₙ must split S into non-overlapping pieces)
P(E) = Σᵢ₌₁ⁿ P(E | Fᵢ) P(Fᵢ)
"The probability of E equals the sum, from i equals one to n, of the probability of E given F sub i times the probability of F sub i."
A practical difference: when reading a formula aloud in class, people use the short forms, such as "F sub i", "X bar" and "beta hat". When explaining what it means, they use fuller phrases, such as "the probability of event F sub i" or "the estimated coefficient beta". Two more habits help: read the vertical bar as "given" every time, and read "and", "or" and "not" as set operations (intersection, union and complement). Textbooks often write one idea in two or three ways (E ∩ F, EF, P(E, F)), so recognising the variants matters more than memorising one.
Watch this part Watch the special video: How to read probability symbols out loud
Kolmogorov's three axioms
Modern probability rests on three axioms set out by the mathematician Andrey Kolmogorov in 1933. An axiom is a rule accepted without proof; everything else is derived from it.
| Axiom | In symbols | In words |
|---|---|---|
| 1 | 0 ≤ P(E) ≤ 1 | Every probability is between 0 and 1 |
| 2 | P(S) = 1 | Something in the sample space always happens |
| 3 | If E ∩ F = ∅, then P(E or F) = P(E) + P(F) | For mutually exclusive events, probabilities add |
When every outcome is equally likely, a probability is a count: P(E) = |E| / |S|. For an even number on a die that is 3/6. This counting formula is a special case, not a definition: a loaded die still obeys the three axioms, but not |E| / |S|.
My handwritten page wrote P(E) + P(Eᶜ) = 1 next to "Kolmogorov's three axioms". That equation is true, but it is not one of the axioms; it is the first rule derived from them (next section). The axiom it replaced is P(S) = 1.
NOT: the complement rule
E and Eᶜ are mutually exclusive, and together they make up the whole sample space. Axioms 2 and 3 therefore give P(E) + P(Eᶜ) = P(S) = 1, so
P(Eᶜ) = 1 − P(E)
This rule is most useful when "not E" is easier to count than E. If a language model gives the word "a" a 0.64 chance of being next, the chance that the next word is anything else is 1 − 0.64 = 0.36.
OR: adding probabilities without double counting
P(E or F) depends on whether the two events can happen together.
| Case | Rule | Die example (E = even, F = more than 3) |
|---|---|---|
| Mutually exclusive: E ∩ F = ∅ | P(E or F) = P(E) + P(F) | E = {2}, F = {5}: 1/6 + 1/6 = 2/6 |
| Overlapping | P(E or F) = P(E) + P(F) − P(E and F) | 3/6 + 3/6 − 2/6 = 4/6 |
The second line is called inclusion–exclusion. Adding P(E) and P(F) counts the outcomes in both, here 4 and 6, twice, so the overlap is subtracted once. Forgetting it is easy to spot when the "probability" comes out above 1.
Conditional probability and the chain rule
The conditional probability of E given F is the probability of E once we know F has happened:
P(E | F) = P(E and F) / P(F), defined when P(F) > 0.
Knowing F shrinks the world to the outcomes in F, and we ask what share of them are also in E. On the die, knowing the roll is more than 3 leaves {4, 5, 6}; two of those are even, so P(even | more than 3) = 2/3, up from 1/2.
Multiplying both sides by P(F) gives the chain rule:
P(E and F) = P(E | F) · P(F)
All the rules above also hold inside a condition: P(Eᶜ | G) = 1 − P(E | G), for example, as long as every term is conditioned on the same G.
Independence
E and F are independent when knowing that F happened does not change our belief that E will happen:
P(E | F) = P(E)
Put that into the chain rule and the product rule appears: P(E and F) = P(E) · P(F). The two forms say the same thing; the red loop in the big picture shows that step. Two separate rolls of a die are independent: the first roll tells you nothing about the second, so P(two sixes) = 1/6 × 1/6 = 1/36.
Two truths about independence follow from the definition:
- It is symmetric: if E is independent of F, then F is independent of E.
- It carries over to complements: if E is independent of F, then E is also independent of Fᶜ. Knowing that F did not happen tells you just as little.
Independent is not the same as mutually exclusive. Mutually exclusive events cannot happen together, so learning that one happened tells you the other did not: that is strong dependence.
Independence is powerful for AI because it turns one hard joint probability into a product of simple ones. Without it, a model has to estimate how many things behave together; with it, each piece can be estimated on its own and multiplied.
At least one works = not all fail
"At least one" questions are hard to add up directly, but easy through the complement. If n parts work independently with probabilities p₁ … pₙ:
P(at least one works) = 1 − P(all fail) = 1 − (1 − p₁)(1 − p₂)…(1 − pₙ)
The complement turns OR into AND, and independence turns AND into multiplication. In the course reader's example, three independent routers that each work with probability 0.9 give a working path with probability 1 − 0.1³ = 0.999.
Independence can change with conditioning
Whether two events are independent can change once we condition on a third event.
- Independent can become dependent. Two fair coin flips are independent. Now suppose we learn that exactly one of them landed heads. If the first flip was heads, the second must be tails: given that information, they are no longer independent.
- Dependent can become independent. The test results of two patients from the same clinic may move together because they share the same lab; once we know which lab ran the tests, the results can be independent of each other.
This is called conditional independence, written E ⊥ F | G. Being conditionally independent given G does not mean being independent without G, and the reverse is not true either, so it is worth checking each time which condition a calculation assumes.
My thoughts
My experience of the first lesson: if I had been taught this way earlier, I would certainly have liked mathematics more. Chris Piech's teaching is simple and easy to follow. This note collects the important concepts, but if you want to understand them more deeply, I really recommend taking the course.
Before the concepts I studied the symbols, because reading a formula aloud correctly is half of understanding it. After that, the concepts to know are few. Kolmogorov's three axioms: every probability is between 0 and 1, the whole sample space has probability 1, and if E and F do not overlap, the probability of E or F is the sum of their probabilities. The complement rule, that an event happening and not happening add up to 1, follows from them. If E and F do overlap, the sum has to subtract the part counted twice, the probability that E and F both happen.
Independence means that F happening does not affect whether E happens; then the probability of both is P(E) × P(F), and conditional probability, P(E | F) = P(E and F) / P(F), shows why. If E is independent of F, then F is independent of E, and E is also independent of not F. Two points I starred: "at least one works" is the same as "not all fail", and an independence relationship can change with conditioning.
Learning sources and resources
This note is based on my study notes from week 1 of Probability for AI (PAI), Stanford's free online course taught by Chris Piech and Mehran Sahami. Definitions and examples were checked against the course's reader:
- Chris Piech, Probability for Computer Scientists, the CS109 course reader: Axioms of Probability, Conditional Probability and Independence (including the router network example).
- A. N. Kolmogorov (1933), Grundbegriffe der Wahrscheinlichkeitsrechnung; English translation Foundations of the Theory of Probability (1950).
Try it yourself
- Seeing Theory: Basic Probability (Brown University): interactive coin and die simulations that show probabilities settling as the number of trials grows.
- Seeing Theory: Compound Probability: drag Venn diagrams to see unions, intersections and conditional probability change.