Let $n > 1$ be an integer. Consider a sequence of independent random variables $Z_1, Z_2, ...$ with $P(Z_i = -1) = P(Z_i = 1) = \frac{1}{2}$. Let $X_0$ be an arbitrary random variable chosen from values in $\{0, ..., n-1\}$ and let us define the sequence $X_0, X_1, ...$ by $X_i = X_0 + Z_1 +...+Z_i \mod n$.
Two questions. First, how can I prove that the sequence $X_0, X_1, ...$ is a markov chain? I know I have to show $P(X_{i+1} = a | X_0, X_1, ..., X_i) = P(X_{i+1} = a | X_i)$ but I'm not sure how to go about doing this.
Secondly, assuming this is a markov chain, are there any invariant distributions? It would seem not, as you can always go up or down a number depending on $Z_i$ but I don't believe this is correct and do not see why.
Observe that for each $k\geqslant0$, \begin{align} X_{k+1} &= \left(\sum_{i=0}^{k+1} Z_i\right) \bmod n\\ &= \left(Z_{k+1}+\sum_{i=0}^k Z_i \right)\bmod n\\ &= \left(Z_{k+1}+ X_k \right)\bmod n\\ &= g(Z_{k+1}+X_k), \end{align} with $g:\{-1,1\}\times \{0,\ldots,n-1\}\to\{0,\ldots,n-1\}$ a measurable function. Hence for any positive integer $k$, we have \begin{align} &\mathbb P (X_{k+1} = j \mid X_0=i_0,\ldots,X_{k-1}=i_{k-1},X_k = i)\\ =&\ \mathbb P(g(Z_{k+1}+X_k)=j \mid X_0=i_0,\ldots,X_{k-1}=i_{k-1},X_k = i)\\ =&\ \mathbb P(g(Z_{k+1}+X_k)=j \mid X_k=i)\\ =&\ \mathbb P(X_{k+1}=j\mid X_k=i)\\ =:&\ p_{ij}, \end{align}
with $$ p_{ij} = \begin{cases} \frac12,& j=i+1\bmod n\\ \frac12,& j=i-1\bmod n, \end{cases} $$ and hence $\{X_n:n\geqslant 0\}$ is a Markov chain.
Since $p_{i,i+1}>0$ ($\!\!\mod n$) for all $i$, the Markov chain is irreducible. If $n$ is odd, then the Markov chain is aperiodic and hence has a unique stationary distribution $\pi$, as the state space is finite. By symmetry it is clear that $\pi$ is the uniform distribution over $\{0,1,\ldots,n-1\}$.
If $n$ is even, then $P_{ii}^k>0$ (where $P$ is the transition matrix with entries $p_{ij}$) if and only if $k$ is even, so the Markov chain is periodic with period $2$. No stationary distribution exists, but the long-run average fraction of time spent in state $k$, i.e. $$ \nu_k := \lim_{k\to\infty}\frac1{k+1}\sum_{i=0}^k \mathsf 1_{\{j\}}(X_i). $$ is given by the entries in the $j^{\mathrm{th}}$ row of the matrix $$ \frac12\left(\lim_{k\to\infty}P^{2k} + P^{2k+1} \right) $$