 Solution

The sequence is a Markov chain when the conditional law of its next state depends on the past only through the current state. Precisely, for each history of positive probability and every $j\in S$,A time-homogeneous chain additionally has transition probabilities independent of $n$, written $P_{ij}=\mathrm{Pr}(X_{n+1}=j\mid X_n=i)$. The displayed single transition matrix in the subsequent parts specifies this time-homogeneous case.