1

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?

1 Answers1

1

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}$).

Ian
  • 101,645
  • I think I'm a little confused, notationally. We're defining $X_n$ and $Y_n$? I'm given some chain, $X_n$. –  Apr 17 '15 at 01:00
  • Actually, I must be confused more than notationally. –  Apr 17 '15 at 01:03
  • @Anthony See my edit, maybe it is clearer now. – Ian Apr 17 '15 at 01:03
  • I'm allowed to use two variables in my Markov chain? –  Apr 17 '15 at 01:04
  • @Anthony I honestly don't see how else you would do it. The process I have defined is indeed a Markov chain, in the sense that the distribution of the next state is dependent only on the distribution of the current state. Does this not match your definition? – Ian Apr 17 '15 at 01:04
  • I'm not sure this usage is allowed in the definition I've been given- the way a Markov chain is defined for me is a as a collection of random variables. –  Apr 17 '15 at 01:07
  • 1
    @Anthony But is a random variable in your terminology always real-valued, or can it be vector-valued? I see vector-valued random variables all the time, often just called random variables, so I would be a little bit surprised at the requirement that your random variables be real-valued. I also have no idea how you would answer this problem under this constraint. – Ian Apr 17 '15 at 01:07
  • I think it's real valued. In which case I could just use a pairing function from $\mathbb{R}\times \mathbb{R} \rightarrow \mathbb{R}$, but I was told there was a simpler solution... –  Apr 17 '15 at 01:09