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

Question

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!

Answer 1

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.

Answer 2

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
AD 0.0000000 0.2500000 0.1250000 0.6250000
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

Hope I have answered your question.