Geometric distribution Geometric X: indicators: Pr[X==(1-p)k-1p the first k trials fail brutal force: Pr[Yk=1]=(1-p) E[X]=∑kPr[X= k=1 O∞ ●X● X=∑Y =∑k(1-p)-1p k=0 k=1 ∞ EX]=〉EY linearity of 1 k=0 expectation p ●X● geometric =∑1-p)k= p k=0
Geometric X: X = k=0 Yk Yk = 1 the first k trials fail 0 otherwise Pr[Yk = 1] = (1 p) k brutal force: indicators: E[X] = k=1 k Pr[X = k] = k=1 k(1 p) k1p ··· ··· = 1 p Geometric distribution E[X] = k=0 E[Yk] = k=0 (1 p) k = 1 p Pr[X = k] = (1 p) k1p linearity of expectation geometric
Balls and Bins m balls ○○○○○○ uniformly independently L444↓I n bins birthday problem,coupon collector problem, occupancy problem
Balls and Bins m balls n bins uniformly & independently birthday problem, coupon collector problem, occupancy problem,