Finite State-Spaces and Hidden Markov Models
Nicolas Chopin, Omiros Papaspiliopoulos · Springer series in statistics · 2020
SummaryThis short chapter considers the special case where the state-space of the considered model is finite; \(\mathcal {X}=\{1,\ldots ,K\}\). In that case the integrals of the forward and backward recursions become sums over K terms, which can be computed exactly at a cost that is shown to be \(\mathcal {O}(TK^2)\). State-space models with a finite state-space model are usually called hidden Markov models. Applying the generic algorithm to their “bootstrap” Feynman-Kac formalisation yields an exact algorithm known as the forward-backward algorithm.