Probability that a certain Markov process has produced a given state

Question

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

Answer 1

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 :)

Answer 2

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

Answer 3

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