# 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, 2017 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, 2017 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 :) Oct 25, 2017 at 19:21
• I'll frame it another way: this is definitely the right answer in this situation, but for folks other than the OP it could stand to have a little bit more elaboration on some assumptions (which the OP really should have included themselves, but didn't).
– Ian
Oct 25, 2017 at 21:30
• I agree, but I did answer the specific question - "I was wondering how they got this answer!" Oct 25, 2017 at 23:28
• @Math1000 , the assumption about the states {-1, 1} is correct, also the stationary part. thanks a lot
– os12
Oct 27, 2017 at 13:22