Finding the stationary distribution of a Markov chain : Exercises

Introduction

The following problems all involve Markov chains with a limiting stationary distribution. The purpose in doing these problems is for you to come to understand how to set up the chain and how to find the stationary distribution by finding the top eigenvector of the transition matrix.

Example problems

Click on the problems to reveal the solution

Problem 1

A Markov chain is described by the following transition matrix: $$ \left( \begin{matrix} 1 - 4p & 4p & 0 \\ 2p & 1 - 4p & 2p \\ 0 & 2p & 1 - 2p \end{matrix} \right) $$ Determine the range of values which $p$ is allowed to take and the range of values of $p$ for which the matrix has a limiting stationary distribution. Then find the limiting stationary distribution for this chain.

For the range of values $p$ can take we know that all the elements of the matrix must be positive or zero and that the rows of the matrix must sum to one. As such $0 \le p \le\frac{1}{4}$

The chain has a limiting stationary distribution if in the long time limit there probability of being in any given state in the future does not depend on the starting state. This is true for $0 \lt p \le \frac{1}{4}$. It is not true for $p=0$ as say we start in state 0. We are guaranteed to finish in state 0 as state 0 is only connected to itself. This is also true for states 1 and 2 - as when $p=0$ the matrix is diagonal. The state we end up in the long time limit thus depends on the intial state and there is no limiting stationary distribution.

There are two ways of proceedinghere:

(1) Gaussian Elimination:

We want to find the solution, $\pi$ of the following matrix equation: $$ \pi \mathbf{A} = \pi \qquad \rightarrow \qquad [\mathbf{A}^T - \mathbf{I}] \pi = 0 $$ We do this by Gaussian elimination as follows. First we reduce the matrix to upper triangular form as shown below: $$ [\mathbf{A}^T - \mathbf{I}] = \left( \begin{matrix} -4p & 2p & 0 \\ 4p & -4p & 2p \\ 0 & 2p & -2p \end{matrix} \right) $$ Adding row (1) to row (2) gives: $$ [\mathbf{A}^T - \mathbf{I}] = \left( \begin{matrix} -4p & 2p & 0 \\ 0 & -2p & 2p \\ 0 & 2p & -2p \end{matrix} \right) $$ And now adding row (2) to row (3) gives the an upper triangular matrix: $$ [\mathbf{A}^T - \mathbf{I}] = \left( \begin{matrix} -4p & 2p & 0 \\ 0 & -2p & 2p \\ 0 & 0 & 0 \end{matrix} \right) $$ We can thus write that: $$ [\mathbf{A}^T - \mathbf{I}] \pi = \left( \begin{matrix} -4p & 2p & 0 \\ 0 & -2p & 2p \\ 0 & 0 & 0 \end{matrix} \right) \left( \begin{matrix} \pi_1 \\ \pi_2 \\ \pi_3 \end{matrix} \right) = 0 \qquad \rightarrow \qquad \begin{matrix} -4p \pi_1 + 2p \pi_2 = 0 \\ -2p \pi_2 + 2p\pi_3 = 0 \end{matrix} \qquad \rightarrow \qquad \begin{matrix} 2 \pi_1 = \pi_2 \\ \pi_2 = \pi_3 \end{matrix} $$

(2) Detailed Balance:

We can arrive at the two simultaneous equations above via an alternative route if we use the detailed balance condition. Remember this states the elements of the transition matrix, $\mathbf{A}$, and the elements of the limiting stationary distribution, $\pi$, are related by: $$ \pi_i A_{ij} = \pi_j A_{ji} $$ With our transition matrix: $$ \mathbf{A} = \left( \begin{matrix} 1 - 4p & 4p & 0 \\ 2p & 1 - 4p & 2p \\ 0 & 2p & 1 - 2p \end{matrix} \right) $$ We thus have for states 1 and 2: $\qquad \pi_1 4p = \pi_2 2p \qquad \rightarrow \qquad 2\pi_1 = \pi_2$

And for states 2 and 3: $\qquad \pi_2 2p = \pi_3 2p \qquad \rightarrow \qquad \pi_2 = \pi_3$

The end of the problem

Both the methods described above (Gaussian elimination and Detailed balance) got us to the following equations: $$ 2\pi_1 = \pi_2 \qquad \textrm{and} \qquad \pi_2 = \pi_3 $$ We thus have two simultaneous equations and two unknowns. We cannot solve these equations. We know, however, that $\pi$ is a vector of probabilities and that as such this vector must be normalized so that: $$ \pi_1 + \pi_2 + \pi_3 = 1 $$ We can thus write: $$ 1= \pi_1 + \pi_2 + \pi_3 = \pi_1 + 2 \pi_1 + 2\pi_1 = 5\pi_1 \qquad \rightarrow \qquad \pi_1 = \frac{1}{5} $$ Inserting this equation into the equations above gives: $$ \pi_1 = \frac{1}{5} \qquad \pi_2 = \frac{2}{5} \qquad \pi_3 = \frac{2}{5} $$

