Function of irreducible and aperiodic Markov chain is also a Markov chain?

285 Views Asked by At

Suppose that $X_1,X_2,\ldots$ is a time-homogeneous irreducible and aperiodic Markov chain over a finite state space $\mathcal{X}$, and $f$ is an arbitrary function over $\mathcal{X}$.

Is $f(X_1),f(X_2),\ldots$ also a time-homogeneous irreducible and aperiodic Markov chain? Is it even a Markov chain?

Note that we can construct examples where functions of Markov chains are not Markov chains (see here for example), but these are examples where the original chain is not irreducible or aperiodic.

2

There are 2 best solutions below

0
On

I was able to come up with a counterexample. There indeed exist irreducible and aperiodic Markov chains and functions such that the function of the Markov chain is no longer a first-order Markov chain. The following is one such example.

enter image description here

Consider the original Markov chain to be the one in the above figure, over state space $\{a,b,c,d\}$. The transition probabilities are mentioned along the edges. This is clearly irreducible (since every state can be reached from every other state) and aperiodic (the self loop is enough to guarantee this).

However, if we define $f:\{a,b,c,d\}\to \{A,B\}$ using $$f(x) = \begin{cases} B &\text{if }x=d\\ A&\text{otherwise,} \end{cases}$$ then the process $f(X_1),f(X_2),\ldots$ is not a first-order Markov chain.

To see why this is the case, observe that the sequence $BAA$ can only correspond to $dab$ in the original chain, and this must be followed by $A$ ($c$ in the original chain). In other words, $$ P\Big(f(X_t)=A\Big|\,f(X_{t-1})=A,f(X_{t-2})=A,f(X_{t-3})=B\Big) = 1 $$ while $$ P\Big(f(X_t)=A\Big|\,f(X_{t-1})=A,f(X_{t-2})=B,f(X_{t-3})=B\Big) = 0.5. $$

However, it should be easy to show that if the new process $\{f(X_t):t\geq 1\}$ is indeed a first-order Markov chain, then it must be irreducible and aperiodic.

0
On

If the function is injective, you always recover a Markov chain (whatever the underlying conditions on the Markov chain). In the general case of a non injective function, it is no more true in general but several criteria are known to ensure the mapping preserves Markov property : Dynkin's criterion, and the more general Rogers Pitman's criterion (an intertwining criterion that crucially also involves the measure you start from).

This is the original paper by Rogers Pitman (phrased in term of semigroup, but Fill and coauthors worked out the discrete time version) :

https://www.jstor.org/stable/2243410?seq=1#page_scan_tab_contents

Also, you may have a look at this question on MO :

https://mathoverflow.net/questions/252671/surprising-examples-of-markov-chains/252749#252749

--

Regarding your concern about aperiodicity/irreducibility : the fact that the original chain is aperiodic or irreducible is not really relevant for this specific problem.