In this chapter, you will learn to:
- Write transition matrices for Markov Chain problems.
- Find the long term trend for a Regular Markov Chain.
- Solve and interpret Absorbing Markov Chains.
Skip to content Skip to navigation
(What does "Endorsed by" mean?)Summary: This chapter covers principles of Markov Chains. After completing this chapter students should be able to: write transition matrices for Markov Chain problems; find the long term trend for a Regular Markov Chain; Solve and interpret Absorbing Markov Chains.
In this chapter, you will learn to:
We will now study stochastic processes, experiments in which the outcomes of events depend on the previous outcomes. Such a process or experiment is called a Markov Chain or Markov process. The process was first studied by a Russian mathematician named Andrei A. Markov in the early 1900s.
A small town is served by two telephone companies, Mama Bell and Papa Bell. Due to their aggressive sales tactics, each month 40% of Mama Bell customers switch to Papa Bell, that is, the other 60% stay with Mama Bell. On the other hand, 30% of the Papa Bell customers switch to Mama Bell. The above information can be expressed in a matrix which lists the probabilities of going from one state into another state. This matrix is called a transition matrix.
 |
The reader should observe that a transition matrix is always a square matrix because all possible states must have both rows and columns. All entries in a transition matrix are non-negative as they represent probabilities. Furthermore, since all possible outcomes are considered in the Markov process, the sum of the row entries is always 1.
Professor Symons either walks to school, or he rides his bicycle. If he walks to school one day, then the next day, he will walk or cycle with equal probability. But if he bicycles one day, then the probability that he will walk the next day is
We obtain the following transition matrix by properly placing the row and column entries. Note that if, for example, Professor Symons bicycles one day, then the probability that he will walk the next day is
 |
In Example 1, if it is assumed that the first day is Monday, write a matrix that gives probabilities of a transition from Monday to Wednesday.
Let
We use the following tree diagram to compute the probabilities.
 |
The probability that Professor Symons walked on Wednesday given that he walked on Monday can be found from the tree diagram, as listed below.
We represent the results in the following matrix.
 |
Alternately, this result can be obtained by squaring the original transition matrix.
We list both the original transition matrix
The reader should compare this result with the probabilities obtained from the tree diagram.
Consider the following case, for example,
It makes sense because to find the probability that Professor Symons will walk on Wednesday given that he bicycled on Monday, we sum the probabilities of all paths that begin with
The transition matrix for Example 1 is given below.
 |
Write the transition matrix from a) Monday to Thursday, b) Monday to Friday.
In writing a transition matrix from Monday to Thursday, we are moving from one state to another in three steps. That is, we need to compute
b) To find the transition matrix from Monday to Friday, we are moving from one state to another in 4 steps. Therefore, we compute
It is important that the student is able to interpret the above matrix correctly. For example, the entry
There are certain Markov chains that tend to stabilize in the long run, and they are the subject of Section 3. It so happens that the transition matrix we have used in all the above examples is just such a Markov chain. The next example deals with the long term trend or steady-state situation for that matrix.
Suppose Professor Symons continues to walk and bicycle according to the transition matrix given in Example 1. In the long run, how often will he walk to school, and how often will he bicycle?
As mentioned earlier, as we take higher and higher powers of our matrix
Therefore, in the long run, Professor Symons will walk to school
When this happens, we say that the system is in steady-state or state of equilibrium. In this situation, all row vectors are equal. If the original matrix is an
or,
At the end of Section 2, we took the transition matrix
In this section, we wish to answer the following four questions.
Does every Markov chain reach the state of equilibrium?
Answer: A Markov chain reaches a state of equilibrium if it is a regular Markov chain. A Markov chain is said to be a regular Markov chain if some power of it has only positive entries.
Determine whether the following Markov chains are regular.
The matrix
Observe that the first row, second column entry,
The transition matrix
has only positive entries.
Does the product of an equilibrium vector and its transition matrix always equal the equilibrium vector? That is, does
At this point, the reader may have already guessed that the answer is yes if the transition matrix is a regular Markov chain. We try to illustrate with the following example from Paragraph 3.
A small town is served by two telephone companies, Mama Bell and Papa Bell. Due to their aggressive sales tactics, each month 40% of Mama Bell customers switch to Papa Bell, that is, the other 60% stay with Mama Bell. On the other hand, 30% of the Papa Bell customers switch to Mama Bell. The transition matrix is given below.
 |
