## Abstract

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 language | English (US) |
---|---|

Pages (from-to) | 2812-2828 |

Number of pages | 17 |

Journal | SIAM Journal on Numerical Analysis |

Volume | 57 |

Issue number | 6 |

DOIs | |

State | Published - 2019 |

## Keywords

- Multilevel Monte Carlo
- Optimal transport
- Smoothing

## ASJC Scopus subject areas

- Numerical Analysis
- Computational Mathematics
- Applied Mathematics