Problem 2

Consider the reversible Markov chain, between the states $X=0,1,2,3,4,5,6,7,8$, represented by the following matrix. $$ P= \left( \begin{matrix} 0& 1/2& 0& 0& 0& 1/2& 0& 0& 0\\ 1/3 & 0 &1/3& 0& 1/3& 0& 0& 0& 0 \\ 0& 1/2 &0 &1/2& 0& 0& 0& 0& 0 \\ 0 &0 & 1/3& 0 &1/3& 0 &0 &0 &1/3\\ 0& 1/4& 0 &1/4& 0& 1/4& 0& 1/4 &0\\ 1/3& 0 &0& 0& 1/3& 0& 1/3& 0& 0 \\ 0& 0 &0 &0 &0 &1/2& 0& 1/2& 0 \\ 0& 0 &0& 0& 1/3 &0 &1/3& 0 &1/3\\ 0 &0& 0& 1/2& 0& 0& 0& 1/2& 0 \\ \end{matrix} \right) \qquad . $$ Draw the transition graph for this process (hint: start by drawing a 3 x 3 grid of nodes with 0, 5 and 6 on the top row 1,4 and 7 on the second row and 2,3 and 8 on the bottom row). Then find the stationary distribution by using the detailed balance condition.

The transition graph for this particular Markov chain looks like this:

By using the detailed balance condition: $$ \pi_{i}p_{ij} = \pi_{j}p_{ji} $$ we can find that the stationary distribution satisfies the following equations: $$ \pi_0 = \pi_2 = \pi_6 = \pi_8 \qquad \pi_1 = \pi_3 = \pi_5 = \pi_7 = \frac{3}{2} \pi_0 \qquad \pi_4 = 2 \pi_0 $$ When these equations are solved by exploiting the fact that $\pi$ must be normalized we thus find that: $$ \pi_0 = \pi_2 = \pi_6 = \pi_8 = \frac{1}{12} \qquad \pi_1 = \pi_3 = \pi_5 = \pi_7 = \frac{3}{24} = \frac{1}{8} \qquad \pi_4 = \frac{2}{12} = \frac{1}{6} $$

Problem 3

A double glazing firm employs staff to cold call clients and try to sell them new windows for their home. There are three levels of staff pay: Level 1 (£50), Level 2 (£75) or Level 3 (£100). The amount a person is paid in a given evening is determined by their performance that evening and their performance on the previous evening. A staff member who was paid at level 1 on the previous day is moved to level 2 if they are amongst the top 80% of sellers that evening. Similarly a staff member on level 2 the previous evening is moved to level 3 if they are amongst the top 80% this evening. Members of staff in the bottom 20% have their pay reduced by at least one level. If they are in level 2 their pay falls to that of level 1. If they are in level 3 they fall to level 1 if they are in the bottom 5% and level 2 otherwise. If the company employs $n$ members of staff, calculate the average amount they would expect to pay out in salaries each evening. You may assume that the performance of any given member of the sales team is random and hence that the ordering of staff performances is random.

The transition matrix for this problem should be: $$ A = \left( \begin{matrix} 0.2 & 0.8 & 0.0 \\ 0.2 & 0.0 & 0.8 \\ 0.05 & 0.15 & 0.8 \end{matrix} \right) $$ You can find the stationary distribution by using Gaussian elimination. It is: $$ \pi_1=\frac{1}{11} \qquad \pi_2 =\frac{2}{11} \qquad \pi_3 = \frac{8}{11} $$ The expected amount you need to pay out each evening is thus: $$ \textrm{pay} = 90.91n \quad \textrm{pounds} $$

Problem 4

A magazine has print and ipad editions and 100,000 subscribers. These subscribers can subscribe to the magazine in one of three ways. They can buy the print magazine only, they can buy an ipad subscription only or they can buy both an ipad and a print subscription to the magazine. The magazine is constantly changing its content and there is not always a complete overlap between the features in the ipad and print versions of the magazine. As a consequence people are continuously changing their subscription package. In any given week no one ever changes from a purely print subscription to the ipad edition and vice versa. However, every week a constant fraction, $p$, of the subscribers on a print only subscription change to the ipad+print subscription. Similarly $p$ subscribers on an ipad only subscription change to the ipad+print subscription every week. Of those subscribers on the ipad+print subscription a fraction, $2p$, of them decide which version of the magazine they prefer in any given week and adjust their subscription accordingly. Subscribers are split 50/50 on which version of the magazine they prefer so $p$ change to ipad only, while the other $p$ change to print only. Explain why the level of subscription a person has to the magazine is a Markov process, draw the transition graph and write down the transition matrix for the random variable. Calculate the average number of magazines that need to be printed each week in order to satisfy the demand for printed editions.

