268 CHAPTER 10. MARKOV PROCESSES
and so pnij is the ijth entry of Pn where P is the transition matrix. The above descriptionindicates that this transition probability matrix is of the form
P =
1 q 0 · · · 0
0 0. . . 0
0 p. . . q
......
. . . 0 0
0 · · · 0 p 1
(10.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.
Lemma 10.3.1 Let p, q > 0 and p+ q = 1. Then the eigenvalues of
0 q 0 · · · 0
p 0 q · · · 0
0 p 0. . .
...... 0
. . .. . . q
0... 0 p 0
have absolute value less than 1.
Proof: By Gerschgorin’s theorem, (See Page 173) if λ is an eigenvalue, then |λ| ≤ 1.Now suppose v is an eigenvector for λ. Then
Av =
qv2
pv1 + qv3...
pvn−2 + qvn
pvn−1
= λ
v1
v2...
vn−1
vn
.
Suppose |λ| = 1. Let vk be the first nonzero entry. Then
qvk+1 = λvk
and so |vk+1| > |vk|. If {|vj |}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| . Thus by induction, the sequence is increasing. Hence |vn| ≥|vn−1| > 0. However, the last line states that p |vn−1| = |vn| which requires that |vn−1| >|vn| , a contradiction. ■
Now consider the eigenvalues of 10.2. For P given there,
P − λI =
1− λ q 0 · · · 0
0 −λ. . . 0
0 p. . . q
......
. . . −λ 0
0 · · · 0 p 1− λ