Markov chains

Introduction

A Markov chain is a process where you have a number of states $S=\{s_1,s_2,\ldots,s_r\}$, and the process starts in one of these states and moves to another state. Each move is called a step.

If the process is in step $s_i$ then the probability of moving to $s_j$ in the next step is $p_{ij}$. This probability is independent of the state the process was in before $s_i$. The probabilities $p_{ij}$ for all possible movements are called the transition probabilities.

Mathematically we express Markov chains as transition matrices with the probabilities $p_{ij}$ of moving from one state to another as the entries of the transition matrix.

Imagine a political constituency that elects a different Member of Parliament at each election. It's a marginal constituency, since the political opinions of the voters living there are quite diverse.

If the current MP is from the Labour party, there is a 60% chance that he will retain his seat and a 40% chance that a Conservative MP will be chosen at the next election. If the current MP is Conservative, there is an equal chance of either party being chosen at the next election.

The Markov chain's transition matrix for the underlying process looks like this $$ \mathbf{P} = \begin{array}{cc} & \begin{array}{cc} L & C \end{array} \\ \begin{array}{c} L \\ C \end{array} & \left(\begin{array}{cc} 0.6 & 0.4 \\ 0.5 & 0.5 \end{array} \right) \end{array} $$

Notice that the entries on each row all add up to 1, since each row is the complete probability space for possible transitions from the state that the row represents.

Limit properties

You can calculate the probabilities of being in certain states after a number of steps. For example, if a process starts in state $s_i$, the probability that it will be in state $s_j$ after two steps is $p^{(2)}_{ij}$, which is the $ij$-th entry of the transition matrix squared $\mathbf{P}^2$.

Indeed in general the probability that a process will start in state $s_i$ and end up in state $s_j$ after $n$ steps is $p^{(n)}_{ij}$, the $ij$-th entry of the matrix $\mathbf{P}^n$.

It is also possible to use Markov chain transition matrices to find probabilities of future states given an initial distribution. That means if you know that in the beginning of some example process there are certain probabilities of certain states, you can express them as a vector and left-multiply it to the transition matrix.

If $\mathbf{u}$ is an initial distribution for the initial state of a process and $\mathbf{P}$ is the transition matrix for the ensuing Markov chain, then the probability of being at state $s_i$ after $n$ steps is the $i$-th entry in the vector $$ \mathbf{u}^{(n)} = \mathbf{uP}^n $$

Going back to the politics example, if we know that right now there is a Conservative MP in the seat, then the probability that there will be another Conservative MP in the same seat after two further elections is the second entry of the vector $$ \left(0,1\right) \left(\begin{array}{cc} 0.6 & 0.4 \\ 0.5 & 0.5 \end{array} \right)^2 = \left(0.55,0.45\right) $$ which is 0.45.

Example

Q) A process has three states A, B, and C, and initially there is an equal chance of it being in any of these three states. If the process is in state A, then it has to move to states B or C with equal probability. If in B it has a 0.5 probability of staying in B and 0.25 probability of moving to A or C. If in C it can move to A with probability 0.7 but it can't move to state B.

Find the probability that after three steps the process is in state A. Then find the probability that process is in the same state after four steps as it is after three steps.

A) Initially there is an equal chance of the process being in any state, so the initial distribution is $$ \mathbf{u} = \left(1/3,1/3,1/3\right) $$

The transition matrix is $$ \mathbf{P} = \left(\begin{array}{cc} 0 & 0.5 & 0.5 \\ 0.25 & 0.5 & 0.25 \\ 0.7 & 0 & 0.3 \end{array} \right) $$

Calculate the probability that after three steps the process is in state A by matrix multiplication $$ \mathbf{uP}^3 = \left(1/3,1/3,1/3\right)\left(\begin{array}{cc}0.255 & 0.3625 & 0.3825 \\ 0.32125 & 0.3375 & 0.34125 \\ 0.3955 & 0.28 & 0.3245 \end{array}\right) = \left( 0.3239, 0.3267, 0.3494 \right)$$

where each entry is correct to 4 decimal places. Therefore the probability we're after is 0.3239 to 4 decimal places.

We were also asked that if the process was in some state after three steps, to find the probability that it's in that same step one step later.

