Advanced Algorithms Concentration of Measure 尹一通Nanjing University,2022Fall
尹⼀通 Nanjing University, 2022 Fall Advanced Algorithms Concentration of Measure
Measure Concentration Flip a coin for many times: flips-1 flips -5 flips 50 flips -500 fips-500000 0.8 10.8 0.8 0.8 0.8 0.6 0.6 0.6 0.6 0.6 0.4 0.4 0.4 0.4 0.4 0.2 0.2 0.2 0.2 0.2 0 0 0 0 0 0 0 0
• Flip a coin for many times: Measure Concentration
Chernoff-Hoeffding Bounds
Chernoff-Hoeffding Bounds
Chernoff Bound (Bernstein Inequalities) Life in Los Angeles 价 PLOY 《RBAN STRES T RATE MED MED. Herman Chernoff 品 Chernoff face
Chernoff Bound (Bernstein Inequalities) Herman Chernoff Chernoff face
Chernoff Bound Chernoff Bound: For independent X,,Xn∈{0，l}with X=∑X,andu=E[X灯 i=1 For anyδ>0， e1os(可) For any 0<<1, Hirs0-(a-苏可》
Chernoff Bound Chernoff Bound: For independent with and For any , For any , X1, …, Xn ∈ {0,1} X = n ∑ i=1 Xi μ = 피[X] δ > 0 Pr[X ≥ (1 + δ)μ] ≤ ( eδ (1 + δ)(1+δ) ) μ 0 < δ < 1 Pr[X ≤ (1 − δ)μ] ≤ ( e−δ (1 − δ)(1−δ) ) μ