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.
Please forgive the poor wording.
 A: 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}.$$