The transition matrix for this problem should be: $$ \left( \begin{matrix} 1-p & p & 0 \\ p & 1-2p & p \\ 0 & p & 1-p \end{matrix} \right) $$ We find the stationary distribution to be: $$ \pi_1 = \pi_2 = \pi_3 = \frac{1}{3} $$ The number of magazines required is thus: 66667

Problem 5

I own 4 umbrellas and keep some in my home and some in my office. I keep moving between my home and office and only take one of my umbrellas with me if it rains. Obviously, if it does not rain I do not take an umbrella. The probability of rain on any given day is equal to $p$. Explain why the number of umbrellas in my current location, $S$, is a Markov process, draw the transition graph for this variable and write out the transition matrix. When doing this remember that if there are 3 umbrellas in my office, $S_i=3$, and it doesn't rain there will be 1 umbrella available for me once I get home, $S_{i+1}=1$, and set out to the office once more. Now use the Markov chain you have drawn to solve the following problem: If I am in my office/home when it rains and there are no umbrellas available I will get wet as I walk to home/work. Using the detailed balance condition or otherwise show that if $p=0.6$ the probability this will occur is approximately 5.4 %. How many umbrellas should I buy if I want the probability of getting wet to be less than 1 %.

The transition matrix in the four umbrella case is: \[ \begin{matrix} \mathbf{P} = \left( \begin{matrix} 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1-p & p \\ 0 & 0 & 1-p & p & 0 \\ 0 & 1-p & p & 0 & 0 \\ 1-p & p & 0 & 0 & 0 \end{matrix} \right) \end{matrix} \] This matrix has an interesting symmetry, which we will exploit in solving the final problem. At first though lets try to determine the stationary distribution (using detailed balance) for the four umbrella case. The detailed balance equations tell us that: \[ \pi_0 = \pi_4( 1-p) \qquad \pi_1 ( 1-p) = \pi_3 (1-p) \qquad \pi_2 p = \pi_3 p \qquad \pi_1 p = \pi_4 p \] In other words $\pi_1=\pi_2=\pi_3=\pi_4=\frac{1}{1-p}\pi_0$ and, as normalization tells us, we thus have: \[ 1 = \pi_0 + \pi_1 + \pi_2 + \pi_3 + \pi_4 = (1-p)\pi_1 + 4\pi_1 = (5-p)\pi_1 \qquad \rightarrow \qquad \pi_1 = \frac{1}{5-p} \] and hence that: \[ \pi_0 = \frac{1-p}{5-p} \] This probability, $\pi_0$, is the probability that I am in a location where there is no umbrella. For me to also get wet it must rain as I walk to home/work. (I will get wet in these cases as I have no umbrella to take with me on the journey). The probability of getting wet is thus: \[ P(\textrm{WET}) = \frac{p(1-p)}{5-p} = \frac{0.6\times 0.4}{4.4} \approx 0.0545 \] Now the nice thing in this question is that the symmetry of the matrix ensures that we can come up with a general equation for the result. That is to say we can come up with a solution if we have $n$ (as opposed to four) umbrellas. When we construct the $(n+1) \times (n+1)$ matrix that we would have in this case and exploit the detailed balance condition we would find that: $$ \pi_1 = \pi_2 = \pi_3 = \dots = \pi_n $$ Furthermore, just as in the four umbrella question $\pi_0=(1-p)\pi_1$. Following through the working above (i.e. using the normalisation condition and so on) we find that: \[ P(\textrm{WET}) = \frac{p(1-p)}{n+1-p} \qquad \rightarrow \qquad n = \frac{p(1-p)}{P(\textrm{WET})} - 1 + p \] Hence for chance of getting wet to be less than 1% with $p=0.6$ we need: \[ n = \frac{ 0.6 \times 0.4 }{ 0.01 } - 0.4 \approx 24 \]

Problem 6

In the nation of Markovatamia there are three political parties the greens, the blues and the reds. Elections take place every four years and the politicians of these parties all vie for seats in the senate. The number of seats each party holds in the senate is proportional to the number of votes that party received in the election. The voters of Markovatamia are a flighty bunch, however, and regularly switch their allegiances between the parties. In fact the best predictor for the party an elector votes for when the next election swings round is the party that that person voted for in the previous election. In particular, if an elector voted red during the last election the probabilities they will vote green, blue and red in the current election are 0.25, 0.25 and 0.5 respectively. If an elector voted green in the last election they will not vote green again and the probabilities they will vote blue and red are $\frac{2}{3}$ and $\frac{1}{3}$ respectively. Lastly, if an elector voted blue they will not vote blue again. Instead they are equally likely to vote green or red. Given this information calculate the average number of seats each party has in the 370-person senate.

169 red, 106 blues and 95 greens (approximately) (N.B. This problem is slightly different to the one we did in class)