Monday, October 24, 2016

Invariant Distribution of a Second-Order Markov Chain?

A second-order Markov chain $X$ on a finite state space $\mathcal{X}$ is a stochastic process that satisfies
$$
 \mathbb{P}(X_n=x|X_{n-1}=x_{n-1},\dots,X_1=x_1) = \mathbb{P}(X_n=x|X_{n-1}=x_{n-1},X_{n-2}=x_{n-2})
$$
If the second term is invariant of $n$, we call the second-order Markov chain homogeneous and write
$$
  Q_{x,y\to z}= \mathbb{P}(X_3=z|X_2=y,X_1=x)
$$
We say that this Markov chain is irreducible, if and only if from every pair $(x,y)$ every other state $z$ can be reached in any number of steps. In other words, let
$$
  Q^n_{x,y\to z}= \mathbb{P}(X_n=z|X_2=y,X_1=x).
$$
Then, $X$ is irreducible, if and only if for every $(x,y)$ and every $z$ there exists an $n=n(x,y,z)\ge 1$ such that $Q^n_{x,y\to z}>0$. An even stronger condition is regularity: A second-order Markov chain $X$ is regular if and only if this integer $n$ does neither depend on $(x,y)$ nor on $z$. In this case, we write that $Q^n>0$.

We are now interested in the invariant distribution of $X$. In other words, we look for a probability distribution $\pi_{x,y}$ on $\mathcal{X}^2$ such that
$$
  \pi_{y,z} = \sum_{x\in\mathcal{X}} \pi_{x,y}Q_{x,y\to z}.
$$

More precisely, we are interested in the question whether there exists a unique invariant distribution. It is known, for example, that if $X$ is a first-order Markov chain, a unique invariant distribution exists if $X$ is irreducible. A fortiori, for a first-order Markov chain, a unique invariant distribution exists if $X$ is regular. Moreover, for a first-order Markov chain, a unique invariant distribution exists if $X$ is a so-called ergodic unichain, i.e., a chain with a single communicating class.

It is easy to show that if $X$ is a second-order Markov chain, that then the process $X^{(2)}$ with samples $(X_1,X_2)$, $(X_2,X_3)$, $(X_3,X_4)$, etc. is a first-order Markov chain. The hope is that this fact allows us to compute the invariant distribution (or prove its uniqueness) with the help of the simple first-order case (see, e.g., here). Unfortunately, in the setting we have here, this is not possible. It turns out that even if $X$ is a regular second-order Markov chain (and thus irreducible), the chain $X^{(2)}$ need not be irreducible. To this end, consider the following example:

Let $X$ be a second-order Markov chain on $\{1,2,3,4\}$ with transition matrix $Q$, where
$$Q=\begin{bmatrix} 0.5 & 0.5 & 0 & 0 \\
0 & 0 & 1 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & 1 & 0 \\
0 & 0 & 0.5 & 0.5 \\
0 & 0.5 & 0.5 & 0 \\
0.5 & 0 & 0 & 0.5 \\
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
1 & 0 & 0 & 0 \\
0 & 0.5 & 0.5 & 0 \\
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & 0.5 & 0.5\end{bmatrix}$$
In this matrix, the columns are labeled with states $\{1,2,3,4\}$, while the rows are labeled with the state tuples, i.e., $\{11,12,13,14,21,\dots,44\}$.

This Markov chain is regular, since $Q^{10}>0$, $Q^{11}>0$,... It turns out, however, that $X^{(2)}$ is not irreducible: $X$ is such that, depending on the initial states, we either have $1-2-3-4-1$ and $1-2-3-1$ or $1-4-3-2-1$ and $1-3-2-1$. It follows that $X^{(2)}$ has transient states $\{(1,1),(2,2),(2,4),(3,3),(4,2),(4,4)\}$ and communicating classes:
$$
  \{(1,2),(2,3),(3,1),(3,4),(4,1)\}
$$
 and
$$
  \{(1,3),(3,2),(2,1),(1,4),(4,3)\}.
$$
It follows that there is no unique distribution $\pi_{x,y}$.

To find out (a little bit) more, I recommend Chapter 7 of this book. Unfortunately, this is as much reference as I have found, the original works being only available in Romanian and on paper. I would be extremely grateful for any reference linked here!