290 CHAPTER 11. LIMITS OF VECTORS AND MATRICES

denoted by b. The Gambler starts with an amount j > 0 and gambles till he either loseseverything or gains everything. He does this by playing a game in which he wins withprobability p and loses with probability q. When he wins, the amount of money he hasincreases by 1 and when he loses, the amount of money he has decreases by 1. Thus thestates are the integers from 0 to b. Let pi j denote the probability that the gambler has i atthe end of a game given that he had j at the beginning. Let pn

i j denote the probability thatthe gambler has i after n games given that he had j initially. Thus

pn+1i j = ∑

kpik pn

k j,

and so pni j is the i jth entry of Pn where P is the transition matrix. The above description

indicates that this transition probability matrix is of the form

P =



1 q 0 0 · · · 00 0 q 0

0 p 0. . .

......

. . . . . . q 00 p 0 00 0 · · · 0 p 1

(11.2)

The absorbing states are 0 and b. In the first, the gambler has lost everything and hencehas nothing else to gamble, so the process stops. In the second, he has won everything andthere is nothing else to gain, so again the process stops.

Consider the eigenvalues of this matrix which is a piece of the above transition matrix.

Lemma 11.3.1 Let p,q > 0 and p+q = 1. Then the eigenvalues of

A≡

0 q 0

p 0. . .

. . .. . . q

0 p 0

have absolute value less than 1.

Proof: By Gerschgorin’s theorem, (See Page 139.) if λ is an eigenvalue, then |λ | ≤ 1.Alternatively, you note that ∑i Ai j ≤ 1. If λ is an eigenvalue of A then it is also one for AT

and if ATx= λx where |xi| is the largest of the∣∣x j∣∣ ,

∑j

A jix j = λxi, |λ | |xi| ≤∑j

A ji∣∣x j∣∣≤ |xi| so |λ | ≤ 1.

Now suppose v is an eigenvector for λ . Then

A v =



qv2

pv1 +qv3...

pvn−2 +qvn

pvn−1

= λ



v1

v2...

vn−1

vn

 .