Chernoff bound: For independent trials X1,X2,...,XnE(0,1} Let X=>2 Xi,and u=E[X]. For any 6 >0, Pr[X≥(1+6)W≤ PrX≤I-oW aChernof bound: Pr[X ⇥ (1+￾)µ] ￾ ⇥ e￾ (1+￾)(1+￾) ￾µ Pr[X ⇥ (1￾￾)µ] ⇥ ⇥ e￾￾ (1￾￾)(1￾￾) ￾µ For any ￾ > 0, For independent trials X1,X2,...,Xn 2 {0, 1}. Let X = Pn i=1 Xi , and µ = E[X]