1

I have the following markov chain:

enter image description here

Let $(X_n)_{n=0,1,\ldots}$ be the markov chain. For every bijective map $f: \{1,2,3\} \rightarrow \{a,b,c\}$, the map $f\big((X_n)_{n=0,1,\ldots}\big)$ is also a Markov chain.

Find a mapping $f: \{1,2,3\}\rightarrow \{a,b\}$ such that $f\big((X_n)_{n=0,1,\ldots}\big)$ is not a markov chain.

I don't really understand what this question wants me to show. Do I have to show that relabeling the states preserves the markov chain property?

Nullspace
  • 979
  • 1
    For how I understand it, a MC is defined by P(x_t|past)=p(x_t|x_t-1), where x takes values in a set X. You have to show that y_t=f(x_t), which takes value in a,b,c in the first case and in a,b in the second, respects the MC property in the first case but not the second. – Thomas Jun 23 '21 at 20:12

1 Answers1

1

The non-trivial one seems to be the second part, the first property is indeed just a relabelling of the states.

Choose $f(1)=f(2)=a$ and $f(3)=b$. Than one can write things like $P(X_t \in \{ 1,2\})=P(f(X_t) = a)$.

We observe:

$P(X_{t+1} \in \{3\}|X_t \in \{1,2\}) =P(X_t \in \{2\})=1/3$ [1]

because the stationary distribution is $\pi=(1/3,1/3,1/3)$.

but:

$P(X_{t+1} \in \{3\}|X_t \in \{1,2\},X_{t-1} \in \{1,2 \}) =2/3$ [2]

because if $X_t \in \{1,2\},X_{t-1} \in \{1,2 \} \rightarrow X_{t-1}=1$ (if at time $t-1$ $X_{t-1}$ where 2 than at time $t$ it would be 3). Now to arrive at 3, there is only one path starting at $1$ at time $t-1$, which is $1\rightarrow 2\rightarrow3$, which has probability $2/3$.

Since [1] and [2] are not equal, we have:

$P(f(X_{t+1}) = b|f(X_t) = a) =1/3$ [1]

and

$P(f(X_{t+1}) = b|f(X_t) =a,f(X_{t-1}) =a) =2/3$ [2]

Therefore the Markov property is not satisfied.

Thomas
  • 4,029
  • Thank you very much for your answer. I am sorry I didn't see your comment yesterday. I have trying to go through your answer since you posted it and I understand most of the steps but I don't quite understand why it violates the markov property based on the mapping. (I see why the markov property is violated but I don't understand why it is based on the fact that we used a non-injective mapping. ) – Nullspace Jun 24 '21 at 07:57
  • Yes let me know if you find calculation errors. You want the intuitive reason or a formal one ? The intuitive one is that for the non-injective mapping when you know that at time X_t you are in a, you know that you are either in 1 or 2, but you do not know which one and therefore your prediction at time X_t+1 reflect this uncertainty. Adding information about the past at time X_{t-1}, as you can see from the calculations, adds indeed more information and changes your prediction. – Thomas Jun 24 '21 at 08:29
  • Instead, if the mapping where injective, knowing that you are in a at time t would define completetely where you are ( say you are at 2 ) and there is not information about the past that can add more information, since you are already certain of your position – Thomas Jun 24 '21 at 08:31
  • Maybe you can try to formalize the injective case and see how this can work formally. The general idea, anyway, is that if you "coarse grain" information (this is what happens under a non-injective mapping), you lose the markov property because you have less information to predict the future and therefore the past can come into play and permitting you to have better predictions. – Thomas Jun 24 '21 at 08:31
  • Ok that makes a lot of sense. Your first comment cleared it up for me. Thanks for your help! :) – Nullspace Jun 24 '21 at 09:34
  • you are welcome – Thomas Jun 24 '21 at 09:48