[an error occurred while processing this directive] [an error occurred while processing this directive]
These notes were prepared by LT Grant and are used with permission. Pieces of this section are adapted from: Finite Markov Chains, Kemeny and Snell, 1960, and from Random Walks and Electric Networks, Doyle and Snell, 1984.
Before we delve too deeply into Markov Chains and their properties, it might be beneficial to understand where they fit in the larger landscape of mathematics.
Consider modeling the price of a given company’s stock. At time n, we have a wealth of information available to us, the past prices of the stock, the current market conditions, the weather forecast for the next few days, even the price of tea in China, etc. However, if we model the stock using a Finite Markov Process, the only thing which affects the outcome at time n are the previous prices of the stock.
Further, we define a finite 1-st Order Markov Process, these are Markov Processes which only depend on the immediate past. In our stock example, at time n, the only information which would affect our process would be the be the observed stock price at time n - 1.
So in general, we denote the probability of making the transition from state S_{i} to S_{j} at time n as:
Before we proceed more, we will give an example which should help to put some of these concepts in perspective, as well as to help introduce some other ideas.
We consider the magical Land of Oz where the weather follows a very predictable pattern. If it is raining today, then there is a 50% chance of raining again tomorrow, and a 25% chance of either having a nice day or a snowy day tomorrow. Similarly if it is snowing, we have a 50% chance of again having snow, and a 25% chance of either having a nice day, or a rainy day. Also in the land of Oz they never have two nice days in a row, and they equally have rain and snow the day after a nice day.
With this information, one can ask many questions. The first thing we do is to label our states, R,N,S, although one could just as easily label them S_{1},S_{2},S_{3}. With the information above, we can define p_{RR} = 1/2, p_{RN} = 1/4 and so on. We note that writing out every possible transition would give us 3^{2} distinct possibilities. While this isn’t difficult for our case with three states, we note that if we had n states, then we would have n^{2} probabilities.
Thus we use matrices to represent the transition probabilities for our Markov Chain. In our example, our transition matrix is (the row and column labels of R, N and S are for convenience only and are not usually included in the display of the matrix):
We find the probability of going from S_{i} to S_{j} by looking at P_{i,j}. Let it be raining today in Oz. I want to know the probability that tomorrow will be nice. To do this, you look at the R to N or equivalently the (1, 2) entry, and would find that there is a 1/4 chance of a nice day. Also note that all the rows sum to 1, thus this is a Stochastic Matrix.
Now how do we calculate the chance it is nice in two days given it is rainy today? We could use the Law of Total Probability (sometimes also called Bayes’ Rule in elementary probability) to calculate this probability. This requires us to consider every possible weather combination and their respective probabilities. Mixing the R = S_{1}, N = S_{2}, S = S_{3} notation, we find that for this example
For two days, this is not too tedious, but what about the probability it will be nice a week from today given it is rainy today?
This is where the use of matrix notation also becomes very convenient. Notice that the probability above of going from R to N two days hence is the (1.2) entry in the matrix product of P with itself. More generally, we can find the transition probability through n steps by the matrix P^{n}, and this is known as (the finite Markov Chain version of) the Chapman-Kolmogorov Theorem. Thus consider the following matrices from our example:
and
Hence if it is raining today, then the chance it is nice in 2 and 7 days is 3/16 and 0.200012 respectively
We now look a bit further at P^{7}:
Note that the chance of being in any of the three states after seven days is almost independent of our initial state. This means the weather in seven days is almost completely independent of what it is today. If we look at P^{n} for larger values of n, we see the row vectors approach = {2/5, 1/5, 2/5}.
We see that this works for our example, but we note that it will not work for every matrix. Consider:
This matrix describes a two-state system in which we switch states at each time step. Thus Q^{2} = I, Q^{3} = Q, Q^{4} = I and so on.
We say a chain is ergodic if it is possible to move from any one state to any other, not necessarily in one move. Thus both P and Q represent ergodic chains. We say a chain is regular if some power of the transition matrix has all positive entries. While P is such that p_{22} = 0, we see that P^{2} has all nonzero entries, thus P is a regular chain. We also see that Q^{n} will always have zeros, so Q is not a regular chain. In general every regular chain is ergodic, but not every ergodic chain is regular.
If our transition matrix, A, is a regular chain, then we have the following property: As , the matrix A^{n} approaches a limiting matrix , where consists of n copies of the same row vector. This matrix has different names in different texts, two common names are the “limit matrix”, or the matrix of “limiting probabilities.”
Up to this point our only examples have been ergodic chains. Now we consider the following transition matrix:
Note that if we start in state S_{1} or S_{5}, we can’t leave these states. Similarly, if we start in any other state and we “arrive” in states S_{1} or S_{5} at time N, then we remain in those states for all steps n > N. We call these absorbing states, that is, states which once entered are never left.
The transition matrix P represents the random walk on a 5-block street. We assume our random walker is out late at night and has lost all sense of direction on a straight street, he walks one block, stops, looks around, and can’t remember whether he arrived from the left, or the right. Thus he chooses a direction at random, and walks one more block, and repeats the process. He stops when he reaches S_{0}, his house, or S_{4}, a friend’s house. Here we number the states S_{0},S_{1},...,S_{4} in order to make some things a little nicer later, but in general, how we choose to label the states has no effect on the result. In this sense see that if we start at any non-absorbing state, he will eventually arrive at either his house, or his friend’s, and will thus end his wandering.
We note that all matrices with absorbing states are not ergodic, thus R is not ergodic. Therefore we cannot use the result above to get a “limit” matrix, so we must introduce the canonical form. Given a transition matrix with u absorbing states and v non-absorbing states, P, then our matrix has the canonical form:
Where I is the u × u identity matrix, and 0 is the u × v matrix of zeros. Our random walk matrix from above has the canonical form:
The matrix N = (I - Q)^{-1} is called the fundamental matrix. The entries of the fundamental matrix have the following interpretation, N_{ij} is the expected number of times the walker is expected to be at state S_{j} before absorption, given he started in state S_{i}. So in our random walk example:
So letting 1 be the vector of all ones, we have that t = N1 is the expected number of steps before absorption in one of the absorbing states. We define B = NR, this gives us the absorption probabilities. That is, B_{ij} is the probability that starting in the i-th non-absorbing state, that we end up in the j-th absorbing state. In our example:
This allows us to comment about P^{n} for large values of n. As we have that P^{n} approaches the matrix defined as:
( Problem created by LT Grant, 2006.)
(Problem created by LT Grant, 2006.)
(Problem creatd by LT Grant, 2006.)
[an error occurred while processing this directive] [an error occurred while processing this directive]
Last modified: [an error occurred while processing this directive]