= Solution
{c}
Fix any two <integers> $i,j$. By <Bézout's identity>, there are <integers> $u,v$ with $au-bv=j-i$. Replacing $(u,v)$ by $(u+kb,v+ka)$ leaves this identity unchanged. Choose $k$ large enough that both entries are nonnegative. A path with $u+kb$ upward steps and $v+ka$ downward steps then takes $i$ to $j$, with strictly positive <probability> $p^{u+kb}q^{v+ka}$. There are no boundary restrictions on this <state space>.
This applies in both directions, so every pair of states communicates. Hence
$$
\boxed{\text{The Markov chain is irreducible, with sole communicating class }\mathbb Z.}
$$
Back to article page
