Show that any second-order Markov process can be rewritten as a rst-order Markov pro - cess with an augmented set of state variables. Can this always be done parsimoniously, i. e., without increasing the number of parameters needed to specify the transition model?

Let Yt be a variable that will be able to take this form y1, y2, y3 ..., xk. Markov Chain first - order property states that:

P (Ut=u|Ut-1, Ut-2, Ut-3 ...) = P (Ut=u|Ut-1)

while Markov Chain second - order property allows us to write:

P (Ut=u|Ut-1, Ut-2, Ut-3 ...) = P (Ut=u|Ut-1, Ut-2)

We can be able to change the second-order Markov Chain into the first-order Markov Chain by regrouping the state-space as follow: Let At-1, t be a variable that carries 2 consecutive states of the Zt variable, that is to say : If Zt can carry value z1, z2, z3 then we define At-1, t such that At-1, t can take either z1z1, z1z2, z1z3, z2z1, z2z2, z2z3, z3z1, z3z2, z3z3. In this new state-space we are going to have:

P (At-1, t=at-1, t|At-1, t-1, At-2, t-1, At-3, t-2 ...) = P (At-1, t=at-1, t|At-1, t-1)