# Is this Markov?

Consider a process $\{X_n, n\geq 0\}$ with state space $S=\{0,1,2\}$ s.t. $$P(X_{n+1}=j | X_n=i, X_{n-1}=i_{n-1}, \dots, X_0=i_0)=\begin{cases} P_{ij}^I \ \ \ n \ \mbox{ even},\\ P_{ij}^{II} \ \ \ n \ \mbox{odd} \end{cases}$$where $\sum_{j=0}^2 P_{ij}^I = \sum_{j=0}^2 P_{ij}^{II}=1$.

I don't see why this shouldn't be a Markov chain. It looks to me like a non-time homogeneous Markov chain.

Any ideas? Thanks a lot for any help! :)

-
Yes, this is a time-inhomogenous Markov chain. Is this your question? – Did Jan 20 '13 at 19:44
Yes :) Then there is no need to enlarge the state space to make it Markov? Does it satisfy the Chapman-Kolmogorov equations? – Daniel Jan 20 '13 at 19:56
There is only dependence on the divisibility of $n$ by $2$, hence the enlargement is just $S\times \{0,1\}$. – Ilya Jan 20 '13 at 20:12
The solution says the enlargement is $S=\{0,1,2,\hat{0},\hat{1}, \hat{2}\}$ where $X_n$ takes $0,1,2$ if even and $\hat{0}, \hat{1}, \hat{2}$ if odd. But why do we need to do that? Isn't $X$ a Markov chain anyways? – Daniel Jan 20 '13 at 20:17
Once again, X is a Markov chain, an inhomogenous one. The enlargement trick you describe is only useful to make X a homogenous Markov chain. – Did Jan 21 '13 at 7:30

Each inhomogenous Markov chain $(X_n)_{n\geqslant0}$ on the state space $S$ with transitions $(P^I_{ij})_{ij}$ and $(P^{II}_{ij})_{ij}$ alternatively, can be embedded in a homogenous Markov chain $(Z_n)_{n\geqslant0}$ with $Z_n=(X_n,Y_n)$, on the state space $S\times\{0,1\}$, with transitions $(Q_{(i,u),(j,v)})_{(i,u),(j,v)}$ defined by $$Q_{(i,0),(j,1)}=P^I_{ij},\quad Q_{(i,1),(j,0)}=P^{II}_{ij},\quad Q_{(i,0),(j,0)}=Q_{(i,1),(j,1)}=0.$$