Martingale Theory Problem set 3, with solutions …

1 MartingaleTheoryProblemset3,withsolution sMartingalesThesolutionsofproblems1,2,3, 4,5,6, j,j= 1,2,..b ( i= +1)=p,P( i= 1)=q:= 1 p,andFn= ( j,0 j n),n 0,theirnatural := nj=1 j,n 0.(a)ProvethatMn:= (q/p)Snisan(Fn)n 0- Martingale .(b)For >0determineC=C( )sothatZ n:=Cn Snb ean(Fn)n :(a)E(Mn+1 Fn)=E(Mn(q/p) n+1 Fn)=MnE((q/p) n+1 Fn)=MnE((q/p) n+1)=Mn(p(q/p) +q(p/q)) =Mn.(b)C=C( ) =(E( )) 1= p+ 'sRuin,1 Agamblerwinsorlo osesonep oundineachroundofb etting,withequalchancesandindep ettingwiththe rmdeterminationthatshewillstopgamblingwh eneithershewonap oundsorshelostbp ounds.(a)Whatistheprobabilitythatshewill b (b)Whatistheexp ectednumb erofherb ettingroundsb :Mo deltheexp j,j= 1,2,..b ( i= +1)=12=P( i= 1),andFn= ( j,0 j n),n 0,theirnatural 0, Sn:=n j=1 j, n nethestoppingtimesTL:= inf{n >0 :Sn= b}, TR:= inf{n >0 :Sn= +a}, T:= min{TL,TR}.Notethat{thegamblerwinsap ounds}={T=TR},{thegamblerlo osesbp ounds}={T=TL}.

2 (a)BytheOptionalStoppingTheoremE(ST)=E(S 0)= bP(T=TL)+aP(T=Tr)= ,P(T=TL)+P(T=Tr)= (T=TL)=aa+b,P(T=TR)=ba+b.(b)Firstproveth atMn:=S2n nisyetanothermartingale:E(Mn+1 Fn)=E(S2n+1 Fn) (n+ 1)=E(S2n+ 2Sn n+1+ 1 Fn) (n+ 1) = = ,applytheOptionalStoppingTheorem0 =E(MT)=E(S2T T)=P(T=TL)b2+P(T=TR)a2 E(T).Hence,usingtheresultfrom(a)E(T)= 'sRuin,2 Answerthesamequestionsasinproblem2whenth eprobabilityofwinningorlo osingonep oundineachroundisp,resp ectively,q:= 1 p,withp (0,1).Hint:Usethemartingalesconstructedi nproblem1 SOLUTION:Mo deltheexp j,j=1,2,..b ( i= +1)=p,P( i= 1)=q,andFn= ( j,0 j n),n 0,theirnatural 0, Sn:=n j=1 j, n nethestoppingtimesTL:= inf{n >0 :Sn= b}, TR:= inf{n >0 :Sn= +a}, T:= min{TL,TR}.Notethat{thegamblerwinsap ounds}={T=TR},{thegamblerlo osesbp ounds}={T=TL}.(a)UsetheOptionalStoppingT heoremforthemartingale(q/p)Sn:1 =E((q/p)Sn)= (p/q)bP(T=TL)+ (q/p)aP(T=TR).Ontheotherhand,P(T=TL)+P(T =Tr)= (T=TL)=1 (q/p)a(p/q)b (q/p)a,P(T=TR)=1 (p/q)b(q/p)a (p/q)b.

3 (b)Now,applytheOptionalStoppingTheoremto themartingaleSn (p q) (T)= (p q) 1E(ST)= (p q) 1(a1 (p/q)b(q/p)a (p/q)b b1 (q/p)a(p/q)b (q/p)a)= (p q) 1a(1 (p/q)b) +b(1 (q/p)a)(q/p)a (p/q) j,j= 1,2,3,..,b eindep endentandidenticallydistributedrandomvar iablesandFn:= ( j,0 j n),n 0,thenatural Rtheexp onentialmomentm( ) :=E(e j)< := 0,Sn:= nj=1 j,n cessMn:=m( ) nexp{ Sn}, n N,isan(Fn)n :Verymuchthesameasproblem1(b). ( ,F,(Fn)n 0,P)b ea lteredprobabilityspaceandYn,n 0,asequenceofabsolutelyintegrablerandomvariablesadaptedtothe ltration(Fn)n ersun,vn,n 0,suchthatE(Yn+1 Fn)=unYn+ ,n 0,sothatthesequenceofrandomvariablesMn:=anYn+bn,n >1,b :WritedownthemartingaleconditionforMn:E( Mn+1 Fn)=E(an+1Yn+1+bn+1 Fn)=an+1unYn+an+1vn+bn+1=anYn+ +1=anu 1n, bn+1=bn an+ 1,an=(n 1 k=0uk) 1,b0= 0,bn= n k=1akvk (inwhateverway)andp erformthefollowingdiscretetimepro oseoneoftheballsuniformlyatrandom(thatis :eachballischosenwithprobability1/N)andp laceitinoneoftheurnsalsouniformlychosena trandom(thatis:eachurnischosenwithprobab ility1/K).

