Chernoff Bound independent X1,X2,...,XnE {0,1} X=∑X,EX]=u i=1 0<6≤1： Px之+<ae(-"肾） r≤1-洲<即(-） t≥2eu: Pr[X≥t≤2-tX = X n i=1 Xi E[X] = µ independent X1, X2,...,Xn 2 {0, 1} Chernoff Bound Pr[X ￾ (1 + ￾)µ] < exp ✓ ￾µ￾2 3 ◆ Pr[X  (1 ￾ ￾)µ] < exp ✓ ￾µ￾2 2 ◆ Pr[X ￾ t]  2￾t 0 < ￾  1 : t ￾ 2eµ :