Chernoff Bounds Life in Los Angeles ORBAN STRES RATE LOW MED Herman Chernoff
Chernoff Bounds Herman Chernoff
Concentration Flip a coin for many times: flips -1 flips-5 flips-50 flips -500 fips=500000 0.8 0.8 0.8 0.8 0.8 0.6 0.6 0.6 0.6 0.6 0.4 0.4 04 0.4 0.4 0.2 0.2 0.2 0.2 02 0 1 1 1 0 0
Concentration Flip a coin for many times:
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 a
Chernof 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]
Chernoff Bounds 0.8 0.6 Pr[X≥1+6川≤ 0.4 0.2 0 0.5 1 1.5 6
Chernoff Bounds Pr[ X ⇥ (1 + ) µ ] ⇥ e (1 + )(1 + ) µ
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-t
X = 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] 2t 0 < 1 : t 2eµ :