Simple random walk - Uppsala University

1 Simple random walkSven Erick Alm9 April 2002(revised 8 March 2006)(translated to English 28 March 2006)Contents1 Introduction22 The monkey at the Passage probabilities .. Passage times .. 53 The gambler s Absorption probabilities .. Absorption times .. Reflecting barriers .. 104 Counting Mirroring .. The Ballot problem .. Recurrence .. Maximum .. The Arcsine law .. 205 Mixed problems236 Literature2411 IntroductionArandom walkis a stochastic sequence{Sn}, withS0= 0, defined bySn=n k=1Xk,where{Xk}are independent and identically distributed random variables ( ).The random walk issimpleifXk= 1, withP(Xk= 1) =pandP(Xk= 1) = 1 p=q. Imagine a particle performing a random walk on the integer points of the real line, where itin each step moves to one of its neighboring points; see Figure 1: Simple random walkRemark can also study random walks in higher dimensions.

2 In two dimensions, eachpoint has 4 neighbors and in three dimensions there are 6 Simple random walk issymmetricif the particle has the same probability for each of random walks are treated in Chapter 7 in Ross book. Here we will only studysimple random walks, mainly in one are interested in answering the following questions: What is the probability that the particle will ever reach the pointa?(The casea= 1is often called The monkey at the cliff .) What time does it take to reacha? What is the probability of reachinga >0before b <0? ( The gambler s ruin ) If the particle afternsteps is ata >0, what is the probability that it has been on the positive side since the first step? it has never been on the negative side?( The Ballot problem ) How far away from 0 will the particle get innsteps?When analyzing random walks, one can use a number of general methods, such as conditioning, generating functions, difference equations,2 the theory for Markov chains, the theory for branching processes, martingales,but also some more specialized, such as counting paths, mirroring, time The monkey at the cliffA monkey is standing one step from the edge of a cliff and takes repeated independent steps;forward, with probabilityp, or backward, with Passage probabilitiesWhat is the probability that the monkey, sooner or later, will fall off the cliff?

3 Call this probabilityP1. ThenP1=P(a random walk particle will ever reachx= 1).We can also study, fork >0,Pk=P(a random walk particle will ever reachx=k),corresponding to the monkey startingksteps from the independence (and the strong Markov property) we getPk= determineP1, condition on the first 1 +q P2=p+q P21,so thatP21 1qP1+pq= 0,with solutions12q 14q2 pq=12q 1 that1 =p+q= (p+q)2=p2+q2+ 2pq,so that1 4pq=p2+q2 2pq= (p q)2and thus 1 4pq=|p q|.3 The solutions can thus be written1 (p q)2q={1,pq.(1)Ifp > qthe solutionpq>1is rejected, so that, forp q( 1/2), we getP1= 1, andthusPk= 1fork is somewhat more difficult to see that forp < qthe correct solution isP1=p/q <1,which givesPk= (p/q) can be shown using generating functions, by using the theory for branching pro-cesses, where the extinction probability is the smallest positive root to the equationg(s) =s;see Problem more direct way is to studyPk(n) =P(to reachx=kin thenfirst steps).}

4 Again conditioning on the first step givesP1(n) =p+q P2(n 1) p+q P21(n 1).SinceP1(1) =p p/q, we can, by induction, show thatP1(n) p/qfor alln 1, if we canshow thatP1(n) p/qimplies that alsoP1(n+ 1) thatP1(n) p/q. ThenP1(n+ 1) p+q P21(n) p+q (p/q)2=p+p2q= limn P1(n) pq,we can, forp < q, reject the solutionP1= have thus provedTheorem as above, fork 1,Pk={1ifp q,(pq)kifp < implies that a symmetric random walk , with probability 1, will visitallpointson the line!Problem < q. Determine the distribution ofY= maxn 0Sn. ComputeE(Y).Hint: StudyP(Y a).Problem < q. Show thatP1is the extinction probability of a branching process withreproduction distributionp0=p,p2= Passage timesWhat time does it take until the monkey falls over the edge?LetTjk= the time it takes to go fromx=jtox=k , so thatT0k= the time it takes the particle to reachx=kfor the first time (when starting inx= 0) ,and further letEk=E(T0k),if the expectation exists.}

5 If it doeas, we must have, fork >0,Ek=k givesE1= 1 +p 0 +q E2= 1 + 2q the casesp < q,p=qandp > < qwe have, by Theorem 1, thatP(T01= ) = 1 P1>0, which implies thatE1= + .Forp=q= 1/2we get, ifE1is supposed to be finite, thatE1= 1 +E1,that is a contradiction, so that also in this caseE1= + .Finally, forp > q, we getE1=11 2q=1p q< .We have provedTheorem 1,Ek={+ ifp q,kp qifp > Theorems 1 and 2 we can also study returns to the starting point. LetP0=P(that the particle ever returns to the starting point),T00= the time until the first return ,E0=E(T00).Theorem + for allpandP0={1ifp=q,1 |p q|ifp6= :With notation as before, we get by conditioning thatP0=p P 1+q , by Theorem 1, we getP 1=P1= 1, so that alsoP0= 1. Ifp6=q, eitherP 1<1orP1<1, so thatP0< the casep < q,P 1= 1andP1=p/q, so thatP0=p+q pq= 2p= 1 (q p)< the casep > q, insteadP 1=q/pandP1= 1, so thatP0=p qp+q= 2q= 1 (p q)< , we thus haveP0= 1 |p q|<1and consequentlyP(T00= )>0, so thatE0= +.}}

