# How to construct a Markov Chain of higher order given another Markov Chain

Given a Markov Chain, I'm trying to construct a Markov Chain of a higher order. So, I'm given Markov Chain $\{ \xi_i \}$ such that $\xi_i \in E = \{0, 1, \dots, N \}$ (so it's finite) and

$$P(\xi_n = x_n | \xi_{n - 1} = x_{n - 1}, \xi_{n - 1} = x_{n - 1}, \dots, \xi_0 = x_0) = P(\xi_n = x_n | \xi_{n - 1} = x_{n - 1})$$

For any $x_n, \dots, x_0$ and $n \geq 1$. The transition matrix is time homogeneous and therefore $P(\xi_n = x_n | \xi_{n - 1} = x_{n - 1}) = p_{x_n x_{n - 1}}$.

An idea I'm trying to apply is basically the following: if I need a Markov Chain of order $m$ then I can make the transitional probability of my new process $\{ \eta_i \}$ so that it uniformly chooses some $t$ from $\{n - 1, n - 2, \dots, n - m\}$ (i.e. $t$ takes values of $n - 1, n - 2, \dots, n - m$ with the same probability) and then take the state from the step $t$, so that

$P(\eta_n = x_n | \eta_{n - 1} = x_{n - 1}, \dots, \eta_{n - m} = x_{n - m}, \dots, \eta_0 = x_0) = P(\eta_n = x_n | \eta_{n - 1} = x_{n - 1}, \dots, \eta_{n - m} = x_{n - m}) = p_{x_n x_t}$

Where $t$ is, as mentioned, sampled uniformly from past $m$ states. I was asked to write a rigorous proof that the resulting chain is indeed a Markov Chain with memory, but I'm unable to understand why my explanation that there is an explicit probability dependency only on the last $m$ states and therefore it is Markov Chain of higher order by construction is not accepted as it certainly seems valid to me.

Any ideas how to achieve the described goal?

• The preferred way to write this is to show that a chain on an enlarged state space (in this case $E^m$) is Markov in the usual sense. – Ian May 14 '18 at 15:53
• @Ian okay this makes sense, because as far as my understanding goes if $E^m$ chain happens to be Markov then the unwrapped one would be Markov Chain of order $m$. However, I'm still not sure how to prove the fact that $E^m$ would be the Markov Chain in a usual sense, could you please elaborate on that? – omtcvxyz May 15 '18 at 5:00