TITLE: How to calculate the autocorrelation of a markov chain?
QUESTION [6 upvotes]: i want to know how to calculate the autocorrelation of a markov chain (e.g for a simple random walk ). 
while i was searching online; i found a lecture with a two states {-1,1} markov chain with the following transition matrix  \begin{bmatrix}\alpha&1-\alpha\\1-\alpha&\alpha\end{bmatrix} 
the lag-d autocorrelation was given as: $( 2\alpha-1)^d $. i was wandering how they got this answer?
I was wandering how to calculate the autocorrelation in general for simple markov chains, or at least for just this simple example

REPLY [5 votes]: Note: I am assuming that the state space is $\{-1,1\}$ and that $\mathbb P(X_0=1)=\mathbb P(X_0=-1)$.
The transition matrix $P$ has eigenvalues $1$ and $2\alpha-1$ with corresponding eigenvectors $\pmatrix{1&1}^T$ and $\pmatrix{-1&1}^T$, so we can write $P=V^{-1}DV$ where $D$ is a diagonal matrix with entries the eigenvalues of $P$ and $V$ a matrix whose columns are given by the eigenvalues of $P$. It follows that for $d\geqslant0$,
\begin{align}
P^d &= V^{-1}D^dV\\\\
&= \frac12\pmatrix{1&1\\-1&1}\pmatrix{1&0\\0&(2\alpha-1)^d}\pmatrix{1&-1\\1&1}\\\\
&= \frac12\pmatrix{1+(2\alpha-1)^d & 1-(2\alpha-1)^d\\1-(2\alpha-1)^d&1+(2\alpha-1)^d}.
\end{align}
We can then compute $\mathbb E[X_nX_{n+d}]$ by conditioning on $X_n$:
\begin{align}
\mathbb E[X_nX_{n+d}] &= \mathbb E[X_nX_{n+d}\mid X_n=-1]\mathbb P(X_n=-1)+ \mathbb E[X_nX_{n+d}\mid X_n=1]\mathbb P(X_n=1)\\
&= \frac12\left(\mathbb E[X_{n+d}\mid X_n=1] - \mathbb E[X_{n+d}\mid X_n=-1]\right) \\
&= \frac12\left( (2\alpha-1)^d + (2\alpha-1)^d\right)\\
&= (2\alpha-1)^d.
\end{align}
{"set_name": "stack_exchange", "score": 6, "question_id": 2487450}