南京大学：《随机算法 Randomized Algorithms》课程教学资源（课件讲稿）Chernoff

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 + ￾ ) ￾ µ

A Generalization of Markov's Inequality Theorem: For any X,for h:XR,for any t>0, E[h(X)] Pr[h(X)≥t1≤ t

A Generalization of Markov’s Inequality Theorem: For any X, for h : X ⇥￾ R+, for any t > 0, Pr[h(X) ⇥ t] ￾ E[h(X)] t

Moment Generating Functions Definition(moment generating functions): The moment generating function of X is M(A)=EcAX. Taylor's expansion: A 三营刘

Moment Generating Functions Definition (moment generating functions): The moment generating function of X is M(￾) = E ￾ e￾X ⇥ . E ⌅ e￾X ⇧ = E ￾ ⇤ ￾ k=0 ￾k k! Xk ⇥ = ⇤ ￾ k=0 ￾k k! E ⌅ Xk ⇧ Taylor’s expansion:

independent X1,X2,.,Xn∈{0，l} X=Xi E[X]= 2=1 Pr[X≥(1+)4≤？ for入>0 s preix≥en+Ase Markov eA(1+8)u ●--直 Independence!

X = X n i=1 Xi E[X] = µ independent X1, X2,...,Xn 2 {0, 1} Pr[X ￾ (1 + ￾)µ] ? X ￾ ￾ ￾(1+￾)µ Pr e e ￾ ￾ ￾ E ￾ e⇥X ⇥ e⇥(1+￾)µ Markov for ￾ > 0  = E ⇥ e￾￾n i=1 Xi ⇤ = E ￾ ⇤ n i=1 e￾Xi ⇥ = ￾ n i=1 E ⇥ e￾Xi ⇤ Independence!

independent X1,X2,..,Xm∈{0，l} X=Xi EX= 2=1 Pr[X≥(1+0)4 for入>0 prle1X≥e1+4=gLeD e1(1+o)μ ●=e eP:(e!-1)=e(e-Du ≤】 i= i=1 pi PrXi 1 =∑ i=1 =pe1+(1-p)e0 ≤ePi(e-l)

X = X n i=1 Xi E[X] = µ independent X1, X2,...,Xn 2 {0, 1} Pr[X ￾ (1 + ￾)µ] X ￾ ￾ ￾(1+￾)µ Pr e e ￾ ￾ ￾ E ￾ e⇥X ⇥ e⇥(1+￾)µ for ￾ > 0  = ￾ n i=1 E ⇥ e￾Xi ⇤ pi = Pr[Xi = 1] µ = X n i=1 pi = pi · e￾·1 +(1￾ pi)· e￾·0 ⇥ epi(e￾￾1) ￾ n i=1 epi(e￾￾1) ￾ e(e￾￾1)µ =

independent X1,.X2,.,Xn∈{0，l} X=Xi E[X]= i=1 Pr[X≥(1+o)W for入>0 ●≤ee-1r

X = X n i=1 Xi E[X] = µ independent X1, X2,...,Xn 2 {0, 1} Pr[X ￾ (1 + ￾)µ] X ￾ ￾ ￾(1+￾)µ Pr e e ￾ ￾ ￾ E ￾ e⇥X ⇥ e⇥(1+￾)µ for ￾ > 0  ￾ e(e￾￾1)µ ∑ √ e(e∏°1) e∏(1+±) !µ

independent X1,X2,.,Xn∈{0，l} m X=∑X: E[X]= i=1 入>0 1.3 1.2 1.1 0.9 0.8 0.7 0. 0 0. 1.5 whenλ=ln(1+6)

X = X n i=1 Xi E[X] = µ independent X1, X2,...,Xn 2 {0, 1} Pr[X ￾ (1 + ￾)µ] X ￾ ￾ ￾(1+￾)µ Pr e e ￾ ￾ for ￾ > 0  ∑ √ e(e∏°1) e∏(1+±) !µ when ⇥ = ln(1+￾)