# Markov chains that do not contain all the states in the model

I am trying to understand Mixture Markov Models in order to cluster a set of sequences that do not necessarily all have the same states occurring in them.

If I have several sequences that I am trying to fit a Mixture Markov Model to, how do I go about the fact that some of the chains contain a part of all possible states while the others might contain other states? For example:

sequence 1: 1 2 4 2 4 1

sequence 2: 3 2 3 3 3 3

sequence 3: 1 2 3 1 1 2

How would I define a transition probability matrix for each of the sequences, given that the set of possible states is {1,2,3,4}? In the context of Mixture Markov Modeling, shouldn't a transition probability matrix be 4x4 and contain transfer probabilities for each state from the collection -> each state of the collection?

Take for instance sequence1:

My understanding is that the TPM of sequence1 should be:

   1   2   3   4

1  0.5 0.5 0   0

2  1   0   0   0

3  0   0   0   0

4  0.5 0.5 0   0


This seems to be incorrect, since TPM is a stochastic matrix whose rows sum up to 1, and the third row is just all 0s. Should I completely remove state 3 if I am building a transition probability matrix of a specific sequence?

The reason I need to have a Markov chain for each sequence is that I am trying to calculate log-likelihood distance between each two sequences in order to build a distance matrix and get medoids for initializing the Mixture Markov Model.

The formula for distance that I am trying to use is:

$D(seq_i,seq_j)=1/2* log(p(seq_i|v_j)+p(seq_j|v_i))$, where

$v_i,v_j$ are the Markov Chains representing the sequences $seq_i$ and $seq_j$ correspondingly.

How would I define sequences 1,2,3 in terms of their transition probability matrices and single ML-estimated Markov chains representing each sequence?

• You're right that a transition matrix should include all probabilities for transitioning between all states in a Markov process. And, your TPM for the first sequence is also correct - those are the transition probabilities for that sequence. In sequence 1, there is never a transition to or from the 3rd state (3 in this case). To get TPMs for all 3 sequences, repeat the procedure you used to create the TPM for sequence 1. Aug 20, 2013 at 17:05
• @learner, thank you for your answer. I guess I need to understand better how to work with such matrices. Because if the matrix is like this, there will be some "funny" log-likelihood distances between sequences (e.g. -Infinity). How would I even cluster the sequences according to this?
– zima
Aug 21, 2013 at 9:29
• At least in the context of information theory, it is accepted that the log of 0 can be replaced with 0 (so that, say, variables with no entropy have 0 entropy instead of -Inf). You could define some replacement value to replace -Inf, or you could replace the 0's with some arbitrarily small value, such as 1e-17. Aug 21, 2013 at 12:03
• hm, but in the sense of "distance" where i am assuming 0 is the smallest distance ( and the more negative the log measure is the farther the distance), to equate log(0) to 0 would mean distance between two completely different sequences would be 0. The approach of replacing -Inf by a very small number seems appealing to me - would it not interfere with the future results if the transition matrices will have a "technically" non-zero probability where it should be zero? Is this trick an acceptable move for machine learning/model fitting problems?
– zima
Aug 21, 2013 at 16:10
• @learner, if you don't mind answering one more doubt that I have - don't the rows of stochastic matrix have to sum to 1? if i have one row of almost zeros, would that even be a proper transition matrix?
– zima
Aug 22, 2013 at 9:32

## 1 Answer

Just to summarize, if you substitute your 0 values with some very small value such as 1e-17, your impossible states will still be the furthers apart. As you are trying to derive some sort of ordering of your data, it doesn't matter whether your smallest value is -Inf or -39, as either number will be the smallest value in the dataset.

• if you don't mind answering, I have one more follow-up question.. I have noticed that by using such values, my sum of transition matrix rows can sometimes go over 1 ( and I think this is the reason why sometimes I get corresponding Dirichlet priors larger than 1).. How do I address that? Reduce the relative probabilities of the other transitions to accomodate assigning very small values instead of 0 to these 0-chance probabilities? Please correct me if I am wrong.
– zima
Aug 29, 2013 at 13:55
• You could try adjusting the remaining probabilities - $(0.5 - (1*10^{-17}))$ should be very close to $0.5$. Aug 30, 2013 at 15:07