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

Doob Martingale

Doob Martingale f

Doob sequence: Yi=E[f(X1,...,Xn)X1,...,Xi] Doob sequence is a martingale: EY|X1,.,Xi-1]=Y-1 Proof: EYi X1,...,Xi-1] =EE[f(X1,.,Xn)|X1,,X|X1,,Xi-1] =E[f(X1,.,Xn)X1,,Xi-1] =Y-1

Doob sequence: Yi = E[f (X1,...,Xn) | X1,...,Xi] Doob sequence is a martingale: Proof: E[Yi | X1,...,Xi￾1] = E[E[f(X1,...,Xn) | X1,...,Xi] | X1,...,Xi￾1] = E[f(X1,...,Xn) | X1,...,Xi￾1] = Yi￾1 E[Yi | X1,...,Xi￾1] = Yi￾1

G(n,p) Graph parameter: f(G) example:chromatic#, components,diameter .. numbering all vertex-pairs:1,2,3,...,(2) 1 edge j∈G Yi=E[f(G)I1,...,Ii edgejG Yo=Ef(G) -÷Y(g)=f(G

G(n,p) Graph parameter: example: chromatic #, components, diameter ... 1, 2, 3,..., ￾n 2 ⇥ numbering all vertex-pairs: Ij = ￾ 1 edge j ￾ G 0 edge j ⇥￾ G f(G) Yi = E[f(G) | I1,...,Ii] Y0 = E[f(G)] Y( n 2) = f(G)

G(n,p) Graph parameter: f(G) example:chromatic # components,diameter .. numbering all vertices:1,2,3,...,n Xi:subgraph of G induced by the first i vertices Y=E[f(G)|X1,.,X Yo=E[f(G)】…→Yn=f(G)

Graph parameter: example: chromatic #, components, diameter ... numbering all vertices: f(G) 1, 2, 3,...,n Y0 = E[f(G)] Yn = f(G) Yi = E[f(G) | X1,...,Xi] Xi : subgraph of G induced by the first i vertices G(n,p)