MIT
38
Analysis
lLet Xi=1 if ith red item chosen, else 0
lThen X= å Xi
lChernoff Bound
applies
»Pr[deviation by e] <
exp(-e2pc/ 4)
»< 1/n if pc > 4(log n)/e2
lPretty tight
»if
pc < 1, likely no red samples
»so no meaningful
estimate