# Converting 2nd order Markov chain to the 1st order equivalent

Given a 2nd order Markov chain where each state takes values in the set $\mathcal{X}=\{A,C,G,T\}$, such that all transition probabilities $p(x_t|x_{t-1},x_{t-2})$ are larger than zero,

How to convert it to the equivalent 1st order one with all the transition probabilities defined?

• If you make your state include the values at the previous time-step, it will be first order. – Glen_b -Reinstate Monica Oct 31 '13 at 14:47
• @Glen_b - with a few seconds of typing, well maybe a few more sentences too, you could put this into an answer, which would probably be accepted, and would consequently save the rest of us the trouble of clicking through! :) – jbowman Oct 31 '13 at 16:44
• @Glen_b, then what will be the transition probabilities like? Is it something like $P(X_{t+1},X_{t}|X_{t-1},X_{t-2}) = P(X_{t}|X_{t-1},X_{t-2}) \dot P(X_{t+1}|X_{t},X_{t-1})$? – xiaohan2012 Oct 31 '13 at 17:19

Here's a way to do it:

(I may be writing my state vectors and transition matrices transposed relative to the way you might have learned them, or even the way they're usually done. If that's the case you'll need to translate back.)

The probability model gives you probabilities for 4 output states at time $t$ in terms of the 16 input states - the possible ordered pairs for $(x_{t-1},x_{t-2})$.

For speed of writing, let's write $AC$ for $(A,C)$ and so on.

\begin{array}{c|cccc|cccc|c} & AA & AC &AT&AG& CA &CC &CT &CG& \ldots \\ \hline A &p_{AA\to A}&p_{AC\to A}&p_{AT\to A}&p_{AG\to A}&p_{CA\to A}&p_{CC\to A}&p_{CT\to A}&p_{CG\to A}\\ C &p_{AA\to C}&p_{AC\to C}&p_{AT\to C}&p_{AG\to C}&p_{CA\to C}&p_{CC\to C}&p_{CT\to C}&p_{CG\to C}\\ T &p_{AA\to T}&p_{AC\to T}&p_{AT\to T}&p_{AG\to T}&p_{CA\to T}&p_{CC\to T}&p_{CT\to T}&p_{CG\to T}\\ G &p_{AA\to G}&p_{AC\to G}&p_{AT\to G}&p_{AG\to G}&p_{CA\to G}&p_{CC\to G}&p_{CT\to G}&p_{CG\to G}\\ \hline \end{array}

We could label the partitions with boldface versions of the state $x_{t-1}$:

\begin{array}{c|cccc|cc|c|cc} & AA & AC &AT&AG& CA & &\ldots && \ldots& GG \\ \hline A & & & & & & & & & & \\ C & & \mathbf{A} & & & \quad\mathbf{C} & &\mathbf{T}& & \mathbf{G} & \\ T & & & & & & & & & & \\ G & & & & & & & & & & \\ \hline \end{array}

As I mentioned in comments, you need to extend the state. Let $z_t$ consist of pairs of states $(x_t,x_{t-1})$ and now consider a Markov Chain in $z_t$; that is, you have a transition matrix $p(z_t|z_{t-1})$.

So the state at time $t$ will be one of the 16 pairs $(A,A), (A,C) \ldots (G,G)$, and the transition matrix will be a 16 $\times$ 16 matrix of transition probabilities that will be mostly zero (necessarily so, because any pair that doesn't have the second component of $z_t$ match with the first component of $z_{t-1}$ is impossible).

As above, for speed of writing, let's also write $AC$ for $(A,C)$ and so on.

For ease of display I am going to define $z_{t-1}^*$ which is simply a permuted $z_{t-1}$. We can write $p(z_t|z_{t-1}^*)$ and then arrive back at $p(z_t|z_{t-1})$ by simple permutation.

So the transition matrix for $p(z_t|z_{t-1}^*)$ is of the form:

\begin{array}{c|cccc|cc|c|cc} & AA & AC &AT&AG& CA & &\ldots && \ldots& GG \\ \hline AA & & & & & & & & & & \\ CA & & \mathbf{A} & & & \quad\mathbf{0} & &\mathbf{0}& & \mathbf{0} & \\ TA & & & & & & & & & & \\ GA & & & & & & & & & & \\ \hline AC & & & & & & & & & & \\ \vdots & & \mathbf{0} & & & \quad\mathbf{C} & &\mathbf{0}& &\mathbf{0} & \\ \vdots & & & & & & & & & & \\\hline \vdots & & \mathbf{0} & & &\quad\mathbf{0} & &\mathbf{T}& & \mathbf{0} &\\ \vdots & & & & & & & & & & \\ \hline \vdots & & \mathbf{0} & & &\quad\mathbf{0} & &\mathbf{0}& & \mathbf{G} & \\ GG & & & & & & & & & & \\ \hline \end{array}

We can then rearrange either the rows or columns so they're in the same order; the transition matrix no longer has that simple structure, but contains the same values.

Generally, you can use this procedure to transform any $k$-th order Markov chain to a first-order MC (also holds for Hidden Markov Models).

The first order transition matrix: $T^1$ is of size $[k*k]$. And the second order transition matrix: $T^2$ is of size $[k^2*k]$. So you want to reduce the number of rows from $k^2$ to $k$ by merging.

An example is given on the Wikipedia link, you should be able to convert $T^2$ to $T^1$ simply by marginalising over the $t-2$ states (which are not needed for $T^1$) at each column.

My explanation is probably not crystal clear but I think you will understand what I mean once you see the example on the link.