Stopping Time 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,,X]=Yi. ∀t,E[Y=E[Yo] (martingale) E[Yi]=E[E[Y Xo;...,X:-1]]=E[Yi-1] for random T:EYT=EYo?
Stopping Time 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 . 8t, E[Yt] = E[Y0] E[Yt] = E[E[Yt | X0,...,Xt1]] = E[Yt1] (martingale) for random T: E[YT ] = E[Y0]?
Stopping Time for random T:EYT=Yo? counterexamples: martingale betting strategy(doubling bet whenever lose):let T be the first time of winning flipping a fair coin:let T be the first time that #HEADs -#TAILs =5
Stopping Time for random T: E[YT ] = E[Y0]? counterexamples: • martingale betting strategy (doubling bet whenever lose): let T be the first time of winning • flipping a fair coin: let T be the first time that #HEADs - #TAILs =5
Stopping Time for what random stopping rule: EYT=EYo]? Stopping time: a nonnegative integer-valued random variable T is a stopping time for Xo,X1,X2,..if:Pr[T<o]=1 and Vt≥0，the event“T=t'depends only on Xo,.Xi,,X, example:“T is the first time that” not a stopping time:“T is the last time that.” for what kind of stopping time T we have EYT=EYo]?
Stopping Time for what random stopping rule: E[YT ] = E[Y0]? Stopping time: a nonnegative integer-valued random variable T is a stopping time for X0, X1, X2, ... if: Pr[T < ∞]=1 and ∀t ≥0, the event “T = t” depends only on X0, X1, ..., Xt • example: “T is the first time that ....” • not a stopping time: “T is the last time that ...” for what kind of stopping time T we have E[YT ] = E[Y0]?
Optional Stopping Time Optional Stopping Time(OST)theorem: (Martingale stopping time theorem) Yo,Y1,Y2,..is a martingale w.r.t.Xo,X1,X2,... Tis a stopping time for Xo,X1,X2,... EYT]=EYo] if both following conditions are satisfied: 1.EYT<oo (avoid trading huge loss with small prob. small gain with large prob.) 2. lim [YT0(contributions of largeto Yr are small) indicator
Optional Stopping Time Optional Stopping Time (OST) theorem: (Martingale stopping time theorem) Y0, Y1, Y2, ... is a martingale w.r.t. X0, X1, X2, ... T is a stopping time for X0, X1, X2, ... E[ |YT | ] t] ]=0 E[YT ] = E[Y0] if both following conditions are satisfied: 1. 2. (avoid trading huge loss with small prob. / small gain with large prob.) (contributions of large t to E[YT] are small) indicator
OST:practical version Optional Stopping Time (OST)theorem: (Martingale stopping time theorem) Yo,Y1,Y2,..is a martingale w.r.t.Xo,X1,X2,.. Tis a stopping time for Xo,X1,X2,... EYT=E[Yo] if one of the followings is satisfied: l.T≤t for a finitet (bounded time) 2.Y<c for some finite c for all t (bounded range) 3.E[T]<co and E[lY+1-Yil I Xo,...,Xi]s c for some c (finite time bounded difference
OST: practical version 1. T ≤ t for a finite t 2. |Yt| ≤ c for some finite c for all t 3. E[T]< ∞ and E[|Yt+1-Yt| | X0,..., Xt] ≤ c for some c Optional Stopping Time (OST) theorem: (Martingale stopping time theorem) Y0, Y1, Y2, ... is a martingale w.r.t. X0, X1, X2, ... T is a stopping time for X0, X1, X2, ... E[YT ] = E[Y0] if one of the followings is satisfied: (bounded time) (bounded range) (finite time + bounded difference )
Wald's Equation Wald's Equation: Xo,X1,X2,..are i.i.d.random variables Tis a stopping time for Xo,X1,X2,.. ET],E[X(X:-E[X:)+E[X:-E[X]o...,X-1] 2=1 =Yi-1+EX:-E X=Yi-1
Wald’s Equation Wald’s Equation: X0, X1, X2, ... are i.i.d. random variables T is a stopping time for X0, X1, X2, ... E[T], E[Xi] < 1 E " X T i=1 Xi # = E[T] · E[Xi] Yt = X t i=1 (Xi E[Xi]) E[Yt | X0,...,Xt1] = X t1 i=1 (Xi E[Xi]) + E[Xt E[Xt] | X0,...,Xt1] = Yt1 + E[Xt E[Xt]] = Yt1 let is a martingale w.r.t. X0, X1, X2,
OST:practical version Optional Stopping Time (OST)theorem: (Martingale stopping time theorem) Yo,Y1,Y2,..is a martingale w.r.t.Xo,X1,X2,.. Tis a stopping time for Xo,X1,X2,... EYT=E[Yo] if one of the followings is satisfied: l.T≤t for a finitet (bounded time) 2.Y<c for some finite c for all t (bounded range) 3.E[T]<co and E[lY+1-Yil I Xo,...,Xi]s c for some c (finite time bounded difference
OST: practical version 1. T ≤ t for a finite t 2. |Yt| ≤ c for some finite c for all t 3. E[T]< ∞ and E[|Yt+1-Yt| | X0,..., Xt] ≤ c for some c Optional Stopping Time (OST) theorem: (Martingale stopping time theorem) Y0, Y1, Y2, ... is a martingale w.r.t. X0, X1, X2, ... T is a stopping time for X0, X1, X2, ... E[YT ] = E[Y0] if one of the followings is satisfied: (bounded time) (bounded range) (finite time + bounded difference )
Wald's Equation Wald's Equation: Xo,X1,X2,..are i.i.d.random variables Tis a stopping time for Xo,X1,X2,.. T E[T],E[Xi]<o E =ET]·E[X] Y=(X:-E[X:])is a martingale w.r.t.Xo,X1,X2,.. 2=1 E[Yi-Yi-1 X1,...,X]=E[X:-E[X]]<2E[X]<o o)0=p店-店]=2x-EmEx刘
Wald’s Equation Wald’s Equation: X0, X1, X2, ... are i.i.d. random variables T is a stopping time for X0, X1, X2, ... E[T], E[Xi] < 1 E " X T i=1 Xi # = E[T] · E[Xi] Yt = X t i=1 (Xi E[Xi]) is a martingale w.r.t. X0, X1, X2, ... E[|Yt Yt1| | X1,...,Xt1] = E[|Xt E[Xt]|] 2E[Xt] < 1 0 = E[YT ] = E " X T i=1 Xi # E " X T i=1 E[Xi] # = E " X T i=1 Xi # E [T] E[Xi OST ]
Waiting time for patterns flipping a fair coin uniform and independent X1,X2,.∈{0，l} a pattern:x∈{0，l}k substring:X i,j=XiX+1.X stopping time T:first time encountering x as a substring ET=? characteristic function: 1x[1,]=x[k-j+1, otherwise x=1001 x=1010 x=0000 1001 X1=1 1010 X1=0 0000 X1=1 1001 X2=0 1010 X2=1 0000 X2=1 1001 3=0 1010 X3=0 0000 X3=1 1001X4=1 1010 X4=1 0000 X4=1
Waiting time for patterns flipping a fair coin uniform and independent X1, X2, ... ∈ {0,1} a pattern: x ∈ {0,1}k stopping time T: first time encountering x as a substring E[T] =? substring: X[i, j] = XiXi+1 ··· Xj j = ( 1 x[1, j] = x[k j + 1, k] 0 otherwise characteristic function: x = 1 0 0 1 1 0 0 1 χ1 = 1 1 0 0 1 χ2 = 0 1 0 0 1 χ3 = 0 1 0 0 1 χ4 = 1 x = 1 0 1 0 1 0 1 0 χ1 = 0 1 0 1 0 χ2 = 1 1 0 1 0 χ3 = 0 1 0 1 0 χ4 = 1 x = 0 0 0 0 0 0 0 0 χ1 = 1 0 0 0 0 χ2 = 1 0 0 0 0 χ3 = 1 0 0 0 0 χ4 = 1
uniform and independent X1,X2,.∈{0，l} a pattern:x∈{0，l}k substring:X[i,j]=XX:+1.Xj stopping time T:first time encountering x as a substring characteristic function: 七、 11,=x[k-j+1,网 otherwise x=1001 x=1010 x=0000 1001 X1=1 1010 X1=0 0000 X1=1 1001 X2=0 1010 X2=1 0000 X2=1 1001 X3=0 1010 X3=0 0000 X3=1 1001 X4=1 1010 X4=1 0000 X4=1 k Theorem: E[T]=xj2 j=1
uniform and independent X1, X2, ... ∈ {0,1} a pattern: x ∈ {0,1}k stopping time T: first time encountering x as a substring substring: X[i, j] = XiXi+1 ··· Xj j = ( 1 x[1, j] = x[k j + 1, k] 0 otherwise characteristic function: x = 1 0 0 1 1 0 0 1 χ1 = 1 1 0 0 1 χ2 = 0 1 0 0 1 χ3 = 0 1 0 0 1 χ4 = 1 x = 1 0 1 0 1 0 1 0 χ1 = 0 1 0 1 0 χ2 = 1 1 0 1 0 χ3 = 0 1 0 1 0 χ4 = 1 x = 0 0 0 0 0 0 0 0 χ1 = 1 0 0 0 0 χ2 = 1 0 0 0 0 χ3 = 1 0 0 0 0 χ4 = 1 E[T] = X k j=1 j2 Theorem: j