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

  • $\begingroup$ 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$? $\endgroup$ – Nate Eldredge Dec 22 '16 at 19:17
  • $\begingroup$ You may assume $S \subseteq \mathbb{R}$ $\endgroup$ – HolyMonk Dec 22 '16 at 19:18
  • 1
    $\begingroup$ 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. $\endgroup$ – Nate Eldredge Dec 22 '16 at 19:25
  • $\begingroup$ Yes you make a very valid point. $\endgroup$ – HolyMonk Dec 22 '16 at 19:28
  • $\begingroup$ I will reconsider my question. $\endgroup$ – 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.

enter image description here


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+ϵ)ϵ$.

  • $\begingroup$ Indeed, very nice example. $\endgroup$ – HolyMonk Dec 23 '16 at 9:07
  • $\begingroup$ 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}$. $\endgroup$ – HolyMonk Dec 23 '16 at 9:10
  • $\begingroup$ @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$. $\endgroup$ – Nawaf Bou-Rabee Dec 23 '16 at 11:03
  • $\begingroup$ 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? $\endgroup$ – HolyMonk Dec 23 '16 at 11:10
  • $\begingroup$ @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} ]$. $\endgroup$ – Nawaf Bou-Rabee Dec 23 '16 at 12:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.