I'm having some trouble converting a second order Markov chain into a first order Markov chain, namely I want to define some new random variables $Y_i$, that have the property $P(Y_i=b|Y_{i-1}=b_1,...Y_0 = b_n) = P(Y_i=b|Y_{i-1}=b_1)$, given random variables $X_i$, that have the property that $P(X_i=a|X_{i-1}=a_1,...X_0 = a_n) = P(X_i=a|X_{i-1}=a_1,X_{i-2}=a_2)$. I also need to find a function such that $f(Y_i) = X_i$. I thought initially that I could simply define $Y_i = X_i + X_{i-1}$, and use something like the Cantor pairing function, but I've been told that the cardinality of the range of the random variables shouldn't matter.
Any suggestions?
For intuition, think about a recurrence relation, say $a_n = a_{n-1} + a_{n-2}$. You can turn this into a first order recurrence in two variables by writing $a_n = a_{n-1} + b_{n-1},b_n = a_{n-1}$. We do the same thing to turn higher order differential equations into first order differential equations.
Do the same thing for your Markov chain: given the process $X_n$, define a Markov chain $(Y_n,Z_n)$ in two variables, where $Z_n=Y_{n-1}$ and the distribution of $Y_n$ is determined by $Y_{n-1}$ and $Z_{n-1}$ (in the same way that the distribution of $X_n$ is determined by $X_{n-1}$ and $X_{n-2}$).