  Filtering---estimating the state of a partially observable Markov process
from a sequence of observations---is one of the most widely studied problems in
control theory, AI, and computational statistics. Exact computation of the
posterior distribution is generally intractable for large discrete systems and
for nonlinear continuous systems, so a good deal of effort has gone into
developing robust approximation algorithms. This paper describes a simple
stochastic approximation algorithm for filtering called {em decayed MCMC}. The
algorithm applies Markov chain Monte Carlo sampling to the space of state
trajectories using a proposal distribution that favours flips of more recent
state variables. The formal analysis of the algorithm involves a generalization
of standard coupling arguments for MCMC convergence. We prove that for any
ergodic underlying Markov process, the convergence time of decayed MCMC with
inverse-polynomial decay remains bounded as the length of the observation
sequence grows. We show experimentally that decayed MCMC is at least
competitive with other approximation algorithms such as particle filtering.

Artificial Intelligence;Machine Learning;Systems and Control