Repository logo
 

On large lag smoothing for hidden markov models

Accepted version
Peer-reviewed

Loading...
Thumbnail Image

Type

Article

Change log

Authors

Houssineau, J 
Jasra, A 
Singh, SS 

Abstract

In this article we consider the smoothing problem for hidden Markov models (HMM). Given a hidden Markov chain {Xn}n≥0 and observations {Yn}n≥0, our objective is to compute E[φ(X0,…,Xk)|y0,…,yn] for some real-valued, integrable functional φ and k fixed, kn and for some realisation (y0,…,yn) of (Y0,…,Yn). We introduce a novel application of the multilevel Monte Carlo (MLMC) method with a coupling based on the Knothe-Rosenblatt rearrangement. We prove that this method can approximate the afore-mentioned quantity with a mean square error (MSE) of O(ϵ2), for arbitrary ϵ>0 with a cost of O(ϵ−2). This is in contrast to the same direct Monte Carlo method, which requires a cost of O(nϵ−2) for the same MSE. The approach we suggest is, in general, not possible to implement, so the optimal transport methodology of \cite{span, parno} is used, which directly approximates our strategy. We show that our theoretical improvements are achieved, even under approximation, in several numerical examples.

Description

Keywords

smoothing, multilevel Monte Carlo, optimal transport

Journal Title

SIAM Journal on Numerical Analysis

Conference Name

Journal ISSN

0036-1429
1095-7170

Volume Title

57

Publisher

Society for Industrial & Applied Mathematics (SIAM)

Rights

All rights reserved
Sponsorship
Alan Turing Institute (unknown)