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

Markov Chain : Concept and application

It is a stochastic process used to model random progression of a system mathematically. Stochastic process is a process which is used to describe behavior of a random variable (system) over the time. Random progression refers to transition between states which are part of the system we are studying.

Consider a sequence of two states A and A' as ...AA'A'AA'AAA'A... in which the transition between A and A' can be captured by following matrix,

There are two important things in the screenshot above,

• On left side we can see the transition diagram between A and A' where the probabilities are shown for each possible transition. Note that sum all numbers associated with outgoing arrows for any state must be 1. For example in state A, sum of 0.9 and 0.1 is 1.00.
• On right side the same transitions are captured by a transition probability matrix. Note that sum of any row here must be 1. For example, consider the row with current state as A' where sum of 0.7 and 0.3 is 1.00 as those are only possible transitions for A'.