Is there a concise mathematical form for the probability of ending up in a given state of an HMM?

Question

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.

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.