Why is random walk on $n$-cycle irreducible? 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$?
 A: 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.
