7.4. Markov Chains
Markov Chains
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.
Example 7.4.1
Example 7.4.2
Let W denote that Professor Symons walks and B denote that he rides his bicycle. We use the following tree diagram to compute the probabilities.
| Monday | Tuesday | Wednesday |
The probability that Professor Symons walked on Wednesday given that he walked on Monday can be found from the tree diagram, as listed below.
P(Walked Wednesday | Walked Monday) = P(WWW) + P(WBW) = 1/4 + 1/8 = 3/8.
P(Bicycled Wednesday | Walked Monday) = P(WWB) + P(WBB) = 1/4 + 3/8 = 5/8.
P(Walked Wednesday | Bicycled Monday) = P(BWW) + P(BBW) = 1/8 + 3/16 = 5/16.
P(Bicycled Wednesday | Bicycled Monday) = P(BWB) + P(BBB) = 1/8 + 9/16 = 11/16.
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 T and T2 as follows:
The reader should compare this result with the probabilities obtained from the tree diagram. Consider the following case, for example:
P(Walked Wednesday | Bicycled Monday) = P(BWW) + P(BBW) = 1/8 + 3/16 = 5/16.
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 B and end in W. There are two such paths, and they are BWW and BBW.
Certain Markov chains, called regular Markov chains, tend to stabilize in the long run. It so happens that the transition matrix we have used in the 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.
Example 7.4.3
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 n by n matrix, we get n vectors that are all the same. We call this vector a fixed probability vector