5
$\begingroup$

I collected some sequences of events, e.g. a,b,c a,a,a,c,a,b,b c,b,b,c,a b,c,a a,b,c,a Each event has a certain probability to create the next event, but later events do not depend on other events than the one before, e.g. the graph that can be constructed from the data has the markov property.

From this data a transition matrix can be calculated:

$$ P = \left( \begin{array}{ccc} 0.33 & 0.5 & 0.16\\ 0 & 0.33 & 0.66 \\ 0.8 & 0.2 & 0 \end{array} \right) $$

(if i did not miscalculated anything...)

When I now get a new sequence, is it possible to calculate the probability that this sequence is similar to previous sequences?

Can I just multiply the transition probabilities for a new sequence? For example a,b,b would give me $0.5 \cdot 0.33$?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ I think if you want similarity you need to derive a new matrix P2 and then define a metric to compare P and P2. Just multiplying probabilities will go towards 0 if you have long sequences (especially if you have 0 prob in it). $\endgroup$
    – Dirk Nachbar
    Commented Nov 24, 2016 at 14:36
  • $\begingroup$ also see stats.stackexchange.com/questions/38014/… and math.stackexchange.com/questions/86331/… $\endgroup$
    – Dirk Nachbar
    Commented Nov 24, 2016 at 14:37
  • $\begingroup$ @DirkNachbar In the second link there is a formular for the likelihood. But this is exactly what i did? $\endgroup$
    – reox
    Commented Nov 24, 2016 at 14:43

1 Answer 1

Reset to default
1
$\begingroup$

It seems like you're asking two questions here --

Question 2 (The simpler one): Assuming a Markov chain, is the probability of a sequence x,y,z equal to the product of the transition probabilities i.e. p(y|x)*p(z|y)? The answer is yes.

Question 1: How can you tell if the sequences you generate are similar to the sequences you started with? Or in other words, is a Markov chain really a good model for the data you have? This is not quite as simple.

The way I would do it is to generate a large number of sequences from your transition matrix, find the probability of each one, and then plot a histogram of those probabilities. Then take the sequences from your original data, find the probabilities of THOSE (in your transition matrix) and see where they fall, relative to your histogram. (Make sure you're only comparing sequences of the same length, in a given test, because different-length sequences will very different probabilities.) Doing this, you can see if the simulated sequences look "similar" (in one way) to the original sequences, and actually set up the comparison as a test. If your data falls outside of 95% of the histogram, you can reject the hypothesis that a Markov model is a good model for the original sequences.

At least I think you can -- this seems intuitively right to me, although I also have the vague suspicion I'm abusing the concepts.

Improve this answer
$\endgroup$
4
  • $\begingroup$ The histogram seems like a good idea! to generate the data is another story (but not part of this problem). I wonder if there is any formalism behind that. But i looked now for quite a while and did not found anything useful... maybe I'm just missing the right words to search for... $\endgroup$
    – reox
    Commented Nov 24, 2016 at 15:04
  • $\begingroup$ I thought about that idea and there is something bugging me: Each histogram for a certain sequence length will be the same shape but more shifted towards zero, because the probabilities for the transition are not influenced by the length of the sequence. maybe there is even a linear relationship to that... Maybe it is enough to know the distribution function and be able to create critical values for rejection ranges. $\endgroup$
    – reox
    Commented Nov 24, 2016 at 15:11
  • $\begingroup$ I don't have an intuition about what longer-sequence distributions would look like -- is that your intuition, or can you show it? And I certainly admit there may be non-simulation approaches, but that is the one I could think of. $\endgroup$
    – one_observation
    Commented Nov 24, 2016 at 15:45
  • $\begingroup$ So i did some tests and the data shows the following: First of all i logarithmized the data (sequences and probabilties). The data itself is very non-linear but logarithmized it looks quite good. Then i can see that the sequence length is correlated to the probability (in my case $y = 2.54 - 0.006237x$) - so there you have the relationship between length and probability. The distr. of $-log(p(x,y))$ is an exponential function like $e^{-\lambda x}$. So it could work ;) But I'm far from having a mathematical proove on hand $\endgroup$
    – reox
    Commented Nov 25, 2016 at 9:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.