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
Doob Sequence randomized by f0,o, averaged over E f=Yo,Y1,Y2
1 0 f ( , , , , , ) randomized by averaged over Doob Sequence E[f] = Y0, Y1, Y2