# Autocorrelation for a discrete Markov chain

I'm trying to find the autocorrelation function for a discrete parameter Markov chain, $$\{X(k)\}_{k=0}^{\infty}$$ with a transition probability matrix given by $$P = \begin{bmatrix} \frac{1}{3} & \frac{1}{3} & \frac{1}{3}\\ \frac{1}{3} & \frac{1}{3} & \frac{1}{3}\\ \frac{1}{3} & \frac{1}{3} & \frac{1}{3} \end{bmatrix}$$

and initial-state probabilities $$\textbf{p}(0) = [\frac{1}{3}, \frac{1}{3}, \frac{1}{3}]$$ and state space $$E = \{0,1,2\}$$

So the auto-correlation will be given, for $$n\ge 1$$, by $$\mathbf{E}[X(k)X(k+n)]$$. However I am not quite sure how to calculate this. For something like $$\mathbf{E}[X(k)]$$ one could use the definition of expectation and get $$\sum_{k=0}^{3}X(k)\mathbf{P}(X(k)=k)$$. However i am not quite sure how to deal with the product.

• In general, you would use the law of total expectation and condition on $\{X(k)=i\}$ for $i \in \{1, 2, 3\}$. However, this Markov chain is trivial and there is no memory: Every step we independently transition to a new state, equally likely, with no regard to our current state! Commented Jul 26, 2019 at 14:11
• Typo/mistake: The definition of $E[X(k)]=\sum_{k=0}^3 X(k)P[X(k)=k]$ that you give is not correct for at least three reasons. Can you identify some of those reasons? You should first state a correct equation for $E[X(k)]$ as that is a more basic concept than Markov chains. It may help if you first state a definition for $E[X(10)]$. Commented Jul 26, 2019 at 14:13

HINT

Let's see the expectation of the product for $$k=1$$

$$E[X(0)X(1)]=$$ $$=E[X(1)\mid X(0)=0]P(X(0)=0)+E[X(1)\mid X(0)=1]P(X(0)=1)+E[X(1)\mid ]P(X(0)=2)=$$ $$=\frac13\big(E[X(1)\mid X(0)=0]+E[X(1)\mid X(0)=1]P(X(0)=1)+E[X(1)\mid ]P(X(0)=2)\big).$$

Then $$E[X(1)\mid X(0)=0]=P(X(1)=1\mid X(0)=0)+2P(X(1)=2\mid X(0)=0)=\frac13+\frac23=1.$$ $$E[X(1)\mid X(0)=1]=P(X(1)=1\mid X(0)=1)+2P(X(1)=2\mid X(0)=1)=\frac13+\frac23=1,$$ $$E[X(1)\mid X(0)=2]=P(X(1)=1\mid X(0)=2)+2P(X(1)=2\mid X(0)=2)=\frac13+\frac23=1.$$

That is,

$$E[X(0)X(1)]=1.$$

Consider that, for al $$m\geq 1$$:

$$P^m = \begin{bmatrix} \frac{1}{3} & \frac{1}{3} & \frac{1}{3}\\ \frac{1}{3} & \frac{1}{3} & \frac{1}{3}\\ \frac{1}{3} & \frac{1}{3} & \frac{1}{3} \end{bmatrix} ^m=\begin{bmatrix} \frac{1}{3} & \frac{1}{3} & \frac{1}{3}\\ \frac{1}{3} & \frac{1}{3} & \frac{1}{3}\\ \frac{1}{3} & \frac{1}{3} & \frac{1}{3} \end{bmatrix}.$$

(This can be shown by mathematical induction.)

That is, the $$n$$-step transition probability matrix is the same as the one step matrix. As a result, at the $$k^{\text{th}}$$ step the probabilities of the possible states are equal. ($$\frac13$$)

From here I infer that $$E[X(k)X(k+1)]=1$$ for all $$k$$.