Day 85 — Discrete probability

Updated

July 30, 2026

Day 85 — Discrete probability on finite spaces

Stage VIII · concept day
Goal: Finite \(\Omega\); events; Kolmogorov axioms lite; uniform model; counting probability; mutually exclusive vs independent; union bound.

Why this matters

Probability is the language of hashing collisions, randomized algorithms, reliability, and noise models. We stay finite and discrete — no integrals, no measure theory. Counting from Stage V becomes probability by weighting outcomes.

Note

No labs / no simulation projects. Exact arithmetic with fractions.

Theory

Sample spaces and events

Definition. A finite sample space is a nonempty finite set \(\Omega\) of outcomes.
An event is any subset \(A\subseteq\Omega\).

Examples.
- Fair die: \(\Omega=\{1,2,3,4,5,6\}\).
- Two fair coins: \(\Omega=\{HH,HT,TH,TT\}\).
- Uniform random residue mod \(m\): \(\Omega=\{0,1,\ldots,m-1\}\).

Probability measures (finite)

Definition. A probability on finite \(\Omega\) is a function \(P:2^{\Omega}\to[0,1]\) such that:

  1. \(P(\Omega)=1\).
  2. If \(A\cap B=\emptyset\) then \(P(A\cup B)=P(A)+P(B)\) (finite additivity; extends to any finite disjoint union).

Consequences. \(P(\emptyset)=0\); \(P(A^c)=1-P(A)\); if \(A\subseteq B\) then \(P(A)\le P(B)\);
\(P(A\cup B)=P(A)+P(B)-P(A\cap B)\).

Atomic form. It is enough to specify \(p_\omega=P(\{\omega\})\ge 0\) with \(\sum_{\omega\in\Omega}p_\omega=1\), then \(P(A)=\sum_{\omega\in A}p_\omega\).

Uniform probability

Definition. On finite \(\Omega\), the uniform measure is \(P(A)=|A|/|\Omega|\).

Fair coin / die / random element means uniform on the natural \(\Omega\) unless stated otherwise.

Counting probability

