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?
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}$.