10.3. ABSORBING STATES 269

and so, expanding the determinant of the matrix along the first column and then along thelast column yields

(1− λ)2det

−λ q

p. . .

. . .

. . . −λ q

p −λ

 .

The roots of the polynomial after (1− λ)2have absolute value less than 1 because they are

just the eigenvalues of a matrix of the sort in Lemma 10.3.1. It follows that the conditionsof Theorem 10.1.3 apply and therefore, limn→∞ Pn exists. ■

Of course, the above transition matrix, models many other kinds of problems. It is calleda Markov process with two absorbing states, sometimes a random walk with two absorbingstates.

It is interesting to find the probability that the gambler loses all his money. This is givenby limn→∞ pn0j .From the transition matrix for the gambler’s ruin problem, it follows that

pn0j =∑k

pn−10k pkj = qpn−1

0(j−1) + ppn−10(j+1)for j ∈ [1, b− 1] ,

pn00 = 1, and pn0b = 0.

Assume here that p ̸= q. Now it was shown above that limn→∞ pn0j exists. Denote by Pj

this limit. Then the above becomes much simpler if written as

Pj = qPj−1 + pPj+1 for j ∈ [1, b− 1] , (10.3)

P0 = 1 and Pb = 0. (10.4)

It is only required to find a solution to the above difference equation with boundary con-ditions. To do this, look for a solution in the form Pj = rjand use the difference equationwith boundary conditions to find the correct values of r. Thus you need

rj = qrj−1 + prj+1

and so to find r you need to have pr2 − r + q = 0, and so the solutions for r are r =

1

2p

(1 +

√1− 4pq

),

1

2p

(1−

√1− 4pq

)Now √

1− 4pq =√1− 4p (1− p) =

√1− 4p+ 4p2 = 1− 2p.

Thus the two values of r simplify to

1

2p(1 + 1− 2p) =

q

p,

1

2p(1− (1− 2p)) = 1

Therefore, for any choice of Ci, i = 1, 2,

C1 + C2

(q

p

)j

will solve the difference equation. Now choose C1, C2 to satisfy the boundary conditions10.4. Thus you need to have

C1 + C2 = 1, C1 + C2

(q

p

)b

= 0