Day 29 — Probability, Conditional Probability & Expectation

Day 29 — Probability, Conditional Probability & Expectation

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

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

C. Independence and exclusion

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

D. Union bound

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

E. Stretch

19. Derive \(P(\text{at least one six in }n\text{ rolls})=1-(5/6)^n\) and find smallest \(n\) with this \(>1/2\).
    
20. Indicator variables: write \(X=\sum I_j\) for number of heads in \(n\) coins.
    
21. CS: false positive rates in \(k\) independent tests — union bound on “any false positive.”
    
22. 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

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

---

Selected mini-solutions

4. Multiples of \(3\): \(\{3,6\}\) ⇒ \(1/3\); \(>4\): \(\{5,6\}\) ⇒ \(1/3\).
   
5. Sum \(9\): \((3,6),(4,5),(5,4),(6,3)\) ⇒ \(4/36\).
   
6. \(P(A\cap B^c)=P(A)-P(A\cap B)=P(A)(1-P(B))\) if independent.
   
7. \(\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

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

---

Mini-solutions (selected)

32. \(6\cdot 5\cdot 4/6^3=120/216=5/9\).
    
33. \(P(X=Y=Z=1)=0\) but product of margins \(1/8\).
    
34. \(|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.

---

Day 86 — Conditional probability, chain rule, and Bayes

Stage VIII · concept day
Goal: Define \(P(A\mid B)\); chain rule; Bayes theorem; total probability; base-rate fallacy examples; independence tests via conditionals.

Why this matters

Conditional probability is how evidence updates beliefs. Spam filters, medical tests, debugging with logs, and “given that the hash collided…” are conditional statements. Base-rate fallacies are among the most common quantitative mistakes in technical life.

Note

No labs. Hand computations with fractions; word problems as math, not software.

---

Theory

Conditional probability

Definition. If \(P(B)>0\), the conditional probability of \(A\) given \(B\) is \[ P(A\mid B)=\frac{P(A\cap B)}{P(B)}. \]

Interpretation. Restrict the sample space to \(B\), renormalize.

Immediate: \(P(B\mid B)=1\); \(P(A\cap B)=P(A\mid B)P(B)\).

Chain rule

\[ P(A\cap B)=P(A\mid B)P(B)=P(B\mid A)P(A). \] For three events: \[ P(A\cap B\cap C)=P(A)\,P(B\mid A)\,P(C\mid A\cap B) \] (when the intermediate conditionings are defined).

Law of total probability

If \(B_1,\ldots,B_k\) partition \(\Omega\) (pairwise disjoint, union \(\Omega\)) and \(P(B_i)>0\), then for any event \(A\), \[ P(A)=\sum_{i=1}^k P(A\mid B_i)P(B_i). \] Tree diagrams: branch on partition, multiply along paths, sum paths into \(A\).

Bayes’ theorem

Theorem (Bayes). If \(P(A)>0\) and \(P(B)>0\), \[ P(A\mid B)=\frac{P(B\mid A)P(A)}{P(B)}. \] With total probability in the denominator for a partition \(\{A_i\}\): \[ P(A_j\mid B)=\frac{P(B\mid A_j)P(A_j)}{\sum_i P(B\mid A_i)P(A_i)}. \]

Language. \(P(A)\) prior; \(P(A\mid B)\) posterior; \(P(B\mid A)\) likelihood.

Independence via conditionals

Events \(A,B\) with \(P(B)>0\) are independent iff \(P(A\mid B)=P(A)\) (equivalently \(P(B\mid A)=P(B)\) when \(P(A)>0\)).
This matches \(P(A\cap B)=P(A)P(B)\).

Base-rate fallacy

People confuse \(P(\text{disease}\mid \text{positive test})\) with \(P(\text{positive}\mid \text{disease})\), ignoring the base rate \(P(\text{disease})\).

Canonical setup. Rare disease with prevalence \(p\) small; test sensitivity \(P(+|D)=s\) high; false positive rate \(P(+|D^c)=f\). Then \[ P(D\mid +)=\frac{s p}{s p + f(1-p)}, \] which can be modest even when \(s\approx 1\) if \(p\ll f\).

Multiple updates (idea)

Posterior becomes prior for the next independent piece of evidence (when conditional independence structures allow). Full graphical models are out of scope; the algebra of one Bayes update is enough.

Confusion matrix literacy (tests)

	\(D\)	\(D^c\)
\(+\)	TP	FP
\(-\)	FN	TN

Sensitivity \(=TP/(TP+FN)\); specificity \(=TN/(TN+FP)\); false positive rate \(=1-\text{specificity}\). Bayes uses these with prevalence.

---

Worked examples

Example 1 — Cards.
Draw one card. \(P(\text{Ace}\mid \text{spade})=\frac{1/52}{13/52}=1/13\). Same as unconditional Ace rate — suit and rank independent in a fair deck for these events.

Example 2 — Two children.
Classic care needed: define \(\Omega\) carefully. “At least one boy” vs “first is boy” change conditionals.

Example 3 — Total probability.
Factory: lines \(B_1,B_2\) make \(60\%,40\%\) of items; defect rates \(1\%,3\%\).
\(P(\text{defect})=0.01\cdot 0.6+0.03\cdot 0.4=0.018\).

Example 4 — Bayes on defects.
\(P(B_1\mid\text{defect})=\frac{0.01\cdot 0.6}{0.018}=\frac{0.006}{0.018}=\frac13\).

Example 5 — Medical base rate.
Prevalence \(p=0.001\), sensitivity \(0.99\), false positive rate \(0.01\).
\(P(D\mid +)=\frac{0.99\cdot 0.001}{0.99\cdot 0.001+0.01\cdot 0.999}=\frac{0.00099}{0.00099+0.00999}=\frac{0.00099}{0.01098}\approx 0.09\).
Only about \(9\%\) despite a “\(99\%\) accurate” slogan (ambiguous slogan!).

Example 6 — Independence check.
Two fair coins. \(A=\) first H, \(B=\) second H. \(P(A\mid B)=1/2=P(A)\).

Example 7 — Die.
\(P(\text{six}\mid \text{even})=P(\{6\})/P(\{2,4,6\})=(1/6)/(1/2)=1/3\).

Example 8 — Chain rule.
\(P(A\cap B\cap C)\) for sequential draws without replacement: multiply successive conditionals.

Example 9 — Spam literacy.
Prior \(P(\text{spam})\), likelihood of word given spam vs ham — Bayes filter idea (not building one).

Example 10 — False intuition.
“Test is \(95\%\) accurate” is ambiguous: does it mean sensitivity, specificity, or PPV \(P(D\mid +)\)? Always expand into conditionals.

---

Exercises

A. Definition and chain rule

1. From the definition, prove \(P(A\cap B)=P(A\mid B)P(B)\).
   
2. Die: compute \(P(\text{odd}\mid \ge 4)\).
   
3. Two fair dice: \(P(\text{sum}=7\mid \text{first die shows }3)\).
   
4. Urn: \(3\) red, \(2\) blue; draw two without replacement. \(P(\text{second red}\mid \text{first red})\).
   
5. Write the three-event chain rule and use it on cards drawn without replacement for three aces in a row (setup).

B. Total probability

6. Rework Example 3 with defect rates \(2\%\) and \(5\%\), production \(70\%/30\%\).
   
7. Three machines equal output, defect rates \(1\%,2\%,3\%\). Find \(P(\text{defect})\).
   
8. Prove the law of total probability from additivity and definition of conditional prob.
   
9. Tree diagram: first coin, then if H roll die “success on 6”, if T success automatic — find \(P(\text{success})\).

C. Bayes

10. Complete Example 5 with \(p=0.01\) instead of \(0.001\); compare.
    
11. Factory Example 4 variant: find \(P(B_2\mid\text{defect})\).
    
12. Two types of cabs: \(85\%\) of cabs black, \(15\%\) blue. Witness says blue, \(80\%\) reliable both ways. Find \(P(\text{cab blue}\mid \text{witness says blue})\).
    
13. State Bayes and identify prior, likelihood, posterior in problem 12.
    
14. Prove Bayes from the chain rule.

D. Independence and fallacies

15. Show \(A\perp B\) iff \(P(A\mid B)=P(A)\) when \(P(B)>0\).
    
16. Explain the base-rate fallacy in 5–8 sentences with numbers from Example 5.
    
17. Invent a CS false-positive scenario (intrusion alerts) with base rates; compute PPV.
    
18. Are “sum is even” and “first die is \(1\)” independent for two dice? Check.

E. Stretch

19. Screening: sensitivity \(0.95\), specificity \(0.95\), prevalence \(0.005\). Compute \(P(D\mid +)\) and \(P(D^c\mid -)\).
    
20. Show that if \(P(A\mid B)>P(A)\) then \(P(B\mid A)>P(B)\) (when defined) — evidence is symmetric in a sense.
    
21. Conditional independence idea: \(P(A\cap B\mid C)=P(A\mid C)P(B\mid C)\). Give a verbal example.
    
22. Simpson’s paradox awareness: one paragraph that aggregation can reverse conditionals — no full proof required.

---

Deep dive — Bayes computational pattern

1. Name hypotheses H1..Hk (partition) and evidence E
2. Write priors P(Hi)
3. Write likelihoods P(E|Hi)
4. Compute P(E) = sum_i P(E|Hi)P(Hi)
5. Posterior P(Hj|E) = P(E|Hj)P(Hj) / P(E)
6. Sanity: posteriors sum to 1

Natural frequencies (optional pedagogy): “1000 people; 1 diseased; …” often reduces base-rate errors versus pure decimals.

---

Deep dive — medical numbers template

Symbol	Meaning
\(p\)	prevalence \(P(D)\)
\(s\)	sensitivity \(P(+|D)\)
\(f\)	false positive rate \(P(+|D^c)\)
PPV	\(P(D|+)=sp/(sp+f(1-p))\)
NPV	\(P(D^c|-)\) via similar algebra

---

Additional worked examples

Example 11 — Natural frequencies.
\(1000\) people, \(p=0.001\) ⇒ \(1\) diseased. Sensitivity \(0.99\) ⇒ \(\approx 1\) true positive. \(999\) healthy, \(f=0.01\) ⇒ \(\approx 10\) false positives. PPV \(\approx 1/11\approx 9\%\).

Example 12 — Two-die conditional.
\(P(\text{sum}=7\mid \text{first}=2)=P(\text{second}=5)=1/6\).

Example 13 — Without replacement.
Urn \(5\) red \(5\) blue; \(P(\text{2nd red}\mid \text{1st blue})=5/9\).

Example 14 — Independence failure.
Die: \(A=\{\le 2\}\), \(B=\{\text{even}\}\). \(P(A\cap B)=P(\{2\})=1/6\), \(P(A)P(B)=(1/3)(1/2)=1/6\) — independent. Change \(B\) to \(\{\le 3\}\) and recompute.

Example 15 — Spam idea.
Prior \(P(S)=0.4\), \(P(W|S)=0.3\), \(P(W|H)=0.05\).
\(P(S|W)=\frac{0.3\cdot 0.4}{0.3\cdot 0.4+0.05\cdot 0.6}=\frac{0.12}{0.12+0.03}=0.8\).

---

More exercises

23. Prevalence \(0.02\), sensitivity \(0.9\), FPR \(0.05\): compute PPV.
    
24. Prove \(P(A\cap B\cap C)=P(A)P(B|A)P(C|A\cap B)\).
    
25. Cab problem variant: \(70\%\) green cabs; witness \(75\%\) accurate; posterior green given “green.”
    
26. Show \(P(A|B)>P(A)\) implies \(P(B|A)>P(B)\) when all defined.
    
27. CS: IDS alerts with base rate of true attacks \(10^{-4}\); FPR \(10^{-3}\); compute PPV order of magnitude.
    
28. Total probability with \(4\) machines equal share, defect rates \(1,2,3,4\%\).
    
29. Conditional of complement: express \(P(A^c|B)\) in terms of \(P(A|B)\).
    
30. Explain in prose why \(P(\text{positive}|\text{disease})\) is not “the chance I’m sick if positive.”

---

Selected mini-solutions

2. \(P(\text{odd}\mid\ge 4)=P(\{5\})/P(\{4,5,6\})=(1/6)/(1/2)=1/3\).
   
3. \(p=0.01\): PPV \(=\frac{0.99\cdot 0.01}{0.99\cdot 0.01+0.01\cdot 0.99}=0.5\).
   
4. Classic: posterior blue often \(\approx 0.41\) with standard numbers — recompute carefully.
   
5. Direct from definition and \(P(A\cap B)=P(A)P(B)\).

---

Common pitfalls

Pitfall	Fix
Swapping \(P(A\mid B)\) and \(P(B\mid A)\)	Write definitions; Bayes to convert
Ignoring base rates	Always include \(P(A)\) in Bayes
Conditioning on probability-zero events	Require \(P(B)>0\)
Assuming independence to multiply	Check or justify
“\(99\%\) accurate” without defining	Expand to sensitivity/specificity/PPV
Forgetting partition completeness	Priors must sum to 1

---

Study notes — conditional essentials

Name	Formula
Conditional	\(P(A\mid B)=P(A\cap B)/P(B)\)
Chain	\(P(A\cap B)=P(A\mid B)P(B)\)
Total prob	\(P(A)=\sum P(A\mid B_i)P(B_i)\)
Bayes	\(P(A\mid B)=P(B\mid A)P(A)/P(B)\)
PPV	\(sp/(sp+f(1-p))\)

Fallacy: do not confuse \(P(+|D)\) with \(P(D|+)\).

Sanity: posteriors over a partition given evidence \(E\) must sum to \(1\).

---

Synthesis — Bayes workout

S1. Definition drill: compute \(P(A\mid B)\) for die events \(A=\{\le 2\}\), \(B=\{\text{even}\}\).

S2. Total probability: two lines \(70\%/30\%\), defect \(1\%/4\%\) — \(P(\text{defect})\).

S3. Bayes on S2: \(P(\text{line 1}\mid\text{defect})\).

S4. Medical: \(p=0.005\), \(s=0.98\), \(f=0.02\) — PPV.

S5. Natural frequency rewrite of S4 with \(10{,}000\) people.

S6. Prove Bayes from chain rule in three lines.

S7. Base-rate fallacy: write a wrong “intuitive” answer then correct it.

S8. CS IDS: attack rate \(10^{-5}\), detection \(0.9\), FPR \(10^{-4}\) — order of PPV.

---

Checkpoint

• Can compute \(P(A\mid B)\) from definition
  
• Can use total probability (partition)
  
• Can apply Bayes with a clear prior
  
• Can explain base-rate fallacy with numbers
  
• Can test independence via conditionals
  
• Exercises A–D done; synthesis attempted

Two personal takeaways:

1. …
   
2. …

---

Deeper theory — Bayes as reweighting priors

Start with prior masses \(P(H_i)\) on a partition. Evidence \(E\) multiplies each hypothesis by its likelihood \(P(E\mid H_i)\) and renormalizes: \[ P(H_j\mid E)=\frac{P(E\mid H_j)P(H_j)}{\sum_i P(E\mid H_i)P(H_i)}. \] No mysticism: this is definition of conditional probability plus total probability in the denominator. The “update” language is interpretation.

Odds form (optional).
\[ \frac{P(H\mid E)}{P(H^c\mid E)}=\frac{P(E\mid H)}{P(E\mid H^c)}\cdot\frac{P(H)}{P(H^c)}. \] Posterior odds \(=\) likelihood ratio \(\times\) prior odds. Useful for quick mental Bayes.

---

Deeper theory — base rates with natural frequencies

Population \(N\)	Diseased \(Np\)	Healthy \(N(1-p)\)
Test \(+\)	\(\approx Nps\) true \(+\)	\(\approx N(1-p)f\) false \(+\)
Test \(-\)	false \(-\)	true \(-\)

PPV \(\approx\) (true \(+\))/(true \(+\) + false \(+\)). Same algebra as Bayes; fewer decimal slips.

---

Worked examples — full Bayes numbers

Example 16 — Cab problem standard numbers.
Prior blue \(15\%\), black \(85\%\). Witness says blue; accuracy \(80\%\) both ways: \(P(\text{says blue}\mid\text{blue})=0.8\), \(P(\text{says blue}\mid\text{black})=0.2\).
\(P(\text{says blue})=0.8\cdot 0.15+0.2\cdot 0.85=0.12+0.17=0.29\).
\(P(\text{blue}\mid\text{says blue})=0.12/0.29\approx 0.414\).

Example 17 — Two-step tree.
Machine \(A\) makes \(70\%\) of parts, defect \(2\%\); machine \(B\) \(30\%\), defect \(5\%\).
\(P(D)=0.014+0.015=0.029\).
\(P(A\mid D)=0.014/0.029=14/29\).
\(P(B\mid D)=15/29\).

Example 18 — Without replacement chain.
Deck: \(P(\text{two aces in two draws})=P(A_1)P(A_2\mid A_1)=\frac{4}{52}\cdot\frac{3}{51}=\frac{12}{2652}=\frac{1}{221}\).

Example 19 — Independence via conditional.
Two dice: \(A=\) first is \(6\), \(B=\) sum is \(7\). \(P(B\mid A)=P(\text{second }=1)=1/6=P(B)\). Independent.
\(A=\) first is \(6\), \(B=\) sum is \(12\): \(P(B\mid A)=P(\text{second }=6)=1/6\), \(P(B)=1/36\) — not independent.

Example 20 — IDS order of magnitude.
Attack rate \(p=10^{-4}\), detection \(s=0.9\), FPR \(f=10^{-3}\).
PPV \(\approx (0.9\cdot 10^{-4})/(0.9\cdot 10^{-4}+10^{-3})\approx 0.00009/0.00109\approx 0.083\) — about \(8\%\) of alerts are real.

---

Extra exercises — Bayes mastery

31. Prevalence \(0.002\), sensitivity \(0.95\), FPR \(0.01\): PPV and natural-frequency version with \(N=10000\).
    
32. Prove the odds form of Bayes for binary \(H\).
    
33. Three hypotheses equal prior, likelihoods of \(E\) are \(0.1,0.2,0.3\) — posteriors?
    
34. Show \(P(A\mid B)+P(A^c\mid B)=1\).
    
35. Medical: compute NPV \(P(D^c\mid -)\) with \(p=0.01\), \(s=0.9\), specificity \(0.95\).
    
36. CS spam: prior \(0.3\), \(P(W|S)=0.5\), \(P(W|H)=0.02\) — \(P(S|W)\).
    
37. Explain in 6 sentences a base-rate failure in hiring tests or security alerts.
    
38. Chain rule for four events (write the formula).

---

Mini-solutions (selected)

31. \(sp=0.0019\), \(f(1-p)\approx 0.01\), PPV \(\approx 0.0019/0.0119\approx 0.16\).
    
32. Unnormalized \(0.1,0.2,0.3\) sum \(0.6\); posteriors \(1/6,1/3,1/2\).
    
33. \(0.5\cdot 0.3/(0.15+0.02\cdot 0.7)=0.15/0.164\approx 0.915\).

---

Closing synthesis card

Name	Role
\(P(A\mid B)\)	renormalize to \(B\)
Total probability	law of alternatives
Bayes	invert likelihoods with priors
PPV	\(P(D\mid +)\) — not sensitivity
Natural frequencies	base-rate guardrail

Never confuse \(P(+|D)\) with \(P(D|+)\).

Tomorrow

Day 87 — Expectation, variance, coupon collector, concentration inequalities.

---

Day 87 — Expectation, variance, indicators, coupon collector, Markov & Chebyshev

Stage VIII · concept day
Goal: Define \(\mathbb{E}[X]\); prove linearity; use indicators; Bernoulli/Binomial/Geometric; variance; coupon collector \(\mathbb{E}[T]=n H_n\); state Markov and Chebyshev.

Why this matters

Expectation turns random processes into deterministic summaries: expected collisions, expected probes, expected trials until success. Linearity works without independence — the most powerful cheap trick in probabilistic method and algorithm analysis. Concentration inequalities (Markov, Chebyshev) bound “bad tail” probabilities.

Note

No labs / no Monte Carlo projects. Exact symbolic/fractional calculations.

---

Theory

Expectation on finite spaces

Definition. If \(X:\Omega\to\mathbb{R}\) and \(\Omega\) is finite, \[ \mathbb{E}[X]=\sum_{\omega\in\Omega} X(\omega)\,P(\{\omega\})=\sum_{x} x\,P(X=x). \]

Intuition. Probability-weighted average of values.

Linearity of expectation

Theorem. For any random variables \(X,Y\) (on the same space) and constants \(a,b\), \[ \mathbb{E}[aX+bY]=a\mathbb{E}[X]+b\mathbb{E}[Y]. \] Extends to any finite sum. No independence required.

Proof. Expand the sum over \(\omega\); rearrange.

Indicator variables

Definition. \(I_A=1\) on \(A\), \(0\) elsewhere. Then \(\mathbb{E}[I_A]=P(A)\).

Method. To count the expected number of “success patterns,” write \(X=\sum_j I_j\) and use linearity: \[ \mathbb{E}[X]=\sum_j P(\text{event }j). \]

Hashing pairs: \(X=\sum_{\text{pairs }\{i,j\}} I_{ij}\) with \(I_{ij}=1\) if \(i,j\) collide ⇒ \(\mathbb{E}[X]=\binom{n}{2}/m\) under uniform independent hashing.

Named distributions

Bernoulli(\(p\)). \(X\in\{0,1\}\), \(P(X=1)=p\). \(\mathbb{E}[X]=p\), \(\mathrm{Var}(X)=p(1-p)\).

Binomial(\(n,p\)). Number of successes in \(n\) independent Bernoulli(\(p\)) trials. \[ P(X=k)=\binom{n}{k}p^k(1-p)^{n-k},\qquad \mathbb{E}[X]=np,\qquad \mathrm{Var}(X)=np(1-p). \] Proof of mean: \(X=\sum_{i=1}^n I_i\), each \(\mathbb{E}[I_i]=p\).

Geometric(\(p\)) (trials until first success). \(P(X=k)=(1-p)^{k-1}p\) for \(k=1,2,\ldots\).
\(\mathbb{E}[X]=1/p\). (Memoryless: remaining wait given no success yet is still geometric.)

Variance

Definition. \[ \mathrm{Var}(X)=\mathbb{E}\bigl[(X-\mathbb{E}[X])^2\bigr]=\mathbb{E}[X^2]-(\mathbb{E}[X])^2. \] Standard deviation \(\sigma=\sqrt{\mathrm{Var}(X)}\).

Properties. \(\mathrm{Var}(aX+b)=a^2\mathrm{Var}(X)\). For independent \(X,Y\), \(\mathrm{Var}(X+Y)=\mathrm{Var}(X)+\mathrm{Var}(Y)\). (Without independence, cross term \(2\mathrm{Cov}\) appears.)

Coupon collector

Problem. \(n\) coupon types, each pack independent uniform. \(T=\) time to collect all \(n\).

Stages. Let \(T_i\) be waiting time to get a new coupon when you already have \(i-1\) distinct. Then \(T_i\sim\mathrm{Geometric}((n-i+1)/n)\) and \(T=\sum_{i=1}^n T_i\).

Expectation. \[ \mathbb{E}[T]=\sum_{i=1}^n \mathbb{E}[T_i]=\sum_{i=1}^n \frac{n}{n-i+1}=n\sum_{k=1}^n \frac{1}{k}=n H_n=\Theta(n\log n). \]

Markov’s inequality (statement)

Theorem (Markov). If \(X\ge 0\) a.s. and \(a>0\), then \[ P(X\ge a)\le \frac{\mathbb{E}[X]}{a}. \]

Proof idea. \(\mathbb{E}[X]\ge \mathbb{E}[X\cdot I_{X\ge a}]\ge a P(X\ge a)\).

Chebyshev’s inequality (statement)

Theorem (Chebyshev). For \(a>0\), \[ P\bigl(|X-\mathbb{E}[X]|\ge a\bigr)\le \frac{\mathrm{Var}(X)}{a^2}. \]

Proof. Apply Markov to \((X-\mathbb{E}[X])^2\ge 0\) with threshold \(a^2\).

Use. If variance is small, \(X\) concentrates around its mean. Weaker than Chernoff bounds but needs only mean and variance.

Optional: second moment method awareness

Bounding \(P(X=0)\) via \(\mathbb{E}[X^2]/(\mathbb{E}[X])^2\) — name only for probabilistic method culture.

---

Worked examples

Example 1 — Die mean.
\(\mathbb{E}[\text{fair die}]=(1+\cdots+6)/6=3.5\).

Example 2 — Linearity without independence.
Two indicators of dependent events: still \(\mathbb{E}[I+J]=P(I=1)+P(J=1)\).

Example 3 — Binomial mean.
\(n=10\), \(p=1/2\): \(\mathbb{E}=5\), \(\mathrm{Var}=2.5\).

Example 4 — Geometric.
\(p=1/6\) (roll a six): expected rolls \(=6\).

Example 5 — Coupon \(n=2\).
\(\mathbb{E}[T]=2(1+1/2)=3\).

Example 6 — Coupon \(n=365\) literacy.
\(\mathbb{E}[T]\approx 365 H_{365}\approx 365\cdot 6.0\approx 2200\) (since \(H_n\approx\ln n+\gamma\)).

Example 7 — Hashing expected collisions.
\(\mathbb{E}[X]=\binom{n}{2}/m\) as indicator sum.

Example 8 — Variance compute.
Bernoulli: \(\mathbb{E}[X^2]=\mathbb{E}[X]=p\) (since \(X^2=X\)), \(\mathrm{Var}=p-p^2\).

Example 9 — Markov.
\(X\ge 0\), \(\mathbb{E}[X]=2\): \(P(X\ge 10)\le 0.2\).

Example 10 — Chebyshev.
\(\mathbb{E}[X]=0\), \(\mathrm{Var}=1\): \(P(|X|\ge 2)\le 1/4\).

Example 11 — Empty bins.
\(n\) balls \(n\) bins independent: \(I_j=\) bin \(j\) empty, \(P=(1-1/n)^n\to e^{-1}\), \(\mathbb{E}[\text{empty}]\to n/e\).

---

Exercises

A. Expectation basics

1. Compute \(\mathbb{E}[X]\) for \(P(X= -1)=P(X=1)=1/2\).
   
2. Prove linearity for \(aX+bY\) from the sum-over-\(\omega\) definition.
   
3. Fair die: \(\mathbb{E}[X^2]\) and \(\mathrm{Var}(X)\).
   
4. If \(X\) is constant \(c\), show \(\mathbb{E}[X]=c\), \(\mathrm{Var}=0\).
   
5. Show \(\mathbb{E}[I_A]=P(A)\).

B. Indicators and named laws

6. Expected number of fixed points of a random permutation of \(n\) elements (indicator per position).
   
7. Expected number of heads in \(n\) fair coins two ways (definition + indicators).
   
8. Binomial: prove \(\mathbb{E}[X]=np\) via indicators.
   
9. Geometric: prove \(\mathbb{E}[X]=1/p\) (hint: condition on first trial or series).
   
10. Expected number of colliding pairs for \(n=50\), \(m=1000\).

C. Coupon collector

11. Derive \(\mathbb{E}[T]=n H_n\) carefully.
    
12. Compute \(\mathbb{E}[T]\) for \(n=5\) exactly as a fraction.
    
13. Show \(\mathbb{E}[T]=\Theta(n\log n)\) using \(H_n=\Theta(\log n)\).
    
14. Expected time to collect the first coupon? The last coupon when \(n-1\) owned?

D. Variance and tails

15. Compute \(\mathrm{Var}(X)\) for fair die.
    
16. For \(X\sim\mathrm{Bin}(n,p)\), state \(\mathrm{Var}\) and use Chebyshev to bound \(P(|X-np|\ge n/2)\) roughly.
    
17. Prove Markov’s inequality.
    
18. Prove Chebyshev from Markov.
    
19. Give an example where Markov is tight (or nearly tight).
    
20. Why does Chebyshev need variance while Markov does not?

E. Stretch

21. Expected number of empty bins with \(m\) bins \(n\) balls.
    
22. Variance of number of fixed points in a random permutation (use indicators + covariances for \(i\neq j\)).
    
23. Show \(\mathbb{E}[X^2]\ge (\mathbb{E}[X])^2\) (nonnegative variance).
    
24. CS: expected probes in ideal chaining search related to \(1+\alpha\) — connect to indicators per bucket length.
    
25. Coupon collector: median is also \(\Theta(n\log n)\) (awareness); why expectation alone doesn’t give high-probability bounds without concentration.

---

Deep dive — indicator method pattern

1. Define X = quantity to understand (count of patterns)
2. Write X = sum_j I_j where I_j indicates pattern j occurs
3. Compute p_j = P(I_j = 1)
4. E[X] = sum_j p_j
5. Optionally: Var via covariances if concentration needed

Classic applications: fixed points of permutations; colliding hash pairs; empty bins; number of runs; edges in random graphs (awareness).

---

Deep dive — Markov/Chebyshev when to use

Inequality	Needs	Gives	Typical use
Markov	\(X\ge 0\), mean	\(P(X\ge a)\le\mathbb{E}[X]/a\)	First crude tail
Chebyshev	mean + variance	deviation from mean	Second-moment tails
Chernoff (awareness)	independent sum structure	exp tails	Advanced algorithms

Markov is weak but universal for nonnegative \(X\). Chebyshev needs \(\mathrm{Var}\) but still polynomial tails only.

---

Additional worked examples

Example 12 — Fixed points.
\(X=\sum_{i=1}^n I_i\), \(P(I_i=1)=1/n\), \(\mathbb{E}[X]=1\) for all \(n\ge 1\).

Example 13 — Binomial variance.
Independent Bernoulli: variances add ⇒ \(np(1-p)\).

Example 14 — Coupon stages.
\(n=4\): \(\mathbb{E}[T]=4(1+1/2+1/3+1/4)=4\cdot 25/12=25/3\approx 8.33\).

Example 15 — Markov on coupon.
\(\mathbb{E}[T]=nH_n\); \(P(T\ge 2nH_n)\le 1/2\).

Example 16 — Chebyshev on \(\mathrm{Bin}(n,1/2)\).
Mean \(n/2\), var \(n/4\): \(P(|X-n/2|\ge\sqrt{n})\le (n/4)/n=1/4\).

Example 17 — Linearity dependence.
Two indicators of same event \(A\): \(\mathbb{E}[I+I]=2P(A)\) even though perfectly dependent.

---

More exercises

26. Expected number of times a fair die shows \(6\) in \(n\) rolls.
    
27. Expected number of empty bins: \(m\) bins, \(n\) balls independent uniform.
    
28. Prove \(\mathrm{Var}(X)=\mathbb{E}[X^2]-(\mathbb{E}[X])^2\) by expanding.
    
29. Geometric: show memoryless \(P(X>s+t\mid X>s)=P(X>t)\).
    
30. Coupon: expected time to get any fixed particular coupon is geometric \(n/(1)\) wait — time to see coupon #\(1\) from start is geometric \(1/n\) mean \(n\).
    
31. Use Chebyshev to bound \(P(|X-\mu|\ge 3\sigma)\).
    
32. CS: expected chain length \(\alpha\) under uniform hashing — indicator sum per bucket.

---

Selected mini-solutions

6. \(\mathbb{E}[\text{fixed points}]=1\).
   
7. \(\binom{50}{2}/1000=1.225\).
   
8. Exact fraction \(nH_n\) with \(H_5=137/60\), etc.
   
9. \(\mathbb{E}[X]\ge aP(X\ge a)\).
   
10. \(m(1-1/m)^n\).

---

Common pitfalls

Pitfall	Fix
Thinking linearity needs independence	It does not
\(\mathbb{E}[XY]=\mathbb{E}[X]\mathbb{E}[Y]\) always	Needs independence (or uncorr.)
Geometric as number of failures vs trials	State convention; mean \(1/p\) for trials
Markov on signed variables	Needs \(X\ge 0\)
Confusing amortized with expectation	Different concepts (Day 83 vs here)
Using Markov for two-sided deviation	Use Chebyshev

---

Study notes — expectation essentials

Object	Mean / note
Linearity	always, no independence
Indicator	\(\mathbb{E}[I]=P\)
Bernoulli(\(p\))	\(p\); var \(p(1-p)\)
Binomial(\(n,p\))	\(np\); var \(np(1-p)\)
Geometric(\(p\)) trials	\(1/p\)
Coupon collector	\(nH_n=\Theta(n\log n)\)
Variance	\(\mathbb{E}[X^2]-(\mathbb{E}[X])^2\)
Markov	\(P(X\ge a)\le\mathbb{E}[X]/a\) (\(X\ge 0\))
Chebyshev	\(P(|X-\mu|\ge a)\le\mathrm{Var}/a^2\)

---

Synthesis — expectation workout

S1. Prove linearity for \(X+Y\) from sum-over-\(\omega\) definition.

S2. Expected fixed points of random permutation of \(n=10\).

S3. \(\mathbb{E}\) and \(\mathrm{Var}\) of \(\mathrm{Bin}(20,1/5)\).

S4. Geometric: expected rolls until double-six on two dice (\(p=1/36\)).

S5. Coupon \(n=6\): exact \(\mathbb{E}[T]=6H_6\) as a fraction.

S6. Hashing pairs: \(\mathbb{E}[X]\) for \(n=30\), \(m=1000\).

S7. Prove Markov; apply to nonnegative \(X\) with mean \(4\), bound \(P(X\ge 20)\).

S8. Chebyshev: \(X\) mean \(0\) var \(9\), bound \(P(|X|\ge 6)\).

---

Checkpoint

• Can define \(\mathbb{E}[X]\) and use linearity
  
• Can run indicator method
  
• Know Bernoulli/Binomial/Geometric means
  
• Can compute variance via \(\mathbb{E}[X^2]-(\mathbb{E}[X])^2\)
  
• Can derive coupon collector \(\mathbb{E}[T]=n H_n\)
  
• Can state Markov and Chebyshev
  
• Exercises A–D done; synthesis attempted

Two personal takeaways:

1. …
   
2. …

---

Deeper theory — linearity without independence (why it works)

\[ \begin{align*} \mathbb{E}[X+Y] &=\sum_{\omega}(X(\omega)+Y(\omega))P(\omega)\\ &=\sum_{\omega}X(\omega)P(\omega)+\sum_{\omega}Y(\omega)P(\omega)\\ &=\mathbb{E}[X]+\mathbb{E}[Y]. \end{align*} \] No step uses \(P(X=x,Y=y)=P(X=x)P(Y=y)\). Dependence can be total; the averages still add. That is why indicator sums analyze collisions, fixed points, and empty bins even when the indicators are dependent.

---

Deeper theory — geometric mean derivation (series)

For \(X\sim\mathrm{Geometric}(p)\) as trials until first success, \[ \mathbb{E}[X]=\sum_{k=1}^\infty k(1-p)^{k-1}p=p\sum_{k=1}^\infty k q^{k-1},\qquad q=1-p. \] Use \(\sum_{k=1}^\infty k q^{k-1}=1/(1-q)^2=1/p^2\) for \(|q|<1\). Thus \(\mathbb{E}[X]=p\cdot 1/p^2=1/p\).

First-step conditioning. With probability \(p\), \(X=1\); with probability \(q\), \(X=1+X'\) where \(X'\sim X\). So \(\mathbb{E}[X]=p\cdot 1+q(1+\mathbb{E}[X])\), solve: \(\mathbb{E}[X]=1/p\).

---

Worked examples — indicator and tails

Example 18 — Fixed points \(n=5\).
\(\mathbb{E}[X]=\sum_{i=1}^5 1/5=1\). Dependence among \(I_i\) does not matter.

Example 19 — Empty bins \(m=n=10\).
\(\mathbb{E}[\text{empty}]=10(1-1/10)^{10}=10\cdot 0.9^{10}\approx 10\cdot 0.3487\approx 3.49\).

Example 20 — Coupon \(n=10\).
\(H_{10}=7381/2520\approx 2.92897\), \(\mathbb{E}[T]=10H_{10}\approx 29.29\).

Example 21 — Markov tightness idea.
\(X=0\) with prob \(1-1/a\), \(X=a\) with prob \(1/a\), mean \(1\): \(P(X\ge a)=1/a=\mathbb{E}[X]/a\) — equality in Markov.

Example 22 — Chebyshev on die mean.
Fair die: \(\mathbb{E}=3.5\), \(\mathbb{E}[X^2]=(1^2+\cdots+6^2)/6=91/6\), \(\mathrm{Var}=91/6-(3.5)^2\approx 2.916\).
\(P(|X-3.5|\ge 2.5)\le 2.916/6.25\approx 0.47\) (true probability is \(P(X\in\{1,6\})=1/3\) — bound not tight).

Example 23 — Binomial Chebyshev.
\(X\sim\mathrm{Bin}(100,1/2)\), mean \(50\), var \(25\). \(P(|X-50|\ge 10)\le 25/100=0.25\).

---

Extra exercises — expectation mastery

33. Prove \(\mathrm{Var}(aX+b)=a^2\mathrm{Var}(X)\).
    
34. Expected number of doubles in \(n\) rolls of two dice.
    
35. Coupon \(n=8\): exact \(\mathbb{E}[T]=8H_8\) as a fraction.
    
36. Indicators: expected number of runs of two heads in \(n\) fair coin flips (overlapping allowed) — set up carefully.
    
37. Markov: \(X\ge 0\), \(\mathbb{E}[X]=5\), bound \(P(X\ge 100)\).
    
38. Chebyshev: mean \(20\), var \(16\), bound \(P(|X-20|\ge 8)\).
    
39. Show \(\mathbb{E}[X^2]\ge(\mathbb{E}[X])^2\) from \(\mathrm{Var}\ge 0\).
    
40. CS: expected probes \(\approx 1+\alpha/2\) story for successful search in chaining — one paragraph connecting to bucket load \(\alpha\).

---

Mini-solutions (selected)

34. Each roll \(P(\text{double})=6/36=1/6\); mean \(n/6\) by indicators.
    
35. \(\le 5/100=0.05\).
    
36. \(\le 16/64=0.25\).
    
37. \(H_8=761/280\), \(\mathbb{E}[T]=8\cdot 761/280=761/35\).

---

Closing synthesis card

Tool	Remember
\(\mathbb{E}[X]\)	weighted average
Linearity	always
Indicators	\(\mathbb{E}[I]=P\)
Coupon	\(nH_n=\Theta(n\log n)\)
Markov	nonnegative tails
Chebyshev	mean + variance

Capstone link: expected modular collisions and inverse-based unique solutions are different tools — expectation for averages, number theory for exact algebra.

Tomorrow

Day 88 — Capstone outline (dossier planning).