Stationary distribution of a Markov chain

[Gregg]

Homework Statement

find the stationary distribtion of $\left( \begin{array}{ccccc} \frac{1}{2} & \frac{1}{2} & 0 & 0 & 0 \\ \frac{1}{3} & \frac{2}{3} & 0 & 0 & 0 \\ 0 & \frac{1}{3} & \frac{2}{3} & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 \end{array} \right)$

Homework Equations

$\pi S = \pi$

The Attempt at a Solution

So I think the definition is this $\left( \begin{array}{ccccc} \pi _1 & \pi _2 & \pi _3 & \pi _4 & \pi _5 \end{array} \right)\left( \begin{array}{ccccc} \frac{1}{2} & \frac{1}{2} & 0 & 0 & 0 \\ \frac{1}{3} & \frac{2}{3} & 0 & 0 & 0 \\ 0 & \frac{1}{3} & \frac{2}{3} & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 \end{array} \right)= \left( \begin{array}{c} \pi _1 \\ \pi _2 \\ \pi _3 \\ \text{}_{\pi _4} \\ \pi _5 \end{array} \right)$

I get simulataneous equations... (I've just realized I was doing matrix multiplication the wrong way round)

$\frac{\pi_1}{2} + \frac{\pi_2}{3} = \pi_1$
$\frac{\pi_1}{2} + \frac{2\pi_2}{3} = \pi_2$
$\frac{\pi_3}{3} = \pi_3$
$\pi_5 = \pi_4$
$\pi_4 = \pi_5$

and with the extra condition

$\sum_i \pi_i = 1$ *

This reduces to 3 equations with 4 unknowns.

$\pi_1/2=\pi_2/3$
$\pi_3=0$
$\pi_4=\pi_5$

and using * :

$\pi_1 +3\pi_1/2+2\pi_5 = 1$

This gives me

$\vec{\pi}=\left( \begin{array}{c} \pi _1 \\ 3\frac{\pi _1}{2} \\ 0 \\ \frac{1}{2}-5\frac{\pi _1}{2} \\ \frac{1}{2}-5\frac{\pi _1}{2} \end{array} \right)$

I am unsure how to find $\pi_1$$0 <= \pi_1 <=2$ all seem to work fine. Is this the stationary distribution, an interval of allowed distributions? I thought they were unique.

 

[HallsofIvy]

Homework Statement

find the stationary distribtion of $\left( \begin{array}{ccccc} \frac{1}{2} & \frac{1}{2} & 0 & 0 & 0 \\ \frac{1}{3} & \frac{2}{3} & 0 & 0 & 0 \\ 0 & \frac{1}{3} & \frac{2}{3} & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 \end{array} \right)$

Homework Equations

$\pi S = \pi$

The Attempt at a Solution

So I think the definition is this $\left( \begin{array}{ccccc} \pi _1 & \pi _2 & \pi _3 & \pi _4 & \pi _5 \end{array} \right)\left( \begin{array}{ccccc} \frac{1}{2} & \frac{1}{2} & 0 & 0 & 0 \\ \frac{1}{3} & \frac{2}{3} & 0 & 0 & 0 \\ 0 & \frac{1}{3} & \frac{2}{3} & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 \end{array} \right)= \left( \begin{array}{c} \pi _1 \\ \pi _2 \\ \pi _3 \\ \text{}_{\pi _4} \\ \pi _5 \end{array} \right)$

I get simulataneous equations... (I've just realized I was doing matrix multiplication the wrong way round)

$\frac{\pi_1}{2} + \frac{\pi_2}{3} = \pi_1$
$\frac{\pi_1}{2} + \frac{2\pi_2}{3} = \pi_2$
$\frac{\pi_3}{3} = \pi_3$
$\pi_5 = \pi_4$
$\pi_4 = \pi_5$

and with the extra condition

$\sum_i \pi_i = 1$ *

This reduces to 3 equations with 4 unknowns.

$\pi_1/2=\pi_2/3$

The first equation above reduces to $\frac{\pi_1}{2}= \frac{\pi_2}{3}$. The second equation reduces to $\frac{\pi_1}{2}= \frac{2\pi_2}{3}$
Those two together give $\pi_1=\pi_2= 0$.

$\pi_3=0$
$\pi_4=\pi_5$

and using * :

$\pi_1 +3\pi_1/2+2\pi_5 = 1$

And then this becomes $2\pi_5= 1$ so $\pi_4= \pi_5= \frac{1}{2}$

This gives me

$\vec{\pi}=\left( \begin{array}{c} \pi _1 \\ 3\frac{\pi _1}{2} \\ 0 \\ \frac{1}{2}-5\frac{\pi _1}{2} \\ \frac{1}{2}-5\frac{\pi _1}{2} \end{array} \right)$

I am unsure how to find $\pi_1$$0 <= \pi_1 <=2$ all seem to work fine. Is this the stationary distribution, an interval of allowed distributions? I thought they were unique.

 

[Ray Vickson]

Homework Statement

find the stationary distribtion of $\left( \begin{array}{ccccc} \frac{1}{2} & \frac{1}{2} & 0 & 0 & 0 \\ \frac{1}{3} & \frac{2}{3} & 0 & 0 & 0 \\ 0 & \frac{1}{3} & \frac{2}{3} & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 \end{array} \right)$

Homework Equations

$\pi S = \pi$

The Attempt at a Solution

So I think the definition is this


$\left( \begin{array}{ccccc} \pi _1 & \pi _2 & \pi _3 & \pi _4 & \pi _5 \end{array} \right)\left( \begin{array}{ccccc} \frac{1}{2} & \frac{1}{2} & 0 & 0 & 0 \\ \frac{1}{3} & \frac{2}{3} & 0 & 0 & 0 \\ 0 & \frac{1}{3} & \frac{2}{3} & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 \end{array} \right)= \left( \begin{array}{c} \pi _1 \\ \pi _2 \\ \pi _3 \\ \text{}_{\pi _4} \\ \pi _5 \end{array} \right)$

I get simulataneous equations... (I've just realized I was doing matrix multiplication the wrong way round)

$\frac{\pi_1}{2} + \frac{\pi_2}{3} = \pi_1$
$\frac{\pi_1}{2} + \frac{2\pi_2}{3} = \pi_2$
$\frac{\pi_3}{3} = \pi_3$
$\pi_5 = \pi_4$
$\pi_4 = \pi_5$

and with the extra condition

$\sum_i \pi_i = 1$ *

This reduces to 3 equations with 4 unknowns.

$\pi_1/2=\pi_2/3$
$\pi_3=0$
$\pi_4=\pi_5$

and using * :

$\pi_1 +3\pi_1/2+2\pi_5 = 1$

This gives me

$\vec{\pi}=\left( \begin{array}{c} \pi _1 \\ 3\frac{\pi _1}{2} \\ 0 \\ \frac{1}{2}-5\frac{\pi _1}{2} \\ \frac{1}{2}-5\frac{\pi _1}{2} \end{array} \right)$

I am unsure how to find $\pi_1$


$0 <= \pi_1 <=2$ all seem to work fine. Is this the stationary distribution, an interval of allowed distributions? I thought they were unique.

In this problem there is not a uniquely-defined stationary distribution. You can see why, by looking at the one-step transition matrix S. Note that if we start in state 4 or 5 we remain forever in those states, and we flip-flop back and forth between them. If we start in state 3, in the first step we either stay in state 3 or move to state 2. If we are in states 1 or 2 we stay there forever. However, from states 1,2 or 3 we cannot reach state 4 and 5, and vice-versa. Effectively, the state-space splits into two non-communicating parts, and the different steady-state vectors correspond to those two parts. For example, one distribution would be $\pi_1 = \pi_2 = \pi_3 = 0, \pi_4 = \pi_5 = 1/2,$ corresponding to starting in states 4 or 5 and then spending half the time in each over the long run. Another distribution would have $\pi_1, \pi_2 > 0, \pi_3 = \pi_4 = \pi_5 = 0,$ corresponding to starting in state 1,2 or 3. Note that state 3 is transient, so if we start in state 3 we leave it eventually with probability 1; that is why $\pi_3 = 0.$ Note that we can make these conclusions without doing any calculations!

The only remaining issue is to get $\pi_1, \pi_2$ when we start from states 1, 2 or 3. This would be done by solving the simple 2-state case, using just rows 1-2 and columns 1-2 of S. As you note, these give
$\pi_1 = (1/2)\pi_1 + (1/3)\pi_2 \Longrightarrow \pi_2 = (3/2)\pi_1.$ Since $\pi_1 + \pi_2 = 1,$ we get $\pi_1 = 2/5, \; \pi_2 = 3/5.$

The two "basic" steady-state distributions are $\Pi_1 = (2/5,3/5,0,0,0) \text{ and } \Pi_2 = (0,0,0,1/2,1/2).$ The most general steady-state distribution has the form
$\Pi = a \Pi_1 + (1-a) \Pi_2,$ where $a \in [0,1]$ is the probability we start in states 1, 2 or 3 (and 1-a = probability we start in states 4 or 5).

RGV