We found that $$ \mathbf{uP}^3 = \left( 0.3239, 0.3267, 0.3494 \right)$$ and since $$ \mathbf{P} = \left(\begin{array}{cc} 0 & 0.5 & 0.5 \\ 0.25 & 0.5 & 0.25 \\ 0.7 & 0 & 0.3 \end{array} \right) $$ the probability we're after is the dot product of $\mathbf{uP}^3$ with the diagonal elements of $\mathbf{P}$. This might be a bit confusing. Remember that the transition matrix represents changes from one state to another. So each transition is independent of the step that occurred before it, which is why we can just use $\mathbf{P}$.

Also, the diagonal elements of $\mathbf{P}$ represent transitioning to the same state. So the dot product of $\mathbf{uP}^3$ with the diagonal elements of $\mathbf{P}$ represents all possible situations where we go from one state to the same state again. It is equal to $$ 0.3239\times 0 + 0.3267\times 0.5 + 0.3494\times 0.3 = 0.2862 ~\textrm{(4.s.f.)}$$

Long-run probabilities

After a large number of steps, transition matrices will often converge (depending on their properties). That means you can find probabilities for certain states in the long run.

As long as a Markov chain is non-periodic, it will tend towards a limit as $n$ is taken to infinity. If $\mathbf{P}$ is a transition matrix for a Markov chain, then $$ \lim_{n \to \infty} \mathbf{P}^n = \mathbf{W} $$ where all the rows of $\mathbf{W}$ are the same and equal to a probability vector $\mathbf{w}$. This is a vector of the process's long-run or steady-state probabilities. Interpret them as the average proportion of occurrences of each state after many steps.

In the exam since you'll have a graphical calculator that can handle matrices, the easiest way to find the steady-state probabilities that agrees with the mark schemes is to compute $\mathbf{P}^n$ where $n \ge 10$. If the rows aren't all equal by that point then keep using higher $n$.

By their nature, long-run probabilities also satisfy $$ \mathbf{wP} = \mathbf{w} $$ since they express steady-state behaviour. Then, bringing the terms to one side $$ \mathbf{wP} - \mathbf{w} = \mathbf{0} \Rightarrow \mathbf{w}\left(\mathbf{P}-\mathbf{I}\right) = \mathbf{0} $$

$\mathbf{w}$ is an eigenvector of $\mathbf{P}$ corresponding to the eigenvalue 1. This presents a second method to find $\mathbf{w}$. I actually don't recommend this method - it is much easier to simply compute high values of $\mathbf{P}^n$ on your calculator.

In the above example about politics, see how the ascending powers of $\mathbf{P}$ converge on the limiting matrix $\mathbf{W}$, and the rows become more similar $$ \mathbf{P}^2 = \left(\begin{array}{cc} 0.56 & 0.44 \\ 0.55 & 0.45 \end{array} \right) $$ $$ \mathbf{P}^3 = \left(\begin{array}{cc} 0.556 & 0.444 \\ 0.555 & 0.445 \end{array} \right) $$ $$ \mathbf{P}^4 = \left(\begin{array}{cc} 0.5556 & 0.4444 \\ 0.5555 & 0.4445 \end{array} \right) $$

In fact the limiting matrix is $$ \lim_{n \to \infty} \mathbf{P}^n = \mathbf{W} = \left(\begin{array}{cc} \frac{5}{9} & \frac{4}{9} \\ \frac{5}{9} & \frac{4}{9} \end{array} \right) $$

so the long-run probabilities are $$ \mathbf{w} = \left(5/9 , 4/9\right) $$

This probability vector can be interpreted as the long-term fraction of elections where Labour will win the seat and the Conversatives will win the seat. For every nine elections, Labour will win five, and the Conservatives will win four.

Run lengths and expected values

If the probability of a process staying in one its states $s_j$ after one step is $p_{jj}$, the expected run length is the average number of steps that the process will stay in that state after starting in it.

Think of this quantity as the expected time for the process to eventually change states. Indeed if the probability of the process moving to a different state is $1-p_{jj}$, the formula for the expected run length is $$ \frac{1}{1-p_{jj}} $$

Proof (click to expand)

The expected run length is the expected value for the number of consecutve steps where the process's state remains constant. Let $L$ be the expected run length and $p$ be the probability of the process staying in that same state. The initial state is a given and each successive step happens with probability $p$, taking into account that every step must remain in the same state as before $$ L = 1 + p + p^2 + p^3 + \ldots $$ Since $0\le p\le 1$ this is a convergent infinite geometric series with starting term 1 and multiplier $p$. Hence $$ L = \frac{1}{1-p} $$

