# Transformation on state-space that preserves Markov property

I am solving a problem in Mathematical Statistics by Jun Shao

Let $\{X_n \}$ be a Markov chain. Show that if $g$ is a one-to-one Borel function, then $\{g(X_n )\}$ is also a Markov chain. Give an example to show that $\{g(X_n )\}$ may not be a Markov chain in general.

I have a hard time on solving it, even though I have been staring it and thinking about it for a whole day.

1. For the first part, which is to show that any one-to-one Borel $g$ preserves Markov property of a Markov chain, I guess using the formula for density function under the change of random variables by $g$, learned in elementary probability course, might help, but I am not sure how to use it, or maybe the tools needed to solve the problem are not that simple?

2. For the second part, I really have no idea of how to construct some $\{ X_n\}$ so that $\{g(X_n )\}$ is not a Markov chain, for example, when $g(x)=x^2$?

Here are also some extended thoughts and questions:

1. If $g$ is not one-to-one, is $\{g(X_n )\}$ always not a Markov chain for any Markov chain $\{ X_n\}$?
2. How about if $\{X_t \}, t \in \mathbb{R}$? Does any one-to-one $g$ also preserve Markov property of continuous-time stochastic processes?

Thanks a lot!

-

The transformation you are interested in is often called lumping some states of the process and the resulting process a lumped chain.

For a given denumerable Markov chain $X$ on a state space $E$ with transitions $p$ and a given function $g$, whether $g(X)$ is still a Markov chain or not may depend on the initial distribution of $X$, but a necessary and sufficient condition for $g(X)$ to be Markov for any initial distribution of $X$ (condition known at least since C. J. Burke and M. Rosenblatt A Markovian Function of a Markov Chain in 1958 and widely used in the applications) is that for any $x$ and $x'$ in $E$ such that $g(x)=g(x')$ and any $z$ in $g(E)$, $$\sum_{y:g(y)=z}p(x,y)=\sum_{y:g(y)=z}p(x',y).$$ In words, being at a state $x$, the probability to jump to a lumped state $z$ depends on $x$, only through the lumped state $g(x)$.

A simple but inspiring example is a Markov chain $X$ on three states $0$, $1$ and $2$ with transitions from $0$ to $1$, from $1$ to $2$, from $2$ to $1$ and from $2$ to $0$ and no other transition, thus, for a given $u$ in $(0,1)$, $$p(0,1)=p(1,2)=1,\quad p(2,0)=u=1-p(2,1).$$ The chain $X$ is kosher: $X$ is irreducible and aperiodic and converges in distribution to the unique stationary distribution $\pi$ given by $\pi(0)=u/(2+u)$ and $\pi(1)=\pi(2)=1/(2+u)$. Now, lump together states $1$ and $2$, for example by a function $g$ to a two-state space $\{a,b\}$ such that $g(0)=a$ and $g(1)=g(2)=b$. Then, $$P(g(X_{n})=a|g(X_{n-1})=\cdots=g(X_{n-k})=b,g(X_{n-k-1})=a)$$ is $0$ if $k$ is odd and $u$ if $k$ is even. This shows that $g(X)$ is not Markov and even that $g(X)$ is not a Markov chain of any order.

-

The key is that the Markov property is fundamentally about information: if you want to know something about the process's behavior after some time $t$, and you know its location at time $t$, then any information about the process's behavior before time $t$ is irrelevant. All the relevant information from the history is packed up in the value of $X_t$. You can express this in terms of conditional probabilities or conditional independence, but the idea is the same, in either discrete or continuous time.

Now, if $g$ is a one-to-one function, then $g(X)$ contains exactly the same information as $X$. This is easy to understand, because $g$ has an inverse. Thus you should be able to replace $X$ by $g(X)$ and not change the truth of any statement that is only about information; in particular the Markov property should be preserved.

A more formal statement would be: for any $\sigma$-field $\mathcal{G}$, $X \in \mathcal{G}$ iff $g(X) \in \mathcal{G}$. Now, if you express the Markov property formally in terms of $\sigma$-fields, it should become clear how to prove the first part, in either discrete or continuous time.

For a counterexample to the second part, note that if $g$ is not one-to-one, then $g(X)$ may contain less information than $X$ (but never more). If we think about discrete time, in deciding what state to occupy at time $n+1$, the only information we can use is what state we are in at time $n$. But the function $g$ can merge distinct states into a single state, so that we can no longer tell them apart. If the original distinct states influenced $X_{n+1}$ in an important way, then the process can cease to be Markov.

This doesn't have to happen and you can certainly find particular examples of Markov chains $X_n$ and non-one-to-one functions $g$ so that $g(X_n)$ is not Markov. Just try!

-
Thanks! In the formal statement, what does $X \in \mathcal{G}$ mean? –  Ethan Mar 17 '11 at 4:32
It means that $X$ is measurable with respect to the $\sigma$-field $\mathcal{G}$. –  Nate Eldredge Mar 17 '11 at 12:22
Re @Ethan's comment, one cannot recommand the formulation you used in your post of the fact that $X$ is $\mathcal{G}$-measurable, especially in a more formal statement... –  Did Mar 17 '11 at 13:37