Why is random walk on $n$-cycle irreducible?

Question

Why is random walk on $n$-cycle irreducible?

Isn't $P\left(j,j\right)$ always zero? How do you make $P^t\left(x,y\right) > 0$?

Answer 1

The definition of irreducibility (correctly presented in your question) is saying that it is possible to get from any state to any other state in a finite number of steps.

In the case of the $n$-cycle, it is possible that we could walk the entire way round the cycle: i.e. $X_0 = 0, \, X_1 = 1, \ldots X_{n-1} = n-1, \, X_n = 0$; in which case we would have visited every site, and so the Markov Chain is irreducible.

For a more formal proof: consider $j,k \in \mathbb{Z}_n$, without loss of generality we can assume that $j = 0$ (due to the symmetry of the transition matrix). We will show that there exists $t > 0$ such that $P^t(0,k) > 0$.

Consider one specific way of walking from $0$ to $k$ by going clockwise round the cycle

$$\mathbf{P}(X_0 = 0,\, X_1 = 1,\ldots, X_k = k) = \left(\frac12\right)^k$$

Then it follows that \begin{align*} P^k(0,k) &= \mathbf{P}(X_k = k \, | X_0 = 0) \\ & \geq \mathbf{P}(X_0 = 0,\, X_1 = 1,\ldots, X_k = k)\\ & = \left(\frac12\right)^k\\ & > 0 \end{align*}

In the case $k = 0$, this is a walk with $0$-steps, and so as expected the probability of going from $0$ to $0$ in no steps is $1$; if you don't feel comfortable with this specialcase, you can of course consider instead the walk that takes $n$-steps clockwise: \begin{align*} P^n(0,0) &= \mathbf{P}(X_n = 0 \, | X_0 = 0) \\ & \geq \mathbf{P}(X_0 = 0,\, X_1 = 1,\ldots, X_n = 0)\\ & = \left(\frac12\right)^n\\ & > 0 \end{align*}

Note that to deduce irreducibility we did not need to compute the transition matrix.