Looking at the above formula, you can see that for small values of $p_{jj}$ close to zero the expected run length tends to 1. You can also tell that as $p_{jj}$ tends to 1, the expected run length tends to infinity.

Periodic states

Certain Markov chains have periodic states and their transition matrices do not converge to a single steady-state matrix in the long-run. Instead they can converge differently for $\mathbf{P}^n$ depending on whether $n=2k$ ($n$ is even) or $n=2k+1$ ($n$ is odd).

There are however distinct long-run probabilities for $\mathbf{P}^{2n}$ and $\mathbf{P}^{2n+1}$ as $n\to\infty$. These can be found in the same way as for Markov chains that don't have periodic states. Just try computing powers with $n\ge 10$ as in the mark schemes.

Consider the following transition matrix for a Markov chain $$ \left( \begin{array}{cccc} 0 & 1 & 0 & 0 \\ \frac{1}{2} & 0 & \frac{1}{2} & 0 \\ 0 & \frac{1}{2} & 0 & \frac{1}{2} \\ 0 & 1 & 0 & 0 \end{array} \right)$$

For any $n\ge 1$ $$ \mathbf{P}^{2n} = \left( \begin{array}{cccc} * & 0 & * & 0 \\ 0 & * & 0 & * \\ * & 0 & * & 0 \\ 0 & * & 0 & * \end{array} \right), ~ \mathbf{P}^{2n+1} = \left( \begin{array}{cccc} 0 & * & 0 & * \\ * & 0 & * & 0 \\ 0 & * & 0 & * \\ * & 0 & * & 0 \end{array} \right) $$ where * is some positive number. In the exam the theory you need to know is rather limited, but you should be able to recognise when a transition matrix represents a Markov chain with periodic states by the fact that $\mathbf{P}^{2n} \ne \mathbf{P}^{2n+1}$.

In case you're interested though, state $s_i$ has period $d$ if $p^{(n)}_{ii}= 0$ when $n$ is not a multiple of $d$ and if $d$ is the greatest integer with this property. If $d = 1$ then $s_i$ is aperiodic (not periodic).

Absorbtion and reflection

Absorbing Markov chains

A state $s_j$ in a Markov chain is absorbing if $$ p_{jj} = 1 $$ If a process reaches an absorbing state, it stays in that state forever. In a transition matrix you can tell if a row represents an absorbing state if its element on the diagonal is equal to 1 and the remaining elements are all zeroes.

A Markov chain with $r$ absorbing states and $t$ transient states (i.e. normal and not absorbing) can take the following canonical form $$ \mathbf{P} = \left( \begin{array}{cc} \mathbf{Q} & \mathbf{R} \\ \mathbf{0} & \mathbf{I} \end{array} \right) $$ where $\mathbf{Q}$ is a $t\times t$ matrix, $\mathbf{R}$ is a $t\times r$ non-zero matrix, $\mathbf{0}$ is an $r\times t$ matrix of zeroes, and $\mathbf{I}$ is the $r\times r$ identity matrix.

I showed you above that the probability of starting in state $s_i$ and ending up in state $s_j$ after $n$ steps is $p^{(n)}_{ij}$, the $ij$-th entry of the matrix $\mathbf{P}^n$. For chains with absorbing states the matrix is $$ \mathbf{P}^n = \left( \begin{array}{cc} \mathbf{Q}^n & \mathbf{R}^* \\ \mathbf{0} & \mathbf{I} \end{array} \right) $$

In the long run, the elements of each row of $\mathbf{R}^*$ add up to 1, and every element of $\mathbf{Q}^n$ approaches zero $$ \lim_{n\to\infty} \mathbf{Q}^n = \mathbf{0} $$

Proof (click to expand)

Starting in each transient state, the process may go to another transient state or an absorbing state. Let $n_i$ be the minimum number of steps required to reach an absorbing state starting from the state $s_i$.

Let $p_i$ be the probability of not reaching an absorbing state in $n_i$ steps. Suppose $N$ is the largest $n_i$ and $p$ the largest $p_i$. The probability of not being absorbed in $N$ steps is less than or equal to $p$. The probability of not being absorbed in $2N$ steps is less than or equal to $p^2$, etc.

Since $p_i\lt 1$, these are decreasing and tend to zero. Hence $$ \lim_{n\to\infty} \mathbf{Q}^n = \mathbf{0} $$