When outcomes are equally likely, \[ P(A)=\frac{\#\text{ favorable}}{\#\text{ possible}}. \] All Stage V counting tools apply: product rule, permutations, combinations, IE.

Mutually exclusive vs independent

Mutually exclusive (disjoint): \(A\cap B=\emptyset\). Then \(P(A\cup B)=P(A)+P(B)\).
Exclusive events with \(P(A),P(B)>0\) cannot be independent (below).

Independent: \(P(A\cap B)=P(A)P(B)\).
Intuition: learning \(B\) occurred does not change probability of \(A\) (formalized Day 86 via conditional probability).

Pairwise vs mutual independence. Pairwise: every pair independent. Mutual for three: also \(P(A\cap B\cap C)=P(A)P(B)P(C)\) and all pairs independent. Pairwise does not imply mutual.

Union bound (Boole’s inequality)

Theorem. For any events \(A_1,\ldots,A_k\), \[ P\Bigl(\bigcup_{i=1}^k A_i\Bigr)\le \sum_{i=1}^k P(A_i). \] Proof. By induction from \(P(A\cup B)\le P(A)+P(B)\).

Use. Upper-bound the probability that some bad event occurs, even with dependence. Central in randomized algorithms and hashing analyses.

Complements and “at least one”

\[ P(\text{at least one of }A_i)=P\Bigl(\bigcup A_i\Bigr)=1-P\Bigl(\bigcap A_i^c\Bigr). \] When independence holds, \(P(\bigcap A_i^c)=\prod P(A_i^c)\).

Connection to hashing (Day 76)

Collision probability \(\le\binom{n}{2}/m\) is a union bound / expectation link: \(P(X\ge 1)\le\mathbb{E}[X]\) for nonnegative integer \(X\) (Markov preview Day 87), and \(\mathbb{E}[X]=\binom{n}{2}/m\).

Discrete random variables (light)

Definition. A random variable is a function \(X:\Omega\to\mathbb{R}\).
Distribution: \(P(X=x)=P(\{\omega:X(\omega)=x\})\).
Bernoulli(\(p\)): \(P(X=1)=p\), \(P(X=0)=1-p\).
Indicator \(I_A(\omega)=1\) if \(\omega\in A\), else \(0\): \(P(I_A=1)=P(A)\).

Worked examples

Example 1 — Die.
\(P(\text{even})=1/2\). \(P(\text{prime})=P(\{2,3,5\})=1/2\).

Example 2 — Two coins.
\(P(\text{exactly one H})=|\{HT,TH\}|/4=1/2\).

Example 3 — Inclusion.
Two dice, \(P(\text{sum}=7\text{ or both even})\). Compute via IE carefully.

Example 4 — Independent coins.
Fair coins independent: \(P(H\text{ on first and H on second})=1/4= (1/2)(1/2)\).

Example 5 — Exclusive not independent.
Die: \(A=\{1,2\}\), \(B=\{3,4\}\). Disjoint; \(P(A\cap B)=0\neq P(A)P(B)=1/4\).

Example 6 — Union bound.
\(P(A\cup B\cup C)\le P(A)+P(B)+P(C)\) always.

Example 7 — Birthday lite.
\(P(\text{collision})\le\binom{n}{2}/m\) under uniform independent days model (union bound on pair collisions).

Example 8 — Cards.
\(P(\text{Ace from 52})=4/52=1/13\).

Example 9 — Complement.
\(P(\text{no six in one die roll})=5/6\); in \(n\) independent rolls \(P(\text{no sixes})=(5/6)^n\), so \(P(\text{at least one six})=1-(5/6)^n\).

Example 10 — Nonuniform.
\(\Omega=\{a,b,c\}\) with \(p_a=1/2\), \(p_b=p_c=1/4\). \(P(\{a,b\})=3/4\).

Exercises

A. Axioms and basics

  1. Prove \(P(\emptyset)=0\) and \(P(A^c)=1-P(A)\) from the axioms.
  2. Prove \(P(A\cup B)=P(A)+P(B)-P(A\cap B)\).
  3. If \(A\subseteq B\), prove \(P(A)\le P(B)\).
  4. Fair die: \(P(\text{multiple of }3)\), \(P(>4)\), \(P(\text{odd and }>2)\).
  5. Construct a nonuniform probability on \(\{1,2,3,4\}\).

B. Counting probability

  1. Two fair dice: \(P(\text{sum}=9)\).
  2. Three fair coins: \(P(\text{exactly two heads})\).
  3. Random permutation of \(\{1,2,3,4\}\): \(P(1\text{ is first})\).
  4. Poker literacy: \(P(\text{flush})\) setup as ratio of counts (need not finish huge arithmetic).
  5. Password: \(4\) independent uniform alphanumeric from \(62\) chars; \(P(\text{all distinct})\).

C. Independence and exclusion

  1. Prove: if \(A,B\) independent then \(A,B^c\) independent.
  2. Give examples of pairwise independent events that are not mutually independent (standard three-bit parity example).
  3. Can two events with \(P(A)=1\) fail independence with \(B\)? Analyze.
  4. Die: are “even” and “\(\le 3\)” independent? Check numerically.

D. Union bound

  1. Prove union bound for \(k=3\) from \(k=2\).
  2. Five events each with probability \(0.01\); bound \(P(\text{at least one})\).
  3. Hashing: \(n=10\), \(m=100\), bound collision probability by \(\binom{10}{2}/100\).
  4. Why can the union bound exceed \(1\)? What does that tell you?

E. Stretch

  1. Derive \(P(\text{at least one six in }n\text{ rolls})=1-(5/6)^n\) and find smallest \(n\) with this \(>1/2\).
  2. Indicator variables: write \(X=\sum I_j\) for number of heads in \(n\) coins.
  3. CS: false positive rates in \(k\) independent tests — union bound on “any false positive.”
  4. When does equality hold in the union bound?

Deep dive — building \(P\) from atoms

Any finite probability is determined by \(p_\omega\ge 0\) summing to \(1\).
Uniform is the special case \(p_\omega=1/|\Omega|\).
Biased coin: \(\Omega=\{H,T\}\), \(p_H=p\), \(p_T=1-p\).
Product spaces: for independent experiments, \(\Omega=\Omega_1\times\Omega_2\) with \(P(\{(\omega_1,\omega_2)\})=P_1(\omega_1)P_2(\omega_2)\).

Deep dive — independence checklist

For two events:

  1. Compute \(P(A)\), \(P(B)\), \(P(A\cap B)\).
  2. Test \(P(A\cap B)\stackrel{?}{=}P(A)P(B)\).
  3. Optionally test \(P(A\mid B)\stackrel{?}{=}P(A)\).

For three events, check all pairs and the triple product — pairwise ≠ mutual.

Standard counterexample (pairwise not mutual).
Two independent fair bits \(X,Y\); let \(Z=X\oplus Y\). Then \(X,Y,Z\) are pairwise independent but \(P(X=Y=Z=1)=0\neq 1/8\).

Additional worked examples

Example 11 — IE two dice.
\(P(\text{sum}\ge 10)=P(10)+P(11)+P(12)=3/36+2/36+1/36=6/36=1/6\).

Example 12 — Union bound loose.
Three events each probability \(0.6\): union bound \(1.8>1\) useless; true probability \(\le 1\).

Example 13 — Complement skill.
\(P(\text{all heads in }n\text{ coins})=2^{-n}\); \(P(\text{at least one tail})=1-2^{-n}\).

Example 14 — Nonuniform atoms.
\(p=(1/2,1/3,1/6)\) on \(\{a,b,c\}\): \(P(\{a,c\})=2/3\).

Example 15 — Hash collision union bound.
\(P(\bigcup_{\text{pairs}}C_{ij})\le\sum P(C_{ij})=\binom{n}{2}/m\).

More exercises

  1. Prove finite additivity for three pairwise disjoint events from the two-event axiom.
  2. Two dice: \(P(\text{doubles}\mid \text{sum even})\) — wait until Day 86 if needed; or compute via definition.
  3. Show exclusive positive-probability events cannot be independent.
  4. Random subset of \([n]\) uniform among \(2^n\) subsets: \(P(1\in S)\).
  5. Password length \(8\) from \(62\) chars: \(P(\text{no digits})\) if each char independent uniform.
  6. Union bound for \(n\) events with \(P(A_i)=1/n^2\): conclude \(P(\bigcup A_i)\le 1/n\).
  7. CS: Bloom filter false positive as union-ish reasoning (prose awareness).
  8. Construct \(\Omega\) with \(4\) outcomes and two independent non-trivial events.

Selected mini-solutions

  1. Multiples of \(3\): \(\{3,6\}\) ⇒ \(1/3\); \(>4\): \(\{5,6\}\) ⇒ \(1/3\).
  2. Sum \(9\): \((3,6),(4,5),(5,4),(6,3)\) ⇒ \(4/36\).
  3. \(P(A\cap B^c)=P(A)-P(A\cap B)=P(A)(1-P(B))\) if independent.
  4. \(\binom{10}{2}/100=0.45\).

Common pitfalls

Pitfall Fix
Assuming uniform without saying so State the model
Confusing exclusive with independent Check definitions
Adding probabilities of non-disjoint events Use IE or bound
\(P(A\text{ and }B)=P(A)+P(B)\) Only if exclusive — and then product fails
Union bound as exact probability It is only \(\le\)
Pairwise independence ⇒ mutual Check triple

Study notes — probability essentials

Idea Formula
Uniform \(P(A)=|A|/|\Omega|\)
Complement \(1-P(A)\)
IE two sets \(P(A)+P(B)-P(A\cap B)\)
Independent \(P(A\cap B)=P(A)P(B)\)
Exclusive \(A\cap B=\emptyset\)
Union bound \(P(\bigcup A_i)\le\sum P(A_i)\)
Indicator mean \(\mathbb{E}[I_A]=P(A)\) (Day 87)

Always state the model (uniform? independent trials?) before computing a number.

Synthesis — discrete probability workout

S1. Axioms: derive \(P(A^c)=1-P(A)\) and \(P(A\cup B)=P(A)+P(B)-P(A\cap B)\).

S2. Two dice: \(P(\text{sum}\in\{7,11\})\).

S3. Test independence of “even” and “prime” on a fair die.

S4. Union bound for \(10\) events each of probability \(0.02\).

S5. Three fair coins: distribution of number of heads.

S6. Pairwise vs mutual independence — give the XOR bits example carefully.

S7. Hashing: bound collision probability for \(n=20\), \(m=200\).

S8. Nonuniform atoms \((1/2,1/4,1/4)\): compute \(P\) of each nontrivial event size.

Checkpoint

  • Can define finite \(\Omega\), events, \(P\)
  • Can compute uniform counting probabilities
  • Can test independence \(P(A\cap B)=P(A)P(B)\)
  • Can apply union bound
  • Distinguish exclusive vs independent
  • Exercises A–D done; synthesis attempted

Two personal takeaways:

  1. …
  2. …

Deeper theory — inclusion-exclusion for two and three sets

Two sets. \(P(A\cup B)=P(A)+P(B)-P(A\cap B)\) from additivity on the disjoint decomposition \[ A\cup B=(A\setminus B)\cup(B\setminus A)\cup(A\cap B). \]

Three sets. \[ \begin{align*} P(A\cup B\cup C)&=P(A)+P(B)+P(C)\\ &\quad-P(A\cap B)-P(A\cap C)-P(B\cap C)\\ &\quad+P(A\cap B\cap C). \end{align*} \] Union bound drops all the negative and higher terms’ careful accounting and keeps only the first sum — always an upper bound, sometimes loose.

Deeper theory — product spaces and independent trials

If experiment 1 has \(\Omega_1\) with \(P_1\) and experiment 2 has \(\Omega_2\) with \(P_2\), the independent product uses \(\Omega=\Omega_1\times\Omega_2\) and \[ P(\{(\omega_1,\omega_2)\})=P_1(\{\omega_1\})P_2(\{\omega_2\}). \] Cylinder events \(A_1\times\Omega_2\) and \(\Omega_1\times A_2\) are independent by construction. This is the model for “two independent dice,” “\(n\) independent coin flips,” and idealized independent hash choices.

Worked examples — careful counting

Example 16 — Two dice sum distribution.
Sums \(2..12\) have probabilities \(1,2,3,4,5,6,5,4,3,2,1\) over \(36\). Thus \(P(\text{sum}=7)=6/36=1/6\), \(P(\text{sum}\ge 10)=6/36=1/6\).

Example 17 — Exactly two heads in four fair coins.
\(\binom{4}{2}/16=6/16=3/8\).

Example 18 — Mutual exclusion block.
\(A=\) “sum is \(2\)”, \(B=\) “sum is \(12\)” on two dice: disjoint, \(P(A\cup B)=1/36+1/36=1/18\), and \(P(A)P(B)=1/36^2\neq 0\) so not independent.

Example 19 — Union bound vs exact.
\(n=3\) events each \(P=0.4\) with complicated dependence: union bound \(1.2\) useless; if mutually exclusive, true union \(1.2\) impossible so they cannot be exclusive; if identical \(A_1=A_2=A_3\), true union is \(0.4\).

Example 20 — Hash collision bound.
\(n=15\), \(m=100\): \(\binom{15}{2}/100=105/100=1.05\) — bound \(>1\), so uninformative as a probability upper bound beyond \(1\); still \(\mathbb{E}[X]=1.05\) is meaningful.

Extra exercises — probability fluency

  1. Prove \(P(A\setminus B)=P(A)-P(A\cap B)\).
  2. Three fair dice: \(P(\text{all different})\).
  3. Fair coin \(n\) times: \(P(\text{more heads than tails})\) for \(n=4\).
  4. Show pairwise independent fair bits \(X,Y,Z=X\oplus Y\) fail mutual independence.
  5. Union bound: \(100\) events each \(p=0.001\); bound \(P(\text{at least one})\).
  6. Random integer uniform in \(1..100\): \(P(\text{divisible by }2\text{ or }5)\) via IE.
  7. Indicator sum: number of sixes in \(10\) die rolls — write \(X=\sum I_j\) and \(\mathbb{E}[X]\) preview.
  8. CS: \(k\) independent alerts each with false positive \(10^{-3}\); bound \(P(\text{any FP})\).

Mini-solutions (selected)

  1. \(6\cdot 5\cdot 4/6^3=120/216=5/9\).
  2. \(P(X=Y=Z=1)=0\) but product of margins \(1/8\).
  3. \(|2\cup 5|=50+20-10=60\), probability \(0.6\).

Closing synthesis card

Tool Formula
Uniform \(|A|/|\Omega|\)
Complement \(1-P(A)\)
IE (two) \(P(A)+P(B)-P(A\cap B)\)
Independent \(P(A\cap B)=P(A)P(B)\)
Union bound \(P(\bigcup)\le\sum P\)

Model first, arithmetic second. Independence is an assumption, not a hope.

Tomorrow

Day 86 — Conditional probability and Bayes.