I have an HMM where I know (or at least have estimated) the transition properties. I also know the starting state. I'm interested in knowing the probability that I end up in a given state "much later". By "much later", I mean that I'm not sure exactly how many transitions later...maybe I'd like to compute the probability of each state on some grid of "how many transitions later", like [100, 500, 1000].

I know I can run many instances of the HMM in silico and simply count up where each simulation ends after 100, 500, and 1000 transitions. But is there a more concise way to do this? For example, if there are too many states to store in memory, or the number of transitions is such that it would take a long time to simulate.


1 Answer 1


This can be found using the forward algorithm. Essentially, the forward algorithm is an efficient way to compute the probability of all of the observations and a state.

$\mathbb{P}(x_1, ... ,x_n, z_n)$

It does this by summing over all possible paths to a particular time step (marginalizing out the hidden variables up to that point). If you can imagine an HMM as a lattice of length $N$ and height $T$ where $T$ is the number of states, then the forward algorithm sums over all posssible paths through the lattice.


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.