1 Gambler’s Ruin Problem - Columbia University

1 1 gambler s ruin ProblemConsider a gambler who starts with an initial fortune of $1 and then on each successive gambleeither wins $1 or loses $1 independent of the past with probabilitiespandq= 1 the total fortune after thenthgamble. The gambler s objective is to reach a totalfortune of $N, without first gettingruined(running out of money). If the gambler succeeds,then the gambler is said towinthe game. In any case, the gambler stops playing after winningor getting ruined, whichever happens first. There is nothing special about starting with $1,more generally the gambler starts with $iwhere 0< i < the game proceeds,{Rn:n 0}forms a simple random walkRn= 1+ + n, R0=i,where{ n}forms an sequence of distributed asP( = 1) =p, P( = 1) =q=1 p, and represents the earnings on the succesive the game stops when eitherRn= 0 orRn=N, let i= min{n 0 :Rn {0, N}|R0=i},denote the time at which the game stops whenR0=i.

2 IfR i=N, then the gambler wins, ifR i= 0, then the gambler is (R i=N) denote the probability that the gambler wins whenR0=i. ClearlyP0= 0 andPN= 1 by definition, and we next proceed to computePi,1 i N key idea is to condition on the outcome of the first gamble, 1= 1 or 1= 1, yieldingPi=pPi+1+qPi 1.(1)The derivation of this recursion is as follows: If 1= 1, then the gambler s total fortuneincreases toR1=i+1 and so by the Markov property the gambler will now win with probabilityPi+1. Similarly, if 1= 1, then the gambler s fortune decreases toR1=i 1 and soby the Markov property the gambler will now win with probabilityPi 1.

3 The probabilitiescorresponding to the two outcomes arepandqyielding (1). Sincep+q= 1, (1) can bere-written aspPi+qPi=pPi+1+qPi 1, yieldingPi+1 Pi=qp(Pi Pi 1).In particular,P2 P1= (q/p)(P1 P0) = (q/p)P1(sinceP0= 0), so thatP3 P2= (q/p)(P2 P1) = (q/p)2P1,and more generallyPi+1 Pi= (qp)iP1,0< i < +1 P1=i k=1(Pk+1 Pk)=i k=1(qp)kP1,1yieldingPi+1=P1+P1i k=1(qp)k=P1i k=0(qp)k= P11 (qp)i+11 (qp),ifp6=q;P1(i+ 1),ifp=q= (2)(Here we are using the geometric series equation in=0ai=1 ai+11 a,for any numberaandany integeri 1.)

4 Choosingi=N 1 and using the fact thatPN= 1 yields1 =PN= P11 (qp)N1 (qp),ifp6=q;P1N,ifp=q= ,from which we conclude thatP1= 1 qp1 (qp)N,ifp6=q;1N,ifp=q= ,thus obtaining from (2) (after algebra) the solutionPi= 1 (qp)i1 (qp)N,ifp6=q;iN,ifp=q= (3)(Note that 1 Piis the probability of ruin .) Becoming infinitely rich or getting ruinedIfp > , thenqp<1 and thus from (3)limN Pi= 1 (qp)i>0, p > (4)Ifp , thenqp 1 and thus from (3)limN Pi= 0, p (5)To interpret the meaning of (4) and (5), suppose that the gambler starting withX0=iwishes to continue gambling forever until (if at all) ruined, with the intention of earning asmuch money as possible.

5 So there is no winning valueN; the gambler will only stop if will happen?(4) says that ifp > (each gamble is in his favor), then there is a positive probabilitythat the gambler will never get ruined but instead will become infinitely rich.(5) says that ifp (each gamble is not in his favor), then with probability one thegambler will get John starts with $2, andp= : What is the probability that John obtains a fortune ofN= 4 without going broke?SOLUTIONi= 2,N= 4 andq= 1 p= , soq/p= 2/3, and we wantP2=1 (2/3)21 (2/3)4= What is the probability that John will become infinitely rich?

6 SOLUTION1 (q/p)i= 1 (2/3)2= 5/9 = If John instead started withi= $1, what is the probability that he would go broke?SOLUTIONThe probability he becomes infinitely rich is 1 (q/p)i= 1 (q/p) = 1/3, so the probabilityof ruin is 2 ApplicationsRisk insurance businessConsider an insurance company that earns $1 per day (from interest), but on each day, indepen-dent of the past, might suffer aclaimagainst it for the amount $2 with probabilityq= 1 such a claim is suffered, $2 is removed from the reserve of money.

7 Thus on thenthday, the net income for that day is exactly nas in the gamblers ruin Problem : 1 withprobabilityp, 1 with the insurance company starts off initially with a reserve of$i 1, then what is theprobability it will eventually get ruined (run out of money)?The answer is given by (4) and (5): Ifp > then the probability is given by (qp)i>0,whereas ifp ruin will always ocurr. This makes intuitive sense because ifp > , thenthe average net income per day isE( ) =p q >0, whereas ifp , then the average netincome per day isE( ) =p q 0.

8 So the company can not expect to stay in business unlessearning (on average) more than is taken away by Random walk hitting probabilitiesLeta >0 andb >0 be integers, and letRndenote a simple random walk withR0= 0. Letp(a) =P(Rnhits levelabefore hitting level b).By lettinga=N iandb=i(so thatN=a+b), we can imagine a gambler who startswithi=band wishes to reachN=a+bbefore going broke. So we can computep(a) by castingthe Problem into the framework of the gamblers ruin Problem :p(a) =PiwhereN=a+b,i=b. Thus3p(a) = 1 (qp)b1 (qp)a+b,ifp6=q;ba+b,ifp=q= (6)Examples1.

9 Ellen bought a share of stock for $10, and it is believed that the stock price moves (dayby day) as a simple random walk withp= What is the probability that Ellen sstock reaches the high value of $15 before the low value of $5?SOLUTIONWe want the probability that the stock goes up by 5 before going down by 5. This isequivalent to starting the random walk at 0 witha= 5 andb= 5, and computingp(a).p(a) =1 (qp)b1 (qp)a+b=1 ( )51 ( )10= What is the probability that Ellen will become infinitely rich?SOLUTIONHere we keepi= 10 in the gambler s ruin Problem and letN in the formula forP10as in (4);limN P10= 1 (q/p)10= 1 (.)

10 82)10= Markov chain approachWhen we restrict the random walk to remain within the set of states{0,1, .. , N},{Rn}yieldsa Markov chain (MC) on the state spaceS={0,1, .. , N}. The transition probabilities aregiven byP(Rn+1=i+1|Rn=i) =pi,i+i=p, P(Rn+1=i 1|Rn=i) =pi,i i=q,0< i < N,and both 0 andNare absorbing states,p00=pNN= example, whenN= 4 the transition matrix is given byP= 1 0 0 0 0q0p0 00q0p00 0q0p0 0 0 0 1 .Thus the gambler s ruin Problem can be viewed as a special case of afirst passage timeproblem: Compute the probability that a Markov chain, initially in statei, hits are three communication classes:C1={0},C2={1.}