Detecting the Order of Marcov Chain in given Sequence using AIC

I was working on really interesting project where we need to determine if there is any pattern in a given sequence or its just random sequence. In case you are not familiar with Sequential analysis or Markov Chains you might like to go through these introductory posts:

• Sequential data analysis
• Markov Chain : concept and example

Lets consider one example. There are 4 activities person X can do as following work(1), cook(2), eat(3) and sleep(4). The observed behavior for that person is nothing but a sequence. Lets say in this example the observed sequence is: 1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4...

Now it is pretty easy to predict the next activity in the sequence, which should be 1. The reason is after sleep (4) the person X is always at work(1). In other words we need information about only one state in the given sequence to predict the next state. If the current state is 1 then next state must be 2. If current state is 2 then next must be 3 and so on. This is called first order Markov Chain.

Similarly the second order Markov Chain sequence might look something like this: ...p, q, r, s, t... where the state p and q together decide next state should be r. So in other words if current state is q then we cant be sure about next state being r. It depends on previous state as well.

Now coming back to the problem statement, we are trying to check if for a given set of activities or sequence, is there any pattern we can find or its just random. Important thing to remember is as we wish to check for higher orders the mathematical complexity increases. So in this post we are trying to check only for 0th, 1st, 2nd and "3rd or higher" order.

The code to detect the order can be found below.