Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I am looking for advice on the following practical problem. Please keep in mind that this came up in a practical application.

In the context of Markov chains, we have $N$ states, with $N$ very large. (In this application $N$ is on the order of $10^{100000}$ or so.) Every state is reachable from every other state (possibly in more than one step).

We have two transition probability matrices, $A$ and $B$.
I can probably calculate $A_{ij}$ for any two states $i$ and $j$ if needed, but what I can do easily is just propagate the states (simulate the process).

Suppose we start from some arbitrary state and let the system evolve for a very long time, obtaining a state $k$.

Given this state $k$, what is the probability that the system has been evolved using $A$? What is the probability that it was evolved using $B$?

In other words: I can easily simulate both processes on a computer. Given some state $k$, are there practical techniques to find out which of the two processes is more likely to have produced it?

Note: I think this Markov chain is reversible.

(I expect that the question will probably need clarifications once I manage to understand it more deeply. Please help with this.)

share|improve this question
    
It seems like you want to do statistics, not probabilities : you have two hypotheses on a system and you want to determine which one is the more likely. Can you describe the system a little more? –  Julien Puydt Jul 6 '11 at 6:06
    
@Snark, yes, it's similar to that. I'd also like to know how much more likely one hypothesis is than the other. Of the $k$ state, I only have one. The systems are variations on the discrete-time voter model on a 2D grid (modified so as to let it have a steady state in some sense). However, I'd really like to know if there exists some general ways to accomplish this. –  Szabolcs Jul 6 '11 at 7:09

3 Answers 3

In principle, the dominant eigenvector of A and B can be interpreted as a multinomial probability distribution over the states (e.g. pagerank). If you can somehow compute matrix-vector products for A and B, then you might get lucky and be able to approximate these using the power method, with all the usual caveats about the spectrum.

Failing that, I guess you could simulate A and B for as long as possible and count the relative number of occurrences in each state, which should eventually converge to the same thing.

That said, neither case is computationally tractable with such a massive N, and proving that you've converged to the dominant eigenvector within some tolerance would require also finding the sub-dominant eigenvalue. IMHO having such a massive number of states is likely a red flag... I would be tempted to revisit the model :)

share|improve this answer
    
I think this mostly summarizes the situation and everything else is just confusion; if you can calculate the two eigen vectors and assign a distribution to A and B, you can calculate the conditional probability very conventionally. And if you can't do this, you can't anything. –  Joseph Soulbringer Nov 12 '13 at 4:10
    
In fact, if you could calculate the conditional probability here, you could calculate the eigen vectors pretty easily too. So eigen vectors or bust and this is not statistics, FYI. –  Joseph Soulbringer Nov 12 '13 at 4:14

To answer your question, I believe this is statistic and not probability. I believe that using your methodology might fail in practice. In order to have enough data, you will have to make your Markov chain reach many times the state k, then study the length of the process. And chose the smaller one but in a statistical way. That mean, you'll certainly have to reach the state k at least 10 times from both A and B to have some statistically significant solution.

Here is how I'd do it.

The perfect solution would be found using the Baum Welch algorithm. But it would force you to keep in memory $N$ probability value which might be too much.

Why not try the Viterbi algorithm. Each Markov chain is a special case of Hidden Markov Model where the alphabet is the set of states. Then you'll just have to chose:

$$ \arg\max_{X\in \{A,B\}} [1\ 1\ \cdots 1]\cdot X\cdot 1_k$$

I believe this could be achieved using some dynamic programming and you wouldn't have to keep $N$ states in memory (and even less $N^2$ states of the matrix).

I believe that just simulating the process will certainly be far more difficult due to the certainly extremely small probability to reach the state $k$ (about $1/N$).

share|improve this answer
    
Yes, there is about zero chance of reaching state $k$ from some random state due to the huge number of possible states. A state is actually described by a $\sim 100\times 100$ matrix where each element can have $\sim 100-1000$ different values. –  Szabolcs Jul 6 '11 at 7:16

...we have $N$ states, with N very large. (In this application N is on the order of $10^{100000}$ or so.)

Given some state $k$, are there practical techniques to find out which of the two processes is more likely to have produced it?

If your question is whether there is a practical technique to answer your question given only this information then the answer is no. There are sparse matrix techniques that could be helpful when $N$ is reasonably sized but $N^2$ is too big, but when $N$ itself is so unwieldy, you will have to break open the transition matrix black box. In other words you will probably have to use some of the details of your simulation program to answer this question.

share|improve this answer
    
Actually I can calculate any single element of the transition matrix, but of course I cannot calculate all elements at the same time ($N$ is too big). But I think what you said would still apply. –  Szabolcs Feb 7 '12 at 9:14

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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