# Discrete time process vs Markov chain.

Let $$X_1,X_2,...$$ be a discrete time process, which takes values in $$S$$ that is finite or countable. I want to prove that there exists a Markov chain $$Y_1,Y_2...$$ taking values in countable $$\hat S$$, and a function $$f:\hat S \rightarrow S$$ such that $$f(Y_n)=X_n$$ for any $$n$$.

How to prove this? It seems untrue as the discrete time process can depend on the past values, while the Markov process only depends on the last value.

• What is $\hat{S}$? – user10354138 Oct 30 '18 at 3:35
• @user10354138 it's the set that the markov chain takes values in. – Dole Oct 30 '18 at 4:31
• In case I'm allowed to be pretend to be a lawyer and use the fact that you have not explicitly put any assumptions on $\hat S$, I'd take $\hat S = S^{\Bbb N}$, i.e. the space of all infinite histories of $X$. Otherwise indeed, there may not exist such a Markov Chain. – Ilya Oct 30 '18 at 16:36
• @Ilya It has to be countable unfortunately. Doesn't work when $S$ is infinite. – Dole Nov 2 '18 at 6:49
• Well, maybe then one could work around with $\hat S = \bigcup_{n\in \Bbb N}S^n$, which is countable – Ilya Nov 5 '18 at 10:11