2

Question from an old test:

Find an example of a periodic Markov chain with $3$ states, with a stationary distribution $( \frac{1}{6}, \frac{1}{3}, \frac{1}{2})$.

I can see only two ways to connect the states.
Graphs

A triangle won't work because if we connect it in the way shown in (A), the stationary distribution is different.
If we add at least one edge going in the opposite direction, as in (B), then the chain won't be periodic, because there are periods of $3$ and $5$, so the GCD is $1$.

The second way is to connect as shown in the drawing (C) which is periodic with period $2$, but then I don't see how to choose the probabilities $p$ and $q$, because the condition for the stationary distribution to be equal to $( \frac{1}{6}, \frac{1}{3}, \frac{1}{2})$ will never be met:

$$ \begin{bmatrix} 0 & 1 & 0 \\ p & 0 & q \\ 0 & 1 & 0 \end{bmatrix} \begin{bmatrix} \frac{1}{6} \\ \frac{1}{3} \\ \frac{1}{2} \end{bmatrix} = \begin{bmatrix} \frac{1}{6} \\ \frac{1}{3} \\ \frac{1}{2} \end{bmatrix} $$

The above is always false.

What am I missing? How to find an example of such a chain?

Michał
  • 675
  • 1
  • 12
  • What if you use the last chain structure, but permute the state labels? You do not need to make state b the middle state. – Michael Feb 18 '24 at 21:21
  • @Michael What do you mean? Then the other state will be the middle state and then there is the same problem. – Michał Feb 18 '24 at 21:32
  • By "middle" state I mean the state in the middle of your picture, not in the middle of the 3-tuple $(1/6, 1/3, 1/2)$. – Michael Feb 18 '24 at 21:35
  • Can you show me the theorem that says the state in the middle of your picture must be represented as the second coordinate in your 3-tuple? – Michael Feb 18 '24 at 21:56
  • @Michael I guess it doesn't have to be this way, but even if I move the 'middle' so that it is in 'a', the matrix still doesn't match, because it comes out: [0,p,q & 1,0,0 & 1,0,0]. – Michał Feb 18 '24 at 22:05

1 Answers1

1

You multiplied with the stationary distribution on the wrong side. Markov chain transition matrices are usually written such that the distribution needs to be multiplied from the left, and indeed you wrote the matrix that way. So you want

$$ \begin{bmatrix}\frac16,\frac12,\frac13\end{bmatrix} \begin{bmatrix}0&1&0\\p&0&q\\0&1&0\end{bmatrix} = \begin{bmatrix}\frac16,\frac12,\frac13\end{bmatrix}\;, $$

and this indeed has a solution with $p=\frac13$, $q=\frac23$.

joriki
  • 238,052
  • Thank you. One thing, can you change the order in the stationary distribution? In the question it is $( \frac{1}{6}, \frac{1}{3}, \frac{1}{2})$, and you multiply by $(\frac{1}{6}, \frac{1}{2}, \frac{1}{3})$. – Michał Feb 19 '24 at 08:04
  • 1
    @Michał: Well, you drew the transition graph between the states like that. I thought that was meant to represent all equivalent graphs, I didn’t think you were implying that the vertices are in the same order as in the distribution vector (especially since right above that you have three vertices in a triangle that aren’t in any particular order compared to the distribution vector). If the order in the graph was meant to correspond to the order in the distribution vector, you just have to use the appropriate equivalent graph that connects the $\frac12$ state to the two other states. – joriki Feb 19 '24 at 09:57