Engineering / Mathematics — Discrete Probability
Conditional Probability and Independence
Conditional probability, Bayes' theorem, independence and the distinction between pairwise and mutual independence.
Executive summary
Conditioning restricts attention to a sub-population and renormalises. Independence is the statement that conditioning changes nothing.
The gap between pairwise and mutual independence is the single most consequential subtlety here, and it is exploited deliberately in hashing constructions.
Learning objectives
- Define conditional probability and state Bayes' theorem.
- Distinguish pairwise from mutual independence.
- Recognise where the weaker notion suffices.
01Conditioning
Conditional probability
For events A, B with P(B) > 0:
P(A | B) = P(A ∩ B) / P(B).
Conditioning on B produces a genuine probability distribution supported on B. The definition is a renormalisation, not a new axiom.
Bayes' theorem
P(A | B) = P(B | A) · P(A) / P(B), and with a partition {Aᵢ},
P(B) = Σᵢ P(B | Aᵢ) P(Aᵢ) — the law of total probability.
02Independence
Independence
Events A, B are independent if P(A ∩ B) = P(A)P(B).
A family {Aᵢ} is pairwise independent if every two are independent, and mutually independent if every finite subfamily satisfies P(∩Aᵢ) = ∏P(Aᵢ).
The distinction is not a curiosity. Pairwise independence is far cheaper to construct — a family of pairwise independent hash functions needs only logarithmically many random bits, while mutual independence needs a truly random function. Many analyses need only the weaker property, and the saving is what makes hashing constructions practical.
03Where the weaker notion suffices
| Result | Independence required |
|---|---|
| Variance of a sum | Pairwise |
| Chebyshev-based concentration | Pairwise |
| Collision probability bounds | Pairwise |
| Leftover hash lemma | Pairwise (universal families) |
| Exponential tail bounds | Mutual |
| Repeated-trial error reduction | Mutual |
The pattern is that second-moment arguments need only pairwise independence, while arguments multiplying failure probabilities across many trials need mutual independence. Knowing which side of that line an analysis sits on determines how much randomness must be supplied.
04Frequently asked questions
Is independence the same as disjointness?
They are close to opposites. Disjoint events with positive probability are strongly dependent: knowing one occurred rules the other out entirely. Independence means knowing one occurred tells nothing about the other.
Can an event be independent of itself?
Only if its probability is 0 or 1, since P(A) = P(A)² forces that. This is a useful sanity check: a genuinely uncertain quantity is never independent of itself.
Why do hashing constructions settle for pairwise independence?
Because storing a mutually independent random function on a large domain requires randomness proportional to the domain size, which defeats the purpose. Pairwise independent families need only a couple of random field elements and still support every second-moment argument.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 99-104.
This page carries the durable method layer only: definitions, constructions, algorithms, complexity results and selection criteria, authored originally for KEVOS. No text is transcribed or paraphrased from the source, and no numeric tables or benchmark data are reproduced — these are routed to live authoritative sources instead.
Author: Kevin Jogin. Last reviewed 2026-08-07.