Detecting the Order of Marcov Chain in given Sequence using BIC

In my previous post we have used the AIC (Akaiken Information Criterion) to detect the order in given sequence. However there are few shortfalls of the AIC method. For example it can not always detect the randomness of a sequence accurately. 

Fortunately there is an alternative method BIC (Bayesian Information Criterion) which is pretty much similar to AIC except it can detect randomness of the sequence with more accuracy. 

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 only difference between calculating AIC and BIC can be roughly explained as follows,

• AIC = some-term - penalty1

• BIC = some-term - penalty2 

As you can see we are only changing the penalty which significantly increases accuracy in few scenarios for BIC method. The code for BIC method can be found below.