In context of a hidden Markov model, I am interested in bounding the error of a Bayesian filter when using inexact state transition and observation models.

Consider a hidden Markov model (HMM) with the set $X = \{1, 2, \ldots, n\}$ of states. At each discrete time step $t\in \mathbb{N}$, the system is in state $x_t \in X$ (which is hidden), and emits an observation $y_t \in Y=\{1,2,\ldots, k\}$ (which is observable) for every $t>0$. After each time step, the state transitions according to a Markov process, as specified by the conditional probabilities $P(x_{t+1} \mid x_t)$. Furthermore, the observation $y_t$ is conditionally independent given $x_t$, governed by the collection of conditional probabilities $Q(y_t \mid x_t)$.

By means of recursive Bayesian filtering, information regarding the hidden state is summarized at each time step by a belief state, or state estimate $\pi_t(x_t) := P(x_{t} \mid y_{1:t})$. Given an initial state estimate $\pi_0$ and any sequence $y_{1:t}$ of past observations, the recursion $$ \pi_{t}(x_{t}) = \frac{1}{\eta(y_{t}\mid \pi_{t-1})}Q(y_{t}\mid x_{t})\sum\limits_{x_{t-1} \in X}P(x_{t}\mid x_{t-1})\pi_{t-1}(x_{t-1}) $$ can be applied to recover the state estimate. The expression above comes from the Bayes' rule and propagating the previous belief according to the Markov chain, while $\eta(y_{t}\mid \pi_{t-1}) := \sum\limits_{x_{t}\in X}Q(y_{t}\mid x_{t})\sum\limits_{x_{t-1} \in X}P(x_{t}\mid x_{t-1})\pi_{t-1}(x_{t-1}) $ is the prior probability of observing $y_t$.

We might also think of $P$ as an $n$-by-$n$ matrix, and similarly of $Q$ as a $k$-by-$n$ matrix having the appropriate conditional probabilities as elements.

Suppose we are given $\pi_0$ and the first observation $y_1$, but instead of $P$ and $Q$ only have access to some approximate versions $\hat{P}$ and $\hat{Q}$ of them. Can I find a bound $\epsilon$ on the $L^1$ norm such that for any $\pi_0$, $$ || \pi_1 - \hat{\pi}_1||_1 \leq \epsilon, $$ where $\pi_1$ and $\hat{\pi}_1$ are the state estimates compute according to the recursion above using $P,Q$ and $\hat{P},\hat{Q}$, respectively? The bound $\epsilon$ would be in terms of some appropriate (matrix) norm between $P,\hat{P}$ and $Q, \hat{Q}$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.