Probability and Random Processes Question 6.1:4 In Probability and Random Processes by Grommet and Stirzaker, section 6.1, question 4 it asks

Let $X$ be a Markov chain and let ${n_r : r ≥ 0}$ be an unbounded increasing sequence of positive integers.


Show that $Y_r = X_{n_r}$ constitutes a (possibly inhomogeneous) Markov chain.


Find the transition matrix of $Y$ when $n_r = 2r$ and $X$ is a simple random walk".

I can see that it will be a Markov chain because since $X$ is a Markov chain, modifying the indices will still mean that the next state is only dependent on the current state, not any other. However, I am unable to formalize this or do the last part of the question.
 A: Just try to follow definitions.
$$P(Y_{r}=i_{r}|Y_{r-1}=i_{r-1},...,Y_{0}=i_{0})=P(X_{n_{r}}=i_{r}|X_{n_{r-1}}=i_{r-1},...,X_{n_{0}}=i_{0})$$
By the Markov Property , you have
$$P(X_{n_{r}}=i_{r}|X_{n_{r-1}}=i_{r-1},...,X_{n_{0}}=i_{0})=P(X_{n_{r}}=i_{r}|X_{n_{r-1}}=i_{r-1})=\\P(Y_{r}=i_{r}|Y_{r-1}=i_{r-1})$$ .
Now for $n<m$ say $m=n+k$ for some $k>0$ , you have $$P(X_{m}=i|X_{n}=j)=\\\sum_{i_{1},...,i_{k-1}\in I}P(X_{n+k}=i|X_{n}=j,X_{n+1}=i_{1},...,X_{n+k-1}=i_{k-1})\\\cdot P(X_{n+1}=i_{1},...,X_{n+k-1}=i_{k-1}|X_{n}=j)$$
$$=\sum_{i_{1},...,i_{k-1}\in I}P(X_{n+k}=i|X_{n+k-1}=i_{k-1})p_{ji_{1}}p_{i_{1}i_{2}}p_{i_{2}i_{3}}....p_{i_{k-2}i_{k-1}}$$
$$=\sum_{i_{1},...,i_{k-1}\in I}p_{i_{k-1}i}p_{ji_{1}}p_{i_{1}i_{2}}p_{i_{2}i_{3}}....p_{i_{k-2}i_{k-1}}$$
$$=\sum_{i_{1},....,i_{k-1}\in I}p_{ji_{1}}p_{i_{1}i_{2}}...p_{i_{k-1}i}=p^{(k)}_{ji}$$ where $p_{ji}^{(k)}$ is the $ji$-th entry of $P^{k}=P\cdot P\cdots P\,,\text{k times}$ where $P$ is the transition matrix of the markov chain $(X_{n})_{n\geq 0}$.
So now for $n=2r$ , you have to just calculate $P(Y_{2r}=i|Y_{2(r-1)}=j)$
That is in two steps from $j$ where would you end up?. Let's say you go up with probability $p$ and down with probability $q$.  Then,
$$P(X_{2r}=i|X_{2(r-1)}=j)=p^{2}\delta_{i,j+2}+q^{2}\delta_{i,j-2}+2pq\delta_{i,j}$$ and this precisely gives the $ij$-th element of transition matrix for $(Y_{r})_{r\geq 0}$. Note that $\delta_{i,j}$ is the Kronecker Delta. That is $\delta_{i,j}=\begin{cases} 1\,, i=j\\ 0\,,i\neq j\end{cases}$ . Alternatively , using what I proved above, you can also calculate the matrix $P^{2}$ and use it to find the transition probabilities.
