There is a different kind of Markov process containing so called absorbing stateswhich result in
transition matrices which are not regular. However, Theorem 10.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
n+1 ∑ n
pij = pikpkj,
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.
Lemma 10.3.1Let p,q > 0 and p + q = 1. Then the eigenvalues of
^{2} have 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 conditions of Theorem
10.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
n ∑ n−1 n−1 n−1
p0j = p0k pkj = qp0(j−1) + pp0(j+1)for j ∈ [1,b− 1],
n k n
p00 = 1, and p0b = 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], (10.3)
P0 = 1 and Pb = 0. (10.4)
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 =
will solve the difference equation. Now choose C_{1},C_{2} to satisfy the boundary conditions 10.4.
Thus you need to have
( )b
C1 + C2 = 1, C1 + C2 q = 0
p
It follows that
pb qb
C2 = -b---b, C1 = -b---b
p − q q − p
Thus P_{j} =
qb pb ( q)j qb pb−jqj qj(qb− j − pb− j)
-b---b + -b---b - = -b---b −-b---b = -----b---b----
q − p p − q p q − p q − p q − p
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 10.3 and 10.4 that P_{j} = 1 and
P_{j} = j are two solutions to the difference equation and proceeding as before.