So overall in the long run if a process started in any of the $t$ transient states it will inevitably end up in one of the absorbing states. This should explain in matrix algebra terms why processes of this nature always tend to the absorbing states in the long run.

Example

Q) A rat is released into a triangular cage with three sections separated by small flaps that the rat can move through. An odour that is unpleasant to the rat is released in section A, so it never stays once it arrives, and it moves to section B with probability 0.4 and to section C with probability 0.6. There is a small cheese dispenser in section B, so it never moves to any other section of the cage once it arrives. If the rat is in section C, it moves to section A with probability 0.1, section B with probability 0.3, and stays in section C with probability 0.6. Identify the absorbing state in this process and confirm this by finding large powers of the transition matrix. If the rat is initially released in each of the three sections with probabilities $\left(1/2,1/4,1/4\right)$ then find the probability the rat is in section B after two steps.

A) Firstly the absorbing state is clearly section B. The transition matrix is $$ \mathbf{P} = \left( \begin{array}{ccc} 0 & 0.4 & 0.6 \\ 0 & 1 & 0 \\ 0.1 & 0.3 & 0.6 \end{array} \right)$$

We can put this in canonical form by swapping the second and third rows, and the second and third columns. The important bit is making sure the A, C, and B rows are in the same order as the A, C, and B columns. $$ \mathbf{P}_c = \left( \begin{array}{ccc} 0 & 0.6 & 0.4 \\ 0.1 & 0.6 & 0.3 \\ 0 & 0 & 1 \end{array} \right)$$

Computing a power of $\mathbf{P}_c$ with $n\ge 10$ gives $$ \mathbf{P}_c^{11} = \left( \begin{array}{ccc} 0.0018219 & 0.0125220 & 0.9856561 \\ 0.0020870 & 0.0143439 & 0.9835691 \\ 0 & 0 & 1 \end{array} \right)$$

The entries in the top left $2\times 2$ sub-matrix are approaching zero, and the top two entries in the right hand column are approaching 1. Since B is an absorbing state, as $n\to\infty$ the long-run probabilities for A, B, and C respectively will approach $$ \mathbf{w} = \left(0,1,0\right) $$

Now the initial distribution for A, B, and C is $$\mathbf{u}=\left(1/2,1/4,1/4\right)$$ so the probability the rat is in section B after two steps is the second element of $$ \mathbf{uP}^2 = \left(1/2,1/4,1/4\right)\left( \begin{array}{ccc} 0 & 0.4 & 0.6 \\ 0 & 1 & 0 \\ 0.1 & 0.3 & 0.6 \end{array} \right)^2 = \left(0.045, 0.67, 0.285\right) $$ which is 0.67.

Reflective barriers

A state $s_j$ in a Markov chain is a reflective barrier if $$ p_{jj} = 0 $$ that is if a process reaches a reflective state, it always moves a different state in the following step.

Example

Q) A hedge fund analyst looks at data for a company's stock price. He categorises the movements of the stock price each day into three categories: up by more than 10% in a day; up or down by less than 10% in a day, and down by more than 10% in a day. His data suggest the following transition probabilities:

Identify which state is a reflective barrier, and write down the transition matrix. Find the long-run probabilities for each state of the process. What assumptions has the analyst made for the stock price's daily movement to be modelled as a Markov process?

A) The third state is a reflective barrier, always transitioning the process to the second state. The transition matrix is $$ \mathbf{P} = \left( \begin{array}{ccc} 0.1 & 0.9 & 0 \\ 0.025 & 0.95 & 0.025 \\ 0 & 1 & 0 \end{array} \right)$$

Computing a power of $\mathbf{P}$ with $n\ge 10$ gives the long-run probabilities $$ \mathbf{W} = \lim_{n\to\infty}\mathbf{P}^n = \left( \begin{array}{ccc} 0.0263852 & 0.9498681 & 0.0237467 \\ 0.0263852 & 0.9498681 & 0.0237467 \\ 0.0263852 & 0.9498681 & 0.0237467 \end{array} \right)$$ Therefore the long-run probabilities are, to four decimal places $$ \mathbf{w} = \left(0.0264, 0.9499, 0.0237\right) $$

To model the stock price's movements as a Markov process, the analyst has assumed that the transition between movement categories each day is independent of the transition before it.

More study materials