4 DenotebyXnthenumb er4ofballsinthe rsturnattimenandletFn:= (Xj,1 j n),n 0,b ethenatural ltrationgeneratedbythepro cessn7 Xn.(a)ComputeE(Xn+1 Fn).(b)Usingtheresultfromproblem5, ndrealnumb ersan,bn,n 0,suchthatZn:=anXn+bnb emartingalewithresp ecttothe ltration(Fn)n :(a)E(Xn+1 Fn)= (Xn+ 1)N XnN1K+ (Xn 1)XnNK 1K+Xn(N XnNK 1K+XnN1K)=XnN 1N+1K.(b)Applytheresultfromproblem5withu n=N 1N, vn= ,j 1,b eabsolutelyintegrablerandomvariablesandF n:= (Xj,,1 j n),n 0,theirnatural nethenewrandomvariablesZ0:= 0, Zn:=n 1 j=0(Xj+1 E(Xj+1 Fj)).Provethatthepro cessn7 Znisan(Fn)n (0,1),andTAIL=0withprobability1 .Thevalue [0,1]andn Nwede nepn,t:{0,1}n [0,1]bypn,t(x1,..,xn) :=t nj=1xj(1 t)n nj= othesesab outthep ossiblevalueof :either =a,or =b,wherea,b [0,1]anda6= eatedlyandformthesequenceofrandomvariabl esZn:=pn,a( 1,.., n)pn,b( 1,.., n),where j,j= 1,2,..,aretheresultsofthesuccessivetrial s(HEAD=1,TAIL=0).Provethatthepro cessn7 Znisamartingale(withresp ecttothenatural ltrationgeneratedbythecointosses)ifandon lyifthetruebiasofthecoinis = lman'sOptimalityPrincipleWemo j,j= 1,2.

5 ,b eindep endentrandomvariableswiththefollowingide nticaldistribution;P( j= +1)=p,P( j= 1)= 1 p:=q,1/2< p < :=plog2p+qlog2q+ 2,theentropyofthedistributionof j. jisthereturnofunitb >0andherfortuneafterroundnisYn=Yn 1+Cn nwhereCnistheamountsheb endonthevaluesof 1,.., n 1,and0 Cn Yn ectedrateofwinningswithinnroundsis:rn:=E (log2(Yn/Y0)).Thegambler'sgoalistomaximi zernwithina xednumb erofrounds.(a)Provethatnomatterwhatstrat egythegamblercho oses(thatis:nomatterhowshecho osesCn=Cn( 1,.., n 1) [0,Yn 1])Xn:= log2Yn n isasupermartingaleandhenceitfollowsthatr n n .Thismeansthatshewillnotb eabletomakeheraveragewinningrate,overany numb erofrounds,largerthan .(b)However,thereexistsagamblingstrategy whichmakesXnde nedab :determinetheoptimalchoiceofCn=Cn( 1,.., n). nb eahomogeneousMarkovchainonthecountablest atespaceS:={0,1,2,..}andFn:= ( j,0 j n),n 0,itsnatural SdenotebyQ(i)theprobabilitythattheMarkov chainstartingfromsiteieverreachesthep oint0 S:Q(i) :=P( n < : n= 0 0=i).

