Day 87 — Expectation, variance, coupon collector

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).