= Solution
{c}
The history $\sigma(S_0,\ldots,S_n)$ is contained in $\sigma(Y_1,\ldots,Y_n)$. The increment $Y_{n+1}$ is independent of this history by the given <independence of random variables>. Therefore
$$
\mathbb P(S_{n+1}=j\mid S_0,\ldots,S_n)
=\mathbb P(Y_{n+1}=j-S_n\mid S_0,\ldots,S_n)
=p\mathbf1_{\{j=S_n+a\}}+q\mathbf1_{\{j=S_n-b\}}.
$$
This depends only on the current state and not on time. It is precisely the <time-homogeneous Markov property>, so $S_n$ is a <Markov chain> with <transition probabilities>
$$
\boxed{p_{i,j}=\begin{cases}b/(a+b),&j=i+a,\\a/(a+b),&j=i-b,\\0,&\text{otherwise},\end{cases}\qquad i,j\in\mathbb Z.}
$$
The conditional identity is an identity that holds <almost surely>; histories of zero <probability> require no division by their <probabilities>.
Back to article page
