Let $Y_n=X_{3n}.$ Show that $Y_0,Y_1,...$ is a Markov chain. 
Let $X_0,X_1,...$ be a Markov chain with transition matrix
  $\mathbf{P}$. Let $Y_n=X_{3n}$, for $n=0,1,2,....$ Show that
  $Y_0,Y_1,...$ is a Markov chain and exhibit its transition matrix.

The property of Markov chains is that
\begin{align}
\mathbb{P}(X_{n+1}&=j \ | \ X_0=0,...,X_{n-1}=x_{n-1},X_n=i)\\
&=\mathbb{P}(X_{n+1}=j \ | \ X_n=i),
\end{align}
and I want to show that $Y_0,Y_1,...$ has this property aswell. Substituting in $Y_n=X_{3n}$ I have that
\begin{align}
\mathbb{P}(X_{n+1}&=j \ | \ X_0=0,...,X_{n-1}=x_{n-1},X_n=i)\\
&=\mathbb{P}(Y_{n-2}=j \ | \ Y_0=0,...,Y_{n-3}=i)\\
&=\mathbb{P}(Y_{n-2}=j \ | \ Y_{n-3}=i)\\
&=\mathbb{P}(Y_{n+1}=j \ | \ Y_{n}=i)
\end{align}
which is a Markov chain. Is this correct? And how do I exhibit the transition matrix?
 A: I think you got $X$ and $Y$ mixed up.
The thing you want to show is
$$P(Y_{n+1} = j \mid Y_0 = y_0, \ldots, Y_{n-1} = y_{n-1}, Y_n = i) = P(Y_{n+1} = j \mid Y_n = i).$$
To show this, write the $Y_i$ in terms of $X_i$.
$$P(Y_{n+1} = j \mid Y_0 = y_0, \ldots, Y_{n-1} = y_{n-1}, Y_n = i)
= P(X_{3n+3} = j \mid X_0 = y_0, X_3 = y_1, \ldots, X_{3n-3} = y_{n-1}, X_{3n} = i).$$
By the Markov property for $(X_0, X_1, \ldots)$, the right-hand side can be shown to be equal to $P(X_{3n+3} = j \mid X_{3n} = i)$ (if this is not clear to you, you should prove it explicitly), which in turn can be rewritten as $P(Y_{n+1} = j \mid Y_n = i)$ as desired.

The transition matrix for $(Y_0, Y_1, \ldots)$ involves computing $P(Y_{n+1} = j \mid Y_n = i)$ for all $i$ and $j$. Simply write this in terms of $X_i$, e.g. $$P(X_{3n+3} = j \mid X_{3n} = i) = \sum_k \sum_l P(X_{3n+3} = j, X_{3n+2}=k, X_{3n+1} = l \mid X_{3n} = i) = \cdots$$
and write it interms of the transition probabilities of the $(X_0, X_1, \ldots)$ Markov chain.
In the end, you can actually succinctly write the transition matrix of $(Y_0, Y_1, \ldots)$ as a power of $\mathbf{P}$.
