Chernoff Bound independent X1,X2,...,XnE 10,1} IetX=∑X i=1 t>0: PX≥町N8s即() PrX≤EX]-t≤expX = X n i=1 Xi independent X1, X2,...,Xn 2 {0, 1} Chernoff Bound t > 0 : Pr[X ￾ E[X] + t]  exp ✓ ￾2t 2 n ◆ Pr[X  E[X] ￾ t]  exp ✓ ￾2t 2 n ◆ let