Autocorrelation for a discrete Markov chain

Question

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.

Answer 1

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$.