10.3 Absorbing States
There is a different kind of Markov process containing so called absorbing states which 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 pij denote the probability that the
gambler has i at the end of a game given that he had j at the beginning. Let pijn
denote the probability that the gambler has i after n games given that he had j initially.
and so pijn is the ijth entry of Pn 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.1 Let p,q > 0 and p + q = 1. Then the eigenvalues of
have absolute value less than 1.
Proof: By Gerschgorin’s theorem, (See Page 497) if λ is an eigenvalue, then
is an eigenvector for λ
be the first nonzero entry. Then
is increasing for some m > k
and so q
Thus by induction, the sequence is increasing. Hence
However, the last line states that p
which requires that
Now consider the eigenvalues of 10.2. For P given there,
and so, expanding the determinant of the matrix along the first column and then along the last
The roots of the polynomial after
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
apply and therefore, limn→∞Pn
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
It is interesting to find the probability that the gambler loses all his money. This is given by
limn→∞p0jn.From the transition matrix for the gambler’s ruin problem, it follows that
Assume here that p≠q.
Now it was shown above that limn→∞p0jn
exists. Denote by Pj
Then the above becomes much simpler if written as
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 Pj
and use the difference equation with boundary
conditions to find the correct values of r
. Thus you need
and so to find r you need to have pr2 − r + q = 0, and so the solutions for r are r =
Thus the two values of r simplify to
Therefore, for any choice of Ci,i = 1,2,
will solve the difference equation. Now choose C1,C2 to satisfy the boundary conditions 10.4.
Thus you need to have
It follows that
Thus Pj =
To find the solution in the case of a fair game, one could take the limp→1∕2 of the above
solution. Taking this limit, you get
You could also verify directly in the case where p = q = 1∕2 in 10.3 and 10.4 that Pj = 1 and
Pj = j are two solutions to the difference equation and proceeding as before.