# How to calculate the autocorrelation of a markov chain?

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

• ive only just started looking at markov chains (this year) but it looks to me that it's some function of the determinant of the transition matrix. maybe that helps – Vaas Oct 24 '17 at 12:06

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}
• I would add that you've implicitly assumed that $X_n$ is already distributed according to the stationary distribution. If it isn't then the second equality in the bottom block doesn't go through (but the first one does). I'm also not really sure where the labeling of the states as -1 and 1 came from. – Ian Oct 25 '17 at 17:52
• @Ian If the process isn't stationary, then the autocorrelation function will vary with time, and the context of the problem suggested strongly that the ACF should only be a function of the lag $d$. As for the state space...that is what I found to give the desired result, after some trial and error :) – Math1000 Oct 25 '17 at 19:21