Proving a sequence is a Markov chain 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.
 A: 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)
$$
