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

Chernoff Bound independent X1,X2,...,XnE 10,1} IetX=∑X i=1 t>0: PX≥町N8s即() PrX≤EX]-t≤exp

X = X n i=1 Xi independent X1, X2,...,Xn 2 {0, 1} Chernoff Bound t > 0 : Pr[X ￾ E[X] + t]  exp ✓ ￾2t 2 n ◆ Pr[X  E[X] ￾ t]  exp ✓ ￾2t 2 n ◆ let

The method of bounded differences Independent random variables:X-(X1,X2,...,X). 1,x2..,)satisfies the Lipschitz condition: |jx1,,n）-fx1,,xi1,yi,Xi+1,,xn)|≤Ci for arbitrary possible valuesx1,...,xn,yi. t>0: x>grxyfse( 2t2 Pr[f(X)≤E[f(X)】-t)≤exp

Independent random variables: X=(X1, X2,..., Xn). The method of bounded differences f(x1, x2,..., xn) satisfies the Lipschitz condition: | f(x1, ..., xn) - f(x1,..., xi-1, yi, xi+1, ..., xn) | ≤ ci for arbitrary possible values x1, ..., xn, yi. t > 0 : Pr[f(X)  E[f(X)] ￾ t]  exp ✓ ￾ 2t 2 Pn i=1 c2 i ◆ Pr[f(X) ￾ E[f(X)] + t]  exp ✓ ￾ 2t 2 Pn i=1 c2 i ◆

Martingale Definition: A sequence of random variables Xo,X1,...is a martingale if for all i>0, E[Xi KXo,...,Xi=Xi-1 What does this mean?

E[Xi | X0,...,Xi⇥1] = Xi⇥1 Definition: A sequence of random variables X0,X1,... is a martingale if for all i > 0, Martingale What does this mean?

Azuma's Inequality: Let Xo,X1,...be a martingale such that,for all k =1, IXk-Xk-1≤Ck, Then 12 Pr[lXn-Xol≥t]≤2exp 2∑K=1c呢

Azuma’s Inequality: Let X0,X1,... be a martingale such that, for all k ￾ 1, |Xk ⇥ Xk⇥1| ⇤ ck , Then Pr[|Xn ⇥ X0| ⌅ t] ⇤ 2 exp⇤ ⇥ t 2 2 ⇥n k=1 c2 k ￾

Generalization Definition: Yo,Y1,...is a martingale with respect to Xo,X1,... if,for all i≥0， Yi is a function of Xo,X1,...,Xi; 。E[Yi+1|X0,.,Xi]=Yi

Generalization Definition: Y0,Y1,... is a martingale with respect to X0,X1,... if, for all i ￾ 0, • Yi is a function of X0,X1,...,Xi ; • E[Yi+1 | X0,...,Xi] = Yi

Definition: Yo,Y1,...is a martingale with respect to Xo,X1,... if,for all i≥0， .Yi is a function of Xo,X1,...,Xi; .E[Yi+1 Xo,...,Xi]Yi. Betting on a fair game; Xi:win/loss of the i-th bet; Yi wealth after the i-th bet--Martingale(fair game)

Definition: Y0,Y1,... is a martingale with respect to X0,X1,... if, for all i ￾ 0, • Yi is a function of X0,X1,...,Xi ; • E[Yi+1 | X0,...,Xi] = Yi . • Betting on a fair game; • : win/loss of the i-th bet; • : wealth after the i-th bet -- Martingale (fair game) Xi Yi

Azuma's Inequality (general version): Let Yo,Y1,...be a martingale with respect to Xo,X1,... such that,,for all k≥l, IYk-Yk-1≤Ck, Then Pr[lYn-Yol≥t]≤2exp 2∑1c

Azuma’s Inequality (general version): Then Let Y0,Y1,... be a martingale with respect to X0,X1,... such that, for all k ￾ 1, |Yk ⇥Yk⇥1| ⇤ ck , Pr[|Yn ⇥Y0| ⌅ t] ⇤ 2 exp⇤ ⇥ t 2 2 ⇥n k=1 c2 k ￾

Doob Sequence Definition (Doob sequence): The Doob sequence of a function f with respect to a sequence X1,...,Xn is Yi=E[f(X1,...,Xn)X1,...,Xi] Yo=E[f(X1,.…,Xn)】->Yn=f(X1,.,Xn)

Definition (Doob sequence): Yi = E[f (X1,...,Xn) | X1,...,Xi] The Doob sequence of a function f with respect to a sequence X1,...,Xn is Y0 = E[f (X1,...,Xn)] Yn = f (X1,...,Xn) Doob Sequence

Doob Sequence @, @,@, averaged over E f=Yo

f ( , , , , , ) averaged over Doob Sequence E[f] = ￾ Y0

Doob Sequence randomized by f(①，@， @, averaged over E[f月=Yo,Y

1 f ( , , , , , ) randomized by averaged over Doob Sequence E[f] = ￾ Y0, Y1