## Markov Chain Sampling for Non-linear State Space Models
Using Embedded Hidden Markov Models

**Radford M. Neal,
Dept. of Statistics and Dept. of Computer Science, University of Toronto**

I describe a new Markov chain method for
sampling from the distribution of the state sequences in a non-linear
state space model, given the observation sequence. This method
updates all states in the sequence simultaneously using an embedded
Hidden Markov model (HMM). An update begins with the creation of a
``pool'' of *K* states at each time, by applying some Markov chain
update to the current state. These pools define an embedded HMM whose
states are indexes within this pool. Using the forward-backward
dynamic programming algorithm, we can then efficiently choose a state
sequence at random with the appropriate probabilities from the
exponentially large number of state sequences that pass through states
in these pools. I show empirically that when states at nearby times
are strongly dependent, embedded HMM sampling can perform better than
Metropolis methods that update one state at a time.

Technical Report No. 0304, Dept. of Statistics, University of Toronto
(April 2003), 9 pages:
postscript,
pdf.

Also available
from arXiv.org.

**Associated reference:**
Further developments regarding embedded HMM sampling are reported in
the following conference paper:
Neal, R. M., Beal, M. J., and Roweis, S. T. (2004) ``Inferring state sequences
for non-linear systems with embedded hidden Markov models'', in S. Thrun,
et al (editors), *Advances in Neural Information Processing Systems 16*
(aka NIPS*2003), MIT Press, 8 pages:
abstract,
postscript,
pdf.