(in the same series HMM (part I): recurrence equations for filtering and prediction)

Consider a Hidden Markov Model (HMM) with hidden states (for ), initial probability , observed states , transition probability and observation model . This model can be factorized as

. We will use the notation to represent the set .

In this post we will present the details of the method to find the smoothing distribution of a HMM, given a set of observations :

Our starting point is the marginal probability of given all the observations .

This marginal can be computed by using dynamic programming to calculate the values of and . Starting with we have

For we have:

Considering a chain of length and number of states, both this recursive calculations can be done in by storing the intermediate results in two vectors and using space (where and are function calculating and respectively). The marginal probability of given the observations can be calculated in .