There is a different kind of Markov process containing so called absorbing stateswhich result in transition
matrices which are not regular. However, Theorem 12.1.3 may still apply. One such example is
the Gambler’s ruin problem. There is a total amount of money denoted by b. The Gambler
starts with an amount j > 0 and gambles till he either loses everything or gains everything. He
does this by playing a game in which he wins with probability p and loses with probability q.
When he wins, the amount of money he has increases by 1 and when he loses, the amount of
money he has decreases by 1. Thus the states are the integers from 0 to b. Let p_{ij} denote the
probability that the gambler has i at the end of a game given that he had j at the beginning. Let
p_{ij}^{n} denote the probability that the gambler has i after n games given that he had j initially.
Thus
∑
pni+j1 = pikpnkj,
k
and so p_{ij}^{n} is the ij^{th} entry of P^{n} where P is the transition matrix. The above description indicates that
this transition probability matrix is of the form
The absorbing states are 0 and b. In the first, the gambler has lost everything and hence has nothing else to
gamble, so the process stops. In the second, he has won everything and there 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 12.3.1Let p,q > 0 and p + q = 1. Then the eigenvalues of
( )
0 q 0
|| .. ||
A ≡ || p 0 . ||
|( ... ... q |)
0 p 0
have absolute value less than 1.
Proof: By Gerschgorin’s theorem, (See Page 367.) if λ is an eigenvalue, then
|λ|
≤ 1. Alternatively,
you note that ∑_{i}A_{ij}≤ 1. If λ is an eigenvalue of A then it is also one for A^{T} and if A^{T}x = λx where
^{2} have absolute value less than 1 because they are just the
eigenvalues of a matrix of the sort in Lemma 12.3.1. It follows that the conditions of Theorem 12.1.3 apply
and therefore, lim_{n→∞}P^{n} exists. ■
Of course, the above transition matrix, models many other kinds of problems. It is called
a Markov process with two absorbing states, sometimes a random walk with two aborbing
states.
It is interesting to find the probability that the gambler loses all his money. This is given
by lim_{n→∞}p_{0j}^{n}.From the transition matrix for the gambler’s ruin problem, it follows that
∑
pn0j = pn0−k1pkj = qpn0−(j1−1) + ppn0−(j1+1)for j ∈ [1,b− 1],
k
pn00 = 1, and pn0b = 0.
Assume here that p≠q. Now it was shown above that lim_{n→∞}p_{0j}^{n} exists. Denote by P_{j} this limit. Then the
above becomes much simpler if written as
Pj = qPj−1 +pPj+1 for j ∈ [1,b − 1], (12.3)
P = 1 and P = 0. (12.4)
0 b
It is only required to find a solution to the above difference equation with boundary conditions. To do this,
look for a solution in the form P_{j} = r^{j}and use the difference equation with 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 pr^{2}− r + q = 0, and so the solutions for r are r =
To find the solution in the case of a fair game, one could take the lim_{p→1∕2} of the above solution.
Taking this limit, you get
P = b−-j.
j b
You could also verify directly in the case where p = q = 1∕2 in 12.3 and 12.4 that P_{j} = 1 and P_{j} = j are
two solutions to the difference equation and proceeding as before.