11.3. ABSORBING STATES 291

Suppose |λ |= 1. Let vk be the first nonzero entry. Then vk−1 = 0 and so

qvk+1 = λvk

which implies |vk+1| > |vk|. Thus |vk+1| ≥ |vk|. Then consider the next term. From theabove equations and what was just shown,

|vk+1|= |pvk +qvk+1| ≤ p |vk|+q |vk+2| ≤ p |vk+1|+q |vk+2|

and soq |vk+1| ≤ q |vk+2|

Continuing this way, it follows that the sequence{∣∣v j

∣∣}nj=k must be increasing. Specifi-

cally, if{∣∣v j

∣∣}mj=k is increasing for some m > k, then

p |vm−1|+q |vm| ≥ |pvm−2 +qvm|= |λvm−1|= |vm−1|

and so q |vm| ≥ q |vm−1| . Hence |vn| ≥ |vn−1|> 0. However, this is contradicted by the thelast line which states that p |vn−1|= |vn| which requires that |vn−1|> |vn| , a contradiction.Therefore, it must be that |λ |< 1. ■

Now consider the eigenvalues of 11.2. For P given there,

P−λ I =



1−λ q 0 · · · 0

0 −λ. . . 0

0 p. . . q

......

. . . −λ 00 · · · 0 p 1−λ

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

(1−λ )2 det

−λ q

p. . . . . .. . . −λ q

p −λ

 .

The roots of the polynomial after (1−λ )2 have absolute value less than 1 because they arejust the eigenvalues of a matrix of the sort in Lemma 11.3.1. It follows that the conditionsof Theorem 11.1.3 apply and therefore, limn→∞ Pn exists. ■

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

It is interesting to find the probability that the gambler loses all his money. This is givenby limn→∞ pn

0 j.From the transition matrix for the gambler’s ruin problem, it follows that

pn0 j = ∑

kpn−1

0k pk j = qpn−10( j−1)+ ppn−1

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

pn00 = 1, and pn

0b = 0.