# Question

Let $(X_n)_{n\in \mathbb{N}}$ be an irreducible Discrete Time Markov Chain (DTMC) with finite state space $S$, transition matrix $P$ and steady state $\pi$. Assume that we are ''far enough'' in time that we may assume that for all $n$ $X_n \overset{d}{=} \pi$ then we define: $$\ell_m := \mbox{Corr}(X_{n}, X_{n+m}),$$ since we are working with a Markov chain one would think that for all $m$, $\ell_m$ can be expressed in function of $\ell_1$. My question is : Is there a good way to see this and what this relation is? i.e. find for each $m$ the function $f_m$ s.t. $\ell_m = f_m(\ell_1)$. As show below, for the special case $|S| = 2$ the function $f_m$ is just given by $f_m(x) := x^m$.

# Special Case

In a very special case : a state space with only 2 states we have with $\pi = [\alpha\quad 1-\alpha]$ that for some constant $a \in \left[\max\left(2-\frac{1}{\alpha},0\right),1\right]$: $$P = \begin{pmatrix} a & 1-a\\ \frac{\alpha-\alpha a}{1-\alpha} & \frac{\alpha a - 2\alpha + 1}{1-\alpha}. \end{pmatrix}$$ This allows one to see (by trivial calculations) that $\ell_1 = \mbox{Det}(P)$. But then we see, as $\ell_m$ is just $\ell_1$ for the adapted process $Y_n := X_{n\cdot m}$: $$\ell_m = \mbox{Det}(P^m) = \mbox{Det}(P)^m = \ell_1^m$$

• I know how correlation of real-valued random variables is defined, but how do you define the correlation of random variables taking values in an abstract set $S$? – Nate Eldredge Dec 22 '16 at 19:17
• You may assume $S \subseteq \mathbb{R}$ – HolyMonk Dec 22 '16 at 19:18
• I guess I'm also a little confused by the question. It certainly can't be true that there is a single family of functions $f_m$ that does the job for every possible Markov chain, or even for every possible Markov chain on a given fixed state space $S$. And if you allow the family $f_m$ to depend on the chain, then it is trivially true since you just set $f_m(\ell_1)$ to be whatever $\ell_m$ is for that chain. – Nate Eldredge Dec 22 '16 at 19:25
• Yes you make a very valid point. – HolyMonk Dec 22 '16 at 19:28
• I will reconsider my question. – HolyMonk Dec 22 '16 at 19:28

Here is a simple counterexample that is a bit too long for a comment.

Consider two discrete-time Markov chains on $S=\{1,2,3\}$ with the following two transition matrices: $$P_1 = \begin{bmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{bmatrix} \;, \quad P_2 = \begin{bmatrix} 0 & 1/2 & 1/2 \\ 1/2 & 0 & 1/2 \\ 1/2 & 1/2 & 0 \end{bmatrix}$$ Both chains are irreducible and leave the uniform distribution invariant. The corresponding discrete-time Markov chains have the same lag-$1$ equilibrium autocorrelation, i.e., $\ell_1=-1/2$. However, for $k>1$ their lag-$k$ autocorrelations are quite different since the first chain is periodic with period $3$ while the second chain's lag-$k$ autocorrelation decays to zero with $k$.

This is not quite a counterexample, since the first chain does not have a steady-state or limiting distribution. To correct this deficiency, we break its periodicity by slightly perturbing its entries using a small parameter $\epsilon>0$: $$\tilde P_1 = \begin{bmatrix} 0 & 1-\epsilon & \epsilon \\ \epsilon & 0 & 1-\epsilon \\ 1-\epsilon & \epsilon & 0 \end{bmatrix}$$ The lag-$k$ correlation functions for the chains with transition matrices $\tilde P_1$ (blue line) and $P_2$ (black line) are plotted below with $\epsilon=1/25$ (chosen for visualization purposes only). The inset shows the first few lag correlations. Note that $\ell_1$ is the same for the two chains.

As the OP (HolyMonk) points out in the comments to this answer: for $\tilde P_1$ (given above) and for any $\epsilon>0$, we have $\ell_1 = -1/2$ and $\ell_2 = -1/2−3(−1+ϵ)ϵ$.
• I have done the calculations and in fact we just have $\ell_1 = \frac{-1}{2}$ regardless of the value of $\varepsilon$ whilst for example $\ell_2 = -3 \varepsilon^2 + 3 \cdot \varepsilon - \frac{1}{2}$. – HolyMonk Dec 23 '16 at 9:10
• @HolyMonk That is not quite what I get. For $\tilde P_1$ I get $\pi \propto (1-\epsilon, (1-\epsilon)^{-1}-\epsilon,1)$ and $\ell_1 = (3-4 \epsilon + 3 \epsilon^3 -2\epsilon^4) (-6 + \epsilon (11+(-7+\epsilon) \epsilon))^{-1}$. So for $\epsilon=1/25$ we have $\ell_1 \approx -0.5098$. – Nawaf Bou-Rabee Dec 23 '16 at 11:03
• What do you mean by $\pi$? I usually use this notation for the stationary distribution/steady state but I would think this is just $[\frac{1}{3},\frac{1}{3},\frac{1}{3}]$ here? – HolyMonk Dec 23 '16 at 11:10
• @HolyMonk That's right: I am using your notation for the steady state distribution. The steady distribution for $\tilde P_1$ is no longer uniform when $\epsilon>0$ since $[\frac{1}{3}, \frac{1}{3}, \frac{1}{3}] \tilde P_1 = [ \frac{1-\epsilon}{3}, \frac{1+\epsilon}{3}, \frac{1}{3} ]$. – Nawaf Bou-Rabee Dec 23 '16 at 12:39