On large lag smoothing for hidden markov models

Jeremie Houssineau, Ajay Jasra, Sumeetpal S. Singh

Research output: Contribution to journalArticlepeer-review


In this article we consider the smoothing problem for hidden Markov models. Given a hidden Markov chain { Xn} n≥ 0 and observations { Yn} n≥ 0, our objective is to compute E[varphi (X0, . ,Xk)| y0, . , yn] for some real-valued, integrable functional varphi and k fixed, k ll n and for some realization (y0, . , yn) of (Y0, . , Yn). We introduce a novel application of the multilevel Monte Carlo method with a coupling based on the Knothe-Rosenblatt rearrangement. We prove that this method can approximate the aforementioned quantity with a mean square error (MSE) of scrO (∈-2) for arbitrary ∈ > 0 with a cost of scrO (∈-2). This is in contrast to the same direct Monte Carlo method, which requires a cost of scrO (n∈-2) for the same MSE. The approach we suggest is, in general, not possible to implement, so the optimal transport methodology of [A. Spantini, D. Bigoni, and Y. Marzouk, J. Mach. Learn. Res., 19 (2018), pp. 2639-2709; M. Parno, T. Moselhy, and Y. Marzouk, SIAM/ASA J. Uncertain. Quantif., 4 (2016), pp. 1160-1190] is used, which directly approximates our strategy. We show that our theoretical improvements are achieved, even under approximation, in several numerical examples.

Original languageEnglish (US)
Pages (from-to)2812-2828
Number of pages17
JournalSIAM Journal on Numerical Analysis
Issue number6
StatePublished - 2019


  • Multilevel Monte Carlo
  • Optimal transport
  • Smoothing

ASJC Scopus subject areas

  • Computational Mathematics
  • Applied Mathematics
  • Numerical Analysis


Dive into the research topics of 'On large lag smoothing for hidden markov models'. Together they form a unique fingerprint.

Cite this