Random walk with absorbing states 131 After n = 10000 steps with p = 0.6, E(X„) = 2000 an
Pr{1808<*10000 <2192}^0.95, whereas when p = 0.5 the mean is 0 and
Pr { - 196 < *100oo < 196} ~ 0.95.
Figure 7.3 shows the growth of the mean with increasing n and the approximating normal densities at n = 50 and n = 100 for various p.
7.3 RANDOM WALK WITH ABSORBING STATES
The paths of the process considered in the previous section increase or decrease at random, indefinitely. In many important applications this is not the case as particular values have special significance. This is illustrated in the following classical example.
A simple gambling game
Let two gamblers, A and B, initially have $a and $b, respectively, where a and b are positive integers. Suppose that at each round of their game, player A wins $1 from B with probability p and loses $1 to B with probability q=l—p. The total capital of the two players at all times is
c = a + b.
Let X„ be player A's capital at round n where n = 0,1,2,... and X0 = a. Let Z„ be the amount A wins on trial n. The Z„ are assumed to be independent. It is clear that as long as both players have money left,
X„ = Xn-1+Zn, n=l,2,
where the Z„ are i.i.d. as in the previous section. Thus {X„, n = 0,1,2,...} is a simple random walk but there are now some restrictions or boundary conditions on the values it takes.
Absorbing states
Let us assume that A and B play until one of them has no money left; i.e., has 'gone broke'. This may occur in two ways. A's capital may reach zero or A's capital may reach c, in which case B has gone broke. The process X = {X0, Xu X2,...} is thus restricted to the set of integers {0,1,2,.... c} and it terminates when either the value 0 or c is attained. The values 0 and c are called absorbing states, or we say there are absorbing barriers at 0 and c. Figure 7.4 shows plots of /Ts capital X„ versus trial number for two possible
132 Simple random walks
B broke
c ■-
Figure 7.4 Two sample paths of a simple random walk with absorbing barriers at 0 and c. The upper path results in absorption at c (corresponding to player A winning all the money) and the lower one in absorption at 0 (player A broke).
games. One of these sample paths leads to absorption of X at 0 and the other to absorption at c.
7.4 THE PROBABILITIES OF ABSORPTION AT 0
Let Pa, a = 0,1,2,..., c denote the probabilities that player A goes broke when his initial capital is $a. Equivalently Pa is the probability that X is absorbed at 0 when X0 = a. The calculation of Pa is referred to as a gambler's ruin problem. We will obtain a difference equation for Pa.
First, however, we observe that the following boundary conditions must apply:
Pc = 0
since if a = 0 the probability of absorption at 0 is one whereas if a = c, absorption at c has already occurred and absorption at 0 is impossible.
Now, when a is not equal to either 0 or c, all games can be divided into two mutually exclusive categories:
Probabilities of absorption at 0 133
(i) A wins the first round;
(ii) A loses the first round.
Thus the event {A goes broke from a} is the union of two mutually exclusive events:
{A goes broke from a} =
{A wins the first round and goes broke from a + 1} u {A loses the first round and goes broke from a —I}. (7.6)
Also, since going broke after winning the first round and winning the first round are independent,
Pr {A wins the first round and goes broke from a 4-1} = Pr {-4 wins the first round} Pr {A goes broke from a + 1} = PP.+ V (7-7) Similarly,
Pr {A loses the first round and goes broke from a — 1}
= qP.-i- (7.8)
Since the probability of the union of two mutually exclusive events is the sum of their individual probabilities, we obtain from (7.6)-(7.8), the key relation
Pa = pPa+1 + qPa-1
fl = l,2,...,c-l. (7.9)
This is a difference equation for Pa which we will solve subject to the above boundary conditions.
Solution of the difference equation (7.9) There are three main steps in solving (7.9).
(i) The first step is to rearrange the equation Since p + q = 1, we have
(p + q)Pa = pPa+1+qPa-1,
or
P(Pa+i-Pa) = q(Pa-Pa-i)-Dividing by p and letting
r = * P
gives
Pa+i-Pa = r(Pa-Pa-l).
134 Simple random walks (ii) The second step is to find Pt
To do this we write out the system of equations and utilize the boundary condition P0 = 1:
a=l : P2-Px =r(P1-P0) =^1-1) a = 2 : P3-P2 =r(P2-Pl) = r2(Pt-l)
a = c - 2: Pc_, - Pc_2 = r(Pc_2 - Pc_3) = f-\P, - 1) a = c-l: Pc-Pc-, =r(Pc_1-Pc_2) = r£-1(P1-l)
Adding all these and cancelling gives
Pe-Pi = -P1=(P1-lX'1 + r2+---+^-1), where we have used the fact that Pc = 0.
(7.10)
(7.11)
Special case: p — q.= \ If p = q = i then r = 1 so r + r2 H-----hr0 1 = c — 1.
Hence
-P1=(P1-lXc-l).
Solving this gives
r = l.
(7.12)
General case: p^q Equation (7.11) can be rearranged to give (P1-l)(l+r + r2 + ---+rc-1)+l=0
so
P = 1___L_.
1 1 + r + r2 + ••• + rc-1'
For r#l we utilize the following formula for the sum of a finite number of terms of a geometric series:
l-rc
1 + r + r2 + ••■ + rc 1 = Hence, after a little algebra,
1-r
(7.13)
Pi =
l-re
(7.14)
Equations (7.12) and (7.14) give the probabilities that the random walk is
Probabilities of absorption at 0 135
absorbed at zero when X0 = 1, or the chances that player A goes broke when starting with one unit of capital.
(iii) The third and final step is to solve for Pa, a ^ 1. From the system of equations (7.10) we get
P3 = P2 + r2{P, - 1) = P, + (P, - lXr + r2) Pa=Pa_1+ra-\P1-l) = pi + (P1-l)(r + r2 + -+ra-1).
Adding and subtracting one gives
Pa = (Pi ~ 1X1 + r + r2 + ... + r"-1) + 1.
(7.15)
Special case: p = q = 2 When r = 1 we have 1 + r + r2 + —h r" 1 = a, so using (7.12) gives
p = q.
(7.16)
General case: p^q From (7.14) we find
r-1
1
Substituting this in (7.15) and utilizing (7.13) for the sum of the geometric series,
which rearranges to
r#l.
Thus, in terms of p and q we finally obtain the following results.
Theorem 7.1 The probability that the random walk is absorbed at 0 when it starts at XQ = a, (or the chances that player A goes broke from a) is
1 - (q/pY
p±q-
(7.17)
Table 7.1 Values of Pa for various values of p.
a p = 0.25 p = 0.4 p = 0.5
0 1 1 1
1 0.99997 0.99118 0.9
2 0.99986 0.97794 0.8
3 0.99956 0.95809 0.7
4 0.99865 0.92831 0.6
5 0.99590 0.88364 0.5
6 0.98767 0.81663 0.4
7 0.96298 0.71612 0.3
8 0.88890 0.56536 0.2
9 0.66667 0.33922 0.1
10 0 0 0
5 a -*■ 10
Figure 7.5 The probabilities Pa that player A goes broke. The total capital of both players is 10, a is the initial capital of A, and p = chance that A wins each round.
Absorption at c>0 137
When p = q = £,
Some numerical values
Table 7.1 lists values of Pa for c = 10, a = 0,1,..., 10 for the three values p = 0.25, p = 0.4 and p = 0.5. The values of Pa are plotted against a in Fig. 7.5. Also shown are curves for p = 0.75 and p = 0.6 which are obtained from the relation (see Exercise 8)
Pa(P)=l-Pc-a(l-p).
In the case shown where p = 0.25, the chances are close to one that X will be absorbed at 0 (A will go broke) unless X0 is 8 or more. Clearly the chances that A does not go broke are promoted by:
(i) a large p value, i.e. a high probability of winning each round;
(ii) a large value of X0, i.e. a large share of the initial capital.
7.5 ABSORPTION AT c> 0
We have just considered the random Walk {X„,n = 0,1,2,...} where Xn was player A's fortune at epoch n. Let Yn be player fl's fortune at epoch n. Then { Y„, n = 0,1,2,...} is a random walk with probability q of a step up and p of a step down at each time unit. Also, Y0 = c — a and if Y is absorbed at 0 then X is absorbed at c. The quantity
Qa = Pr {X is absorbed at c when X0 = a},
can therefore be obtained from the formulas for Pa by replacing a by c — a and interchanging p and q.
Special case: p = q = % In this case Pa = 1 — ajc so Qa = 1 - (c — a)/c. Hence
p = g.
General case: p^q From (7.17) we obtain
(p/ go in expressions (7.16) and (7.17) for Pa. There are three cases to consider.
(0 P>q
Then player A has the advantage and since q/pl.
How long will absorption take? 139
Note that even when A and B have equal chances to win each round, player A goes broke for sure when player B has infinite initial capital. In casinos the situation is approximately that of a gambler playing someone with infinite capital, and, to make matters worse p < q so the gambler goes broke with probability one if he keeps on playing. Casino owners are not usually referred to as gamblers!
7.7 HOW LONG WILL ABSORPTION TAKE?
In Section 7.5 we saw that the random walk lona finite interval is certain to be absorbed at 0 or c. We now ask how long this will take. Define the random variable
Ta = time to absorption of X when X0 = a, a = 0,1,2,..., c.
The probability distribution of Ta can be found exactly (see for example Feller, 1968, Chapter 14) but we will find only the expected value of Ta:
Da = E{Ta).
Clearly, if a = 0 or a = c, then absorption is immediate so we have the boundary conditions
(7.19)
(7.20)
X
1
a a
Figure 7.6 Paths leading to absorption after k steps.
0„ = O £»c = 0
140 Simple random walks We will derive a difference equation for Da. Define
P(a,k) = Pi{Ta = k},k = l,2,...
which is the probability that absorption takes k time units when the process begins at a. Considering the possible results of the first round as before (see the sketch in Fig. 7.6), we find
P(a, k) = pP(a + 1, k - 1) + qP(a -l,k- 1).
Multiplying by k and summing over k gives
OO 00 00
E(Ta)= X kP(a,k) = p X kP(a + l,k-l) + q £ kP(a-l,k-l). Putting ; = k — 1 this may be rewritten
Da = Ptu+ ^)P(a + U + q t U + ma~ U)
j=0 j=0
oo oo
= PYJjP(a + lJ) + qZjP(a-l,j)
j=o j=0
+ pfjP(a + l,j) + qfjP(a-l,j).
j=0 j=0
But we have seen that absorption is certain, so
f P(a+l,j)=ZP{a-l,j)=l.
7=0 j=0
Hence
Da = pDa + 1 + qDa_1 + p + q
Table 7.2 Values of Da from (7.22) and (7.23) with c= 10
a p = 0.25 p = 0.4 p = 0.5
0 0 0 0
1 1.999 4.559 9
2 3.997 8.897 16
3 5.991 12.904 21
4 7.973 16.415 24
5 9.918 19.182 25
6 11.753 20.832 24
7 13.260 20.806 21
8 13.778 18.268 16
9 11.334 11.961 9
10 0 0 0
or, finally,
How long will absorption take? 141 ~Da = pDa+l+qDa.l + l L a=l,2,...,c-l. (7.21)
This is the desired difference equation for Da, which can be written down without the preceding steps (see Exercise 11).
The solution of (7.21) may be found in the same way that we solved the difference equation for Pa. In Exercise 12 it is found that the solution satisfying the boundary conditions (7.19), (7.20) is
Da = a(c - a)
p = q,
q-p
l-(q/pf l-(q/pf.
p^q-
(7.22)
(7.23)
Numerical values
Table 7.2 lists calculated expected times to absorption for various values of a when c = 10 and for p = 0.25, p = 0.4 and p = 0.5. These values are plotted as functions of a in Fig. 7.7.
a
p = 0.5
--1
/ /p = 0.4 V«
/ ./ = 0.25
■----~v\
0 ^
j-1-1 i_i_
5 10 a
Figure 7.7 The expected times to absorption, Da, of the simple random walk starting at a when c = 10 for various p.