7
$\begingroup$

I am constructing Markov chains (with 100 to 200 states) and inferring transition probabilities empirically by simply counting how many times I saw each transition in my raw data (about 20k to 60k transitions per data set). Note that the modest number of transitions and the decent number of state results in average number of measurements per edge being between 1 and 12, thus the errors on most of the inferred transition probabilities are decently high.

From each data set, I construct a Markov chain. Given two Markov chains, I want a statistical test that will tell me if they are the same or not (both trying to approximate the same unknown 'true' Markov chain, or two different ones). Any advice? Any exiting code for this (preferably in Matlab, but R is fine)?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ Estimating the transition matrix from the empirical transitions is terrible if you need to simulate from the estimated matrix, because this induces a lot of zeros. Bayesian estimates are superior in this respect because no entry is zero... $\endgroup$
    – Xi'an
    Feb 1, 2012 at 21:15

2 Answers 2

Reset to default
2
$\begingroup$

Since the two chains are assumed to be comparable, they should have the same state space. That leaves the transition matrices, comparing which can be done by a divergence-based hypothesis test, as explained on pg. 139 of Statistical inference based on divergence measures By Leandro Pardo Llorente

Improve this answer
$\endgroup$
-1
$\begingroup$

Here's half-baked idea. Please tell me why it's wrong. :)

  1. Choose randomly a state sequence from dataset A, and leave it out when constructing the chain for that dataset.
  2. Construct the chains for datasets A and B.
  3. Run the sequence through chains A and B, and record the predicted final state.
  4. Repeat 1-3 lots of times.
  5. Report the percentage of times that the chains predict the same final state.
Improve this answer
$\endgroup$
2
  • $\begingroup$ these are chains, not MDPs, there are no actions. Thus you can't 'run a sequence through' the chain. The only thing you can do is calculate the probability of the sequence occurring given the chain. $\endgroup$
    – Artem Kaznatcheev
    Feb 1, 2012 at 17:11
  • $\begingroup$ Right, so change (3) to calculate the probability of the sequence occurring given the chain. The two chains are similar to the extent that the probabilities they give to each sequence are correlated. $\endgroup$
    – Jack Tanner
    Feb 2, 2012 at 19:26

Your Answer

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

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