# Fit and evaluate a second order transition matrix (Markov Process) in R?

I already built 1 first order discrete state Markov Chain model. It was built with R using the function 'markovchainFit()' in 'markovchain' package.

dat<-data.frame(replicate(20,sample(c("A", "B", "C","D"), size = 100, replace=TRUE)))

MC1 <- markovchainFit(dat) # MC1 is the fitted MC Model


Now I am going to build a second order Markov Chain model.

I am not sure how to find the transition matrix, and if the second order Markov Chain model is better than the first order MC model? How to evaluate the them?

Should I choose the first order model or second order model? Is there any standard or test for doing this?

Thank you!

• Your questions about how to evaluate & select MCs are on-topic here, but asking for R code is not. You may get an answer that doesn't include any code. – gung - Reinstate Monica Apr 19 '15 at 13:04
• I would also greatly appropriate of I can get answer without code@gung – uared1776 Apr 19 '15 at 13:27
• @gung Thanks for the comment. I update the question a little bit, now is the information sufficient? – uared1776 Apr 19 '15 at 18:48
• I think the question is fine. I voted to leave your question open & I think it will remain so. I simply left you a comment so you would know what to expect from an answer. – gung - Reinstate Monica Apr 19 '15 at 19:00

This function should produce a Markov chain transition matrix to any lag order that you wish.

dat<-data.frame(replicate(20,sample(c("A", "B", "C","D"), size = 100, replace=TRUE)))

Markovmatrix <- function(X,l=1){
tt <- table(X[,-c((ncol(X)-l+1):ncol(X))] , c(X[,-c(1:l)]))
tt <- tt / rowSums(tt)
return(tt)
}

Markovmatrix(as.matrix(dat),1)
Markovmatrix(as.matrix(dat),2)


where l is the lag.

e.g. 2nd order matrix, the output is:

         A         B         C         D
A 0.2422803 0.2185273 0.2446556 0.2945368
B 0.2426304 0.2108844 0.2766440 0.2698413
C 0.2146119 0.2716895 0.2123288 0.3013699
D 0.2480000 0.2560000 0.2320000 0.2640000


As for how to test what order model. There are several suggestions. One put forward by Gottman and Roy (1990) in their introductory book to Sequential Analysis is to use information value. There is a chapter on that - most of the chapter is available online.

You can also perform a likelihood-ratio chi-Square test. This is very similar to a chi square test in that you are comparing observed to expected frequencies of transitions. However, the formula is as follows:

$$G^2 = 2\sum_i\sum_j n_{ij} \log\left(\frac{n_{ij}}{e_{ij}}\right).$$

The degrees of freedom are the square of the number of codes minus one. In your case you have 4 codes, so (4-1)^2 = 9. You can then look up the associated p-value.

I hope this helps.

• Could you articulate--without using code--what you understand a "second order" model to be? One standard meaning is explained in the other answer to this thread. Your answer is inconsistent with that because you exhibit only a first-order matrix. Your matrix does not provide transitions between ordered pairs of states (of which there are 16, with 64 possible transitions), but only between (original) states. – whuber Feb 5 '18 at 14:31
• good point. Re-reading this answer, not sure what I was referring to. It seems to late to edit the answer - but other should note that the 2nd order matrix is in the answer below. – jalapic Mar 26 '18 at 23:45

The question you should be asking is "Am I in a 1st-order or 2nd-order Markov chain?" rather than which one is better.

In 1st-order, you're next step is only dependent on where you are now, but in 2nd-order, it is dependent on where you were before and now.

In mathematical form, say we wanted to look at probability of you going to be in state A at time $x_{t+1}$, then your probabilities would be:

• 1st-order: $P(x_{t+1} = A | x_t)$
• 2nd-order: $P(x_{t+1} = A | x_t, x_{t-1})$

Let's get on with transition probabilities for 2nd-order. As your 1st-order is $4$x$4$ matrix, your second-order is going to be $4^2$x$4$. This is because you are no longer just looking at transition probabilities AA, AB, AC, etc. (For short-hand, we will refer to (A,B) as AB and (A,B,A) as ABA).

Instead you will be looking at transition probabilities AAA, AAB, AAC, etc. It would look something like this for times X1, X2 and X3:

           A         B         C         D
AA 0.0000000 0.4000000 0.1000000 0.5000000
AB 0.3333333 0.1111111 0.2222222 0.3333333
AC 0.1666667 0.3333333 0.1666667 0.3333333
BA 0.4444444 0.1111111 0.2222222 0.2222222
BB 0.1666667 0.3333333 0.3333333 0.1666667
BC 0.0000000 0.2500000 0.5000000 0.2500000
BD 0.2000000 0.0000000 0.4000000 0.4000000
CA 0.2500000 0.2500000 0.0000000 0.5000000
CB 0.5000000 0.1666667 0.1666667 0.1666667
CC 0.6000000 0.2000000 0.0000000 0.2000000
CD 0.1250000 0.2500000 0.5000000 0.1250000
DA 0.5000000 0.2500000 0.2500000 0.0000000
DB 0.4000000 0.0000000 0.2000000 0.4000000
DC 0.7500000 0.2500000 0.0000000 0.0000000
DD 0.1428571 0.4285714 0.0000000 0.4285714


Let's look at first element of the second row of this matrix, ABA. ABA is calculated by looking at the frequency from A to B, then AB to A divided by AB, just like how you would calculate a 1st-order.

The way to check if you are in 1st-order or 2nd-order is to perform a chi-square test of association on the frequencies of the 2nd order in comparison to your 1st order transition matrix. Since you have 4 states, you will be looking at 4 scenarios/tests; you look at all the 2nd-order frequencies which have A in the middle, B in the middle, C in the middle and D in the middle.

So for A you are looking at rows 1, 5, 9 and 13. (But remember, you are looking at the frequency matrix, which for BAA would be how many transitioned from B to A and then to A again). You then perform a chi-square test of association by comparing each frequency from the 2nd-order to its corresponding transition matrix from the 1st-order; for BAB you would do:

$\frac{(BAB - BAB*AB)^2}{(BAB*AB)}$

You repeat this for all the elements with A in the middle, and see if the it is significant with $(r-1)*(c-1)$ degrees of freedom. Repeat for B, C, and D and if not significant for all, then you're probably in a 1st-order. But if significant, you will be in a 2nd-order, which has a solution too, refer to this article Converting 2nd order Markov chain to the 1st order equivalent