6 Ifp=qwe getE0= 1 +12E 1+12E1= + ,by Theorem symmetric random walk will therefore, with probability 1, return to 0. Thisholds after each return, so thatP(Sn= ) = the walk will return infinitely often, the expected time between returns is infinite! Thelaw of large numbers can therefore not be interpreted as saying that the particle usually is closeto 0. In fact, the particle is rarely close to 0 and a large proportion of the time is spent far awayfrom 0, even in a symmetric random walk ! See Section can be shown that the symmetric random walk in two dimensions also returns tothe origin with probability 1, while in three dimensions the probability is Determine the distribution forY=# returns to 0. ComputeE(Y).3 The gambler s ruinThe monkey at the cliffcan be interpreted as placing an absorbing barrier atx= 1(orx=k).By studying a random walk with two absorbing barriers, one on each side of the staring point,we can solveThe Gambler s ruin:Two players, A and B, play a game with independent rounds where, in each round, oneof the players wins 1 krona from his opponent; A with probabilitypand B with probabilityq= 1 p.

7 A starts the game withakronor and B withbkronor. The game ends when one ofthe players is Absorption probabilitiesWhat are the player s ruin probabilities?This corresponds to a random walk where the particle starts at 0 and is absorbed in the statesband a, or, equivalently, starts inaand is absorbed in 0 anda+ (A wins when he haskkronor).Then,A0= 0,Aa+b= 1and we seekAa. Condition on the outcome of the first round!Ak=p Ak+1+q Ak 1.(2)This homogeneous difference equation can be solved by determining the zeroes of the charac-teristic polynomialz=p z2+q z2 1p z+qp= 0,6with solutionsz1= 1andz2=q/p. (Compare with (1).) This gives, forp6=q, the followinggeneral solution to (2)Ak=C1 1k+C2 (qp)k,where the constantsC1andC2are determined by the boundary conditionsA0= 0 C1+C2= 0,Aa+b= 1 C1+C2(qp)a+b= 1,so thatC1= 1(qp)a+b 1,C2=1(qp)a+b 1,andAk= 1(qp)a+b 1+1(qp)a+b 1(qp)k=(qp)k 1(qp)a+b 1,Aa=(qp)a 1(qp)a+b , we get the difference equationAk=12Ak+1+12Ak characteristic polynomialz2 2z+ 1has the double rootz1=z2= 1, so that we needone more , so thatAk=C1 1k+C2 0 C1= 0,Aa+b= 1 C2=1a+b,so thatAk=ka+b,Aa=aa+ we have shownTheorem probability that A ruins B (the particle is absorbed inx=b) isAa= (qp)a 1(qp)a+b 1ifp6=12,aa+bifp= + ,b= 1corresponds toThe monkey at the (the monkey falls over the edge) =lima P(A wins).

8 Forp=qwe getP1= lima aa+ 1= 1and forp6=qP1= lima (qp)a 1(qp)a+1 1={1ifp > q,pqifp < a symmetric random walk on the points0,1, .. , n, on the circumferenceof a circle; see Figure 2. The random walk starts at 0. It is easily seen that, with probability 1,all points will be visited.(Why?)What is the probability that the pointk(k= 1, .. , n) is the last to be visited?Beforekis visited one ofk 1andk+ 1must be visited. Consider the time point when thishappens for the first time. Because of symmetry, we can assume that it isk 1that is the last point visited means thatk+ 1must be visited beforekand this can only occurif the random walk passes clockwise fromk 1tok+ 1before it visitsk. The probability forthis is the same as the ruin probability for a player withn 1kronor against an opponent with1 krona, We then have shown the surprising result thatP(kis the last point visited) =1nfork= 1.}

9 , 1kk+1 Figure 2: random walk on a circleExample a symmetric random walk starting at 0 and a positiona > # visits inabefore the random walk returns to 0 . Forato be visited at all, the firststep must be to the right, so thatP(Ya>0) =12 P(Ya>0|S1= 1). This conditionalprobability is the chance to win for a player with 1 krona against an opponent witha 1kronor, (Ya>0|S1= 1) =1a, so thatP(Ya>0) =12a. Similarly, we can computeP(Ya= 1|Ya>0). Consider the random walk whenais visited, which we know will happenifYa>0. For this to be the last visit ina, before the next visit to 0, the first step must be to theleft, so thatP(Ya= 1|Ya>0) =12 P(0 is reached beforeastarting ina 1) =12 1a= same situation appears at every visit ina, so that(Ya|Ya>0)is ffg(1/2a) (Geometricdistribution starting at 1) andP(Ya>0) = 1/2a. This givesE(Ya) =12a 2a= 1for alla >0! (Due to symmetry, this also holds for negativea.)

10 Above we have shown something very surprising:Between two visits to 0, the symmetric random walk will make on average 1 visit toallotherpoints!For this to be possible, we must haveE0= , which also was shown in Theorem Theorem 1 to prove that, for allp,aandb, the game will finish with that you have 10 kronor and your opponent has 100 kronor. You get thechoice to play with stakes of 1, 2, 5 or 10 kronor per round. How would you choose, and whatare your chances of winning, if your probability to win a single round isa)p= , b)p= , c)p= Absorption timesHow long will it take before someone is ruined?LetYk= # remaining rounds when A haskkronor ,Ek=E(Yk).Conditioning givesEk= 1 +p Ek+1+q Ek 1,(3)withE0=Ea+b= (3) is a non-homogeneous difference equation. To solve this we need both to solvethe corresponding homogeneous equation, as above, and also to find a particular solution to theinhomogeneous start with the symmetric case (p=q= 1/2).