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 [itex]\pi_1 = \pi_2 = \pi_3 = 0, \pi_4 = \pi_5 = 1/2,[/itex] corresponding to starting in states 4 or 5 and then spending half the time in each over the long run. Another distribution would have [itex] \pi_1, \pi_2 > 0, \pi_3 = \pi_4 = \pi_5 = 0, [/itex] 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 [itex]\pi_3 = 0.[/itex] Note that we can make these conclusions without doing any calculations!

The only remaining issue is to get [itex] \pi_1, \pi_2[/itex] 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
[itex] \pi_1 = (1/2)\pi_1 + (1/3)\pi_2 \Longrightarrow \pi_2 = (3/2)\pi_1.[/itex] Since [itex] \pi_1 + \pi_2 = 1,[/itex] we get [itex] \pi_1 = 2/5, \; \pi_2 = 3/5. [/itex]

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

RGV