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