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

       
               

So in other words for homogeneous chains, if we divide the original chain in multiple segments the transition probability matrices should be almost same.

The examples above are pretty simple due only two states (1, 2) and short length. Imagine sequence with 36 states and length of 20,000+. How can we check if the given sequence is homogeneous or not?

Well researcher have already published few papers regarding the same. One of the possible way to detect Time-homogeneity is 

• Divide the sequence in multiple segments
• Find the transition probability matrix for each
• Based on these matrices do chi-squared test 
• Get p-value for the test to see if there is significant difference in the distribution
• Repeat the process few times by changing number of segments

The code for checking time-homogeneity can be found below.