Detecting Time Homogeneity in Marcov Chains

Time-homogeneous Markov Chains are the sequences, where the transition probabilities, P i,j (n,  n+1) does not depend on n. So the transition probability in Time Homogeneous Markov Chains is, P i,j (n, n+1) = P i,j 

A simple example of time-homogeneous Markov Chain can be,

      ...1,2,1,2,1,2,1,2,1,2...1,2,1,2,1,2,1,2,1,2... 
 

A simple example of time-inhomogeneous Markov Chain can be,

      ...1,2,1,2,1,2,1...1,1,2,2,1,1,2,2,1,1,2,2...  

       

Detecting the Order of Marcov Chain in given Sequence using P-value

In previous two posts we have used AIC (Akaiken Information Criterion) and BIC (Bayesian Information Criterion) to find the Markov Chain order of a given sequence. 

One more approach which is easy to scale for higher order is calculating p-values of chi-square using degrees of freedom from given data for orders of our interest. Then based on these p-values decide the order of given sequence.

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

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...

Sequential data analysis

Consider a sequence AABABABBABAB where each occurrence of A or B can be viewed as a state. In the given sequence of length 12 with 2 states we can see 11 transitions. Number of transitions doesn't depend on number of states but length of sequence.

Types of event sequences:

• Event sequence data : Where sequences are recorded independent of their duration. 
• e.g. OSOFSFS (assuming states are O,S,F) 
• Timed event sequence data: Where sequences are recorded with their duration. 
• e.g. OOSSSOOFFSFS (assuming states are O,S,F) 
• Multiple event sequence data: More than one category at a time is possible. 
• e.g. Mother holds infant, infant vocalizes, mother vocalizes.