6 6 ProvethatZn:=Q( n)isan(Fn)n n,k,n= 1,2,..,k= 1,2,..b eindep endentandidenticallydistributedrandomvar iableswhichtakevaluesfromN={0,1,2,..}.As sumethattheyhave nitesecondmomentanddenote :=E( n,k), 2:=Var( n,k).De netheGalton-Watsonbranchingpro cessZ0:= 1, Zn+1:=Zn k=1 n+1,kandletGn:= (Zj: 0 j n),n 0,b eitsnatural ltration.(a)ProvethatMn:= nZn, n= 0,1,2,..isa(Gn)n 0- Martingale .(b)ProvethatE(Z2n+1 Gn)= 2Z2n+ 2Zn.(c)Usingtheresultfrom(b)provethatNn: = M2n 2 n+1 n 1 1 Mnif 6= 1,M2n n 2 Mnif = 1isalsoa(Gn)n 0- Martingale .(d)Usingtheresultfrom(c)pro vethatif >1thensup0 n< E(M2n)< (thatis:themartingaleMnisuniformlyb oundedinL2)whileif 1thenlimn E(M2n)= .SOLUTION:(a)E(Mn+1 Fn)= (n+1)E(Zn k=1 n+1,k Gn)= (n+1)Zn k=1E( n+1,k Gn)= (n+1)Zn =Mn.(b)Z2n+1Gn=Zn k=1Zn l=1E( n+1,k n+1,l Gn)=Zn( 2+ 2) + (Z2n Zn) 2=Z2n 2+Zn (c)Considerthecase 6= (M2n+1 2 n+2 n+1 1 1Mn+1 Gn)= 2(n+1)E(Z2n+1 Gn) 2 n+2 n+1 1 1E(Mn+1 Gn)= 2(n+1)(Z2n 2+Zn 2) 2 n+2 n+1 1 1Mn=.

7 =M2n 2 n+1 n 1 = (Nn)= 1,andhenceE(M2n)= 1 + 2 n+1 n 1 oundedif > lyaUrn,1 Attimen= 0,anurncontainsB0= 1blue,andR0= ,2,3,..,aballischosenatrandomfromtheurna ndreturnedtotheurn, erofblue,resp ectively,redballsintheurnafterthen-thtur nofthispro cedure.(NotethatBn+Rn=n+ 2.)DenotebyFn:= (Bj,0 j n) = (Rj,0 j n),n 0,thenatural ltrationofthepro :=BnBn+Rnb etheprop ortionofblueballsintheurnjustaftertimen. (a)Showthatn7 Mn,isan(Fn)n 0- Martingale .(b)ShowthatP(Bn=k)= 1/(n+ 2)for0 k n+ 1.(Hint:Writedowntheprobabilityofcho osingkblueandn kredballsinwhatever xedorder.)(c)Wewillproveso onthatM := ?(Hint:Whatisthelimitofthedistributionof Mn(identi edinthepreviousp oint)asn ?)(d)(Tob edoneafterlearningab outtheOptionalStoppingTheorem.)LetTb ethenumb erofballsdrawnuntilthe (1T+2)= 1 lyaUrn,2 Writeaprogramco detosimulatetheP 1blueandR0= 1redballintheurn,p erform1000stepsandrecordtheprop eatthisexp eriment2000timesanddeterminethedistribut ionofthe nalprop ortionofblueballsbyp lyaUrn,3 WecontinuethestudyofP [0,1]b e xedandde neNn( ) :=(Bn+Rn 1)!

8 (Bn 1)!(Rn 1)! Bn 1(1 )Rn ( )isisan(Fn)n (HEAD)= ,P(TAIL)= 1 ,where UNI[0,1]isarandomvariablewhichisuniforml ydistributedin[0,1].Wetossthiscoinmanyti mesanddenoteB0= 1,Bn:= 1 + rstntrials,R0= 1,Rn:= 1 + rstntrials,andFn:= (Bj,0 j n),n 0,thenatural ltrationgeneratedbythesequenceofcointoss es.(Notethe+1-sandthatBn+Rn=n+ 2.)(a)Provethatforanyn N,thejointdistributionof(B0,B1,..,Bn)ist hesameasthatofthesequencedenotedthesamew ayintheP lyaUrn,problem12.(b)ProvethatMn:=BnBn+Rn ,9(withBn,Rnde nedinthisproblem)isanan(Fn)n 0- Martingale .(c)ProvethatNn( ) :=(Bn+Rn 1)!(Bn 1)!(Rn 1)! Bn 1(1 )Rn 1.(withBn,Rnde nedinthisproblem)isexactlythe(regular)co nditionaldensityfunctionoftherandomvaria ble.