# Multiplying two markov chains

Let there be two homogenous markov-chains $$(X_t)_{t \in \mathbb{N}_0}$$ and $$(Y_t)_{t \in \mathbb{N}_0}$$ with transition matrices $$P_X$$ and $$P_Y$$, given as follows:

$$P_X = \begin{pmatrix} 0 & 1 & 0\\ 0 & 0 & 1\\ 1 & 0 & 0 \end{pmatrix}, P_Y = \begin{pmatrix} \frac{2}{3} & \frac{1}{3}\\ 1 & 0 \end{pmatrix}$$

I need to calculate the transition matrix $$P_Z$$ of $$(Z_t)_{t \in \mathbb{N}_0}$$ where $$Z_t = X_t \cdot Y_t$$ for all $$t \in \mathbb{N}_0$$.

Since $$\{0, 1, 2\} \times \{0, 1\} = \{(0,0),(0,1),(1,0),(1,1),(2,0),(2,1)\}$$, $$Z_t$$ has the 3 states $$0, 1$$ and $$2$$.

What I'm confused about is that when I'm in state $$0$$ of $$Z_t$$, I could be in any of the states $$(0,0), (0,1), (1,0)$$ and $$(2,0)$$ in the "combined" matrix. But then the probability to go from state $$0$$ to, say, back to state $$0$$ depends on which of the four states in the combined matrix I am, which would mean the value $$P^{n+1}_{Z, 0,0}$$ depends not only on $$P^n_{Z, 0, 0}$$ but also on previous states. But then I would not have a markov-chain anymore.

• Your observations are correct. If this is a textbook exercise it suggests $Z_t$ is intended to be the Cartesian product of $X_t$ and $Y_t.$ If it's a problem you have formulated for yourself, you have demonstrated it is unanswerable.
– whuber
Jan 28, 2020 at 16:57
• Quite true. The sequence $Z_t$ is not necessarily a Markov chain. Jan 28, 2020 at 17:34

Edit: So, to elucidate (I clearly didn't entertain enough the possibility $$Z_t$$ was not going to be a Markov chain), one reason why $$Z_t$$ isn't a Markovian is the following.

Let $$Z_{t-2} = 2$$ (and $$X_{t-2} = 2$$), then it follows per construction that $$Z_{t-1} = 0$$ (and $$X_{t-1} = 0$$). But then at time $$t$$, $$X_t = 1$$. Thus $$P(Z_t = 2 \mid Z_{t-1} = 0, Z_{t-2} = 2) = 0$$, and the chain now depends on the last two time-points, and it follows that $$Z_t$$ is not Markovian. However, the stationary distribution $$(5/6, 1/12, 1/12)$$ derived below is the valid stationary distribution for $$Z_t$$, but $$Z_t$$ is not a Markov chain, and therefore the assumption

$$\pi_Z P_Z = \pi_Z$$

does not hold. Thus the answer below builds a Markovian model of $$Z_t$$ that has the exact stationary distribution under the requirements, but it is not the actual $$Z_t$$ chain.

Original answer, mistaken assumption highlighted: The stationary distribution of $$X_t$$ is trivially going to be the vector $$\pi_X = (1/3, 1/3, 1/3)$$, while the stationary distribution of $$Y_t$$ after a bit of work is going to be $$\pi_Y = (3/4, 1/4)$$. It follows that the probability of, say, $$\pi_Z(0)$$ must be equal to the sum of the possibilities leading to $$Z_t = 0$$ in stationarity. That is,

$$\pi_Z(0) = \pi_X(0)\cdot \pi_Y(1) + \pi_X(0)\cdot \pi_Y(0) + \pi_X(1)\cdot \pi_Y(0) + \pi_X(2)\cdot \pi_Y(1) \\ = 1/12 + 3/12 + 3/12 + 3/12 = 5/6,$$

and since $$Z_t = 2$$ only if $$X_t = 2, Y_t = 1$$ and $$Z_t = 1$$ only if $$X_t = 1, Y_t=1$$, it follows that $$\pi_Z(1) = \pi_Z(2) = 1/12$$. Thus the stationary vector of the Markov chain $$Z_t$$ is $$\pi_Z = (5/6, 1/12, 1/12).$$

As you implicitly mention in your answer, if $$Z_t = 2$$, it follows that $$X_{t+1} = 0$$, so $$Z_{t+1} = 0$$. Similarly, if $$Z_t = 1$$, $$Y_t = 1$$, so we must again have $$Z_{t+1} = 0$$. We are thus left with calculating the transition probabilities given $$Z_t = 0$$.

For this, recall that by stationarity of Markov chains, we must have $$\pi_Z P_Z = \pi_Z.$$

But by our arguments above, the transition matrix therefore must satisfy $$(5/6, 1/12, 1/12) \begin{pmatrix} p_{0\rightarrow 0} & p_{0\rightarrow 1} & p_{0\rightarrow 1}\\ 1 & 0 & 0\\ 1 & 0 & 0 \end{pmatrix} = (5/6, 1/12, 1/12),$$

and by calculating the l.h.s, we have $$(5/6, 1/12, 1/12) \begin{pmatrix} p_{0\rightarrow 0} & p_{0\rightarrow 1} & p_{0\rightarrow 1}\\ 1 & 0 & 0\\ 1 & 0 & 0 \end{pmatrix} = (5/6 p_{0\rightarrow 0} + 2/12, 5/6 p_{0\rightarrow 1}, 5/6 p_{0\rightarrow 2}),$$ which in particular implies, after multiplying through by 12 and rearranging, a system of 3 (decoupled) equations in 3 unknowns, $$(10p_{0\rightarrow 0}, 10p_{0\rightarrow 1}, 10p_{0\rightarrow 2}) = (8,1,1),$$ or $$(p_{0\rightarrow 0}, p_{0\rightarrow 1}, p_{0\rightarrow 2}) = (4/5, 1/10, 1/10),$$ such that the final matrix is $$P_Z = \begin{pmatrix} 4/5 & 1/10 & 1/10\\ 1 & 0 & 0\\ 1 & 0 & 0 \end{pmatrix}.$$

• Given Xi'an and whuber's comments, this is clearly only valid under additional assumptions not stated in the original question. Jan 28, 2020 at 17:45
• I think in the calculation of $\pi_z$ the index of $\pi_y$ in the last product should be $0$ and the first explicitly stated matrix should have $p_{0 \to 2}$ in the top right corner. Unfortunately I couldn't edit because "Edits must be at least 6 characters; is there something else to improve in this post?"
– Niki
Jan 28, 2020 at 18:34
• Other than that, this seems to work out. Do you know what those additional assumptions are?
– Niki
Jan 28, 2020 at 18:36
• @Niki: Clarified :-) Jan 29, 2020 at 11:04