Exact Bayesian Prediction in a Class of Markov-switching Models

Jump-Markov state-space systems (JMSS) are widely used in statistical signal processing. However as is well known Bayesian restoration in JMSS is an NP-hard problem, so in practice all inference algorithms need to resort to some approximations. In this paper we focus on the computation of the conditional expectation of the hidden variable of interest given the available observations, which is optimal from the Bayesian quadratic risk viewpoint. We show that in some stochastic systems, namely the Partially Pairwise Markov-switching Chains (PPMSC) and Trees (PPMST), no approximation scheme is actually needed since the conditional expectation of interest (be it either in a filtering or prediction problem) can be computed exactly and in a number of operations linear in the number of observations.