If the initial market share for Mama Bell is 20% and for Papa Bell 80%, we'd like to know the long term market share for each company.
Let matrix
Since each month the towns people switch according to the transition matrix
After two months, the market share for each company is
After three months the distribution is
After four months the market share is
After 30 months the market share is
The market share after 30 months has stabilized to
This means that
Once the market share reaches an equilibrium state, it stays the same, that is,
This helps us answer the next question.
Can the equilibrium vector
The answer to the second question provides us with a way to find the equilibrium vector
The answer lies in the fact that
Since we have the matrix
Suppose
Therefore,
Does the long term market share for a Markov chain depend on the initial market share?
We will show that the final market share distribution for a Markov chain does not depend upon the initial market share. In fact, one does not even need to know the initial market share distribution to find the long term distribution. Furthermore, the final market share distribution can be found by simply raising the transition matrix to higher powers.
Consider the initial market share
Clearly,
No matter what the initial market share, the product is
If the initial share is
For any distribution
It makes sense, because the entry
Just as the sum of the parts equals the whole, the sum of the parts of
Three companies,
 |
If the initial market share for the companies
Since the long term market share does not depend on the initial market share, we can simply raise the transition market share to a large power and get the distribution.
We summarize as follows:
A Markov chain is said to be a Regular Markov chain if some power of it has only positive entries.
Let
In this section, we will study a type of Markov chain in which when a certain state is reached, it is impossible to leave that state. Such states are called absorbing states, and a Markov Chain that has at least one such state is called an Absorbing Markov chain. Suppose you have the following transition matrix.
 |
The state
In fact, this is the way to identify an absorbing state. If the probability in row i and column i ,
We begin with an application of absorbing Markov chains to the gambler's ruin problem.
A gambler has $3,000, and she decides to gamble $1,000 at a time at a Black Jack table in a casino in Las Vegas. She has told herself that she will continue playing until she goes broke or has $5,000. Her probability of winning at Black Jack is
The transition matrix is written below. Clearly the state 0 and state
Further observe that since the gambler bets only $1,000 at a time, she can raise or lower her money only by $1,000 at a time. In other words, if she has $2,000 now, after the next bet she can have $3,000 with a probability of
 |
To determine the long term trend, we raise the matrix to higher powers until all the non- absorbing states are absorbed. This is the called the solution matrix.
 |
The solution matrix is often written in the following form, where the non-absorbing states are written as rows on the side, and the absorbing states as columns on the top.
 |
The table lists the probabilities of getting absorbed in state 0 or state 5K starting from any of the four non-absorbing states. For example, if at any instance the gambler has $3,000, then her probability of financial ruin is 135/211.
Solve the Gambler's Ruin Problem of Example 11 without raising the matrix to higher powers, and determine the number of bets the gambler makes before the game is over.
In solving absorbing states, it is often convenient to rearrange the matrix so that the rows and columns corresponding to the absorbing states are listed first. This is called the Canonical form. The transition matrix of Example 11 in the canonical form is listed below.
 |
The canonical form divides the transition matrix into four sub-matrices as listed below.
 |
The matrix
 |
The Fundamental matrix
According to the matrix, the entry 1.78 in the row 3, column 2 position says that the gambler will play the game 1.78 times before she goes from $3K to $2K. The entry 2.25 in row 3, column 3 says that if the gambler now has $3K, she will have $3K on the average 2.25 times before the game is over.
We now address the question of how many bets will she have to make before she is absorbed, if the gambler begins with $3K?
If we add the number of games the gambler plays in each non-absorbing state, we get the average number of games before absorption from that state. Therefore, if the gambler starts with $3K, the average number of Black Jack games she will play before absorption is
That is, we expect the gambler will either have $5,000 or nothing on the 7th bet.
Lastly, we find the solution matrix without raising the transition matrix to higher powers.
The matrix
Which is the same as the following matrix we obtained by raising the transition matrix to higher powers.
 |
We summarize as follows:
More about this module: Metadata | Downloads | Version History
This work is licensed by Rupinder Sekhon under a Creative Commons Attribution License (CC-BY 3.0), and is an Open Educational Resource.
Last edited by Collins Williamson on Jul 15, 2011 11:18 pm -0500.
"Reviewer's Comments: 'I recommend this book for undergraduates. The content is especially useful for those in finance, probability statistics, and linear programming. The course material is […]"