1 Gambler’s Ruin Problem

1 Copyrightc 2009 by Karl Sigman1 Gambler s Ruin ProblemLetN 2 be an integer and let 1 i N 1. Consider a gambler who starts with aninitial fortune of $iand then on each successive gamble either wins $1 or loses $1 independentof the past with probabilitiespandq= 1 prespectively. LetXndenote the total fortuneafter thenthgamble. The gambler s objective is to reach a total fortune of $N, without firstgettingruined(running out of money). If the gambler succeeds, then the gambler is said towinthe game. In any case, the gambler stops playing after winning or getting ruined, whicheverhappens first.{Xn}yields a Markov chain (MC) on the state spaceS={0,1,..,N}. The transitionprobabilities are given byPi,i+1=p, Pi,i 1=q,0< i < N, and both 0 andNare absorbingstates,P00=PNN= example, whenN= 4 the transition matrix is given byP= 1 0 0 0 0q0p0 00q0p00 0q0p0 0 0 0 1.

2 While the game proceeds, this MC forms a simple random walkXn=i+ 1+ + n, n 1, X0=i,where{ n}forms an sequence of distributed asP( = 1) =p, P( = 1) =q=1 p, and represents the earnings on the successive the game stops when eitherXn= 0 orXn=N, let i= min{n 0 :Xn {0,N}|X0=i},denote the time at which the game stops whenX0=i. IfX i=N, then the gambler wins, ifX i= 0, then the gambler is (N) =P(X i=N) denote the probability that the gambler wins whenX0= (N)denotes the probability that the gambler, starting initially with$i, reaches atotal fortune ofNbefore ruin;1 Pi(N)is thus the corresponding probably of ruinClearlyP0(N) = 0 andPN(N) = 1 by definition, and we next proceed to computePi(N),1 i N (Gambler s Ruin Problem )Pi(N) = 1 (qp)i1 (qp)N,ifp6=q;iN,ifp=q= (1)1 There are three communication classes:C1={0}, C2={1.}

3 , N 1}, C3={N}.C1andC3are recurrentwhereasC2is :For our derivation, we letPi=Pi(N), that is, we suppress the dependence onNforease of notation. The key idea is to condition on the outcome of the first gamble, 1= 1 or 1= 1, yieldingPi=pPi+1+qPi 1.(2)The derivation of this recursion is as follows: If 1= 1, then the gambler s total fortuneincreases toX1=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 toX1=i 1 and soby the Markov property the gambler will now win with probabilityPi 1. The probabilitiescorresponding to the two outcomes arepandqyielding (2). Sincep+q= 1, (2) can bere-written aspPi+qPi=pPi+1+qPi 1, yieldingPi+1 Pi=qp(Pi Pi 1).

4 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,yieldingPi+1=P1+P1i k=1(qp)k=P1i k=0(qp)k= P11 (qp)i+11 (qp),ifp6=q;P1(i+ 1),ifp=q= (3)(Here we are using the geometric series equation in=0ai=1 ai+11 a,for any numberaandany integeri 1.)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= ,2thus obtaining from (3) (after algebra) the solutionPi= 1 (qp)i1 (qp)N,ifp6=q;iN,ifp=q= (4) infinitely rich or getting ruinedIn the formula (1), it is of interest to see what happens asN ; denote this byPi( ) =limN Pi(N).

5 This limiting quantity denotes the probability that the gambler , if allowedto play forever unless ruined, will in fact never get ruined and instead will obtain an infinitelylarge ( ) = limN Pi(N). Ifp > , thenPi( ) = 1 (qp)i>0.(5)Ifp , thenPi( ) = 0.(6)Thus, unless the gambles are strictly better than fair (p > ), ruin is :Ifp > , thenqp<1; hence in the denominator of (1), (qp)N 0 yielding the < , thenqp>1; hence in the the denominator of (1), (qp)N yielding the , ifp= , thenpi(N) =i/N 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(4) =1 (2/3)21 (2/3)4= What is the probability that John will become infinitely rich?

6 SOLUTIONP2( ) = 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 isP1( ) = 1 (q/p) = 1/3, so the probabilityof ruin is 1 P1( ) = 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. 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)?

7 The answer is given by (5) and (??): 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. 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 letRn= 1+ + n, n 1, R0= 0 denote a simplerandom walk initially at the origin. Letp(a) =P({Rn}hits levelabefore hitting level b).By lettingi=b, andN=a+b, we can equivalently imagine a gambler who starts withi=band wishes to reachN=a+bbefore going broke.

8 So we can computep(a) by castingthe Problem into the framework of the gambler s ruin Problem :p(a) =Pi(N) whereN=a+b,i=b. Thusp(a) = 1 (qp)b1 (qp)a+b,ifp6=q;ba+b,ifp=q= (7)Examples1. 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?SOLUTION4 Here we equivalently want to know the probability that a gambler starting withi= 10becomes infinitely rich before going broke.

9 Just like Example 2 on Page 3:1 (q/p)i= 1 ( )10 1 = Maximums and minimums of the simple random walkFormula (7) can immediately be used for computing the probability that the simple randomwalk{Rn}, starting initially atR0= 0, will ever hit levela, for any given positive integera 1: Keepafixed while taking the limit asb in (7). The result depends on wetherp < orp A little thought reveals that we can state this Problem as computing thetailP(M a), a 0,whereMdef= max{Rn:n 0}is the all-time maximum of the randomwalk; a non-negative random variable, because{M a}={Rn=a,for somen 1}.Proposition max{Rn:n 0}for the simple random walk starting initially atthe origin (R0= 0).1. Whenp < ,P(M a) = (p/q)a, a 0;Mhas a geometric distribution with success probability1 (p/q):P(M=k) = (p/q)k(1 (p/q)), k this case, the random walk drifts down to , wp1, but before doing so reaches thefinite Ifp , thenP(M a) = 1, a 0:P(M= ) = 1; the random walk will, withprobability 1, reach any positive integerano matter how :Taking the limit in (7) asb yields the result by considering the two casesp < : Ifp < , then (q/p)>1 and so both (q/p)band (q/p)a+btend to asb.

10 But before taking the limit, multiply both numerator and denominator by (q/p) b= (p/q)b,yieldingp(a) =(p/q)b 1(p/q)b (q/p) (p/q)b 0 asb , the result > , then (q/p)<1 and so both (q/p)band (q/p)a+btend to 0 asb yielding thelimit in (7) as 1. Ifp= , thenp(a) =b/(b+a) 1 asb .Ifp < , thenE( )<0, and ifp > , thenE( )>0; so Proposition is consistentwith the fact that any random walk withE( )<0 (called thenegative driftcase) satisfieslimn Rn= , wp1, and any random walk withE( )>0 ( called thepositive driftcase)satisfies limn Rn= + , furthermore we learn that whenp < , although wp1 the chain drifts off to , itfirst reaches a finite maximumMbefore doing so, and this rvMhas a geometric the strong law of large numbers, limn Rnn=E( ),wp1, soRn nE( ) ifE( )<0 and + ifE( )> Proposition also offers us a proof that whenp= , thesymmetriccase, therandom walk will wp1 hit any positive value,P(M a) = symmetry, we also obtain analogous results for the minimum, :Corollary min{Rn.}