Chernoff Bound Chernoff Bound: For independent X1,,Xn∈{0，l}with X=∑X;andu=E[X] i=1 For any 0<<1, Pr[X≥(1+6)W≤ex (〉 Pr[X≤(1-δ)W川]≤exp Fort≥2eu: Pr[X≥1≤2-tChernoff Bound Chernoff Bound: For independent with and For any , For : X1, …, Xn ∈ {0,1} X = n ∑ i=1 Xi μ = 피[X] 0 < δ < 1 Pr[X ≥ (1 + δ)μ] ≤ exp (−μδ2 3 ) Pr[X ≤ (1 − δ)μ] ≤ exp (−μδ2 2 ) t ≥ 2eμ Pr[X ≥ t] ≤ 2−t