Large Deviation Bounds for Functionals of Viterbi Paths

Autor:	Alexander Roitershtein, Elizabeth Kleiman, Arka P. Ghosh
Rok vydání:	2011
Předmět:	Mathematical optimization Iterative Viterbi decoding Markov chain Stochastic process Markov process Estimator Library and Information Sciences Viterbi algorithm Computer Science Applications symbols.namesake symbols Applied mathematics Almost surely Forward algorithm Information Systems Mathematics
Zdroj:	IEEE Transactions on Information Theory. 57:3932-3937
ISSN:	1557-9654 0018-9448
Popis:	In a number of applications, the underlying stochastic process is modeled as a finite-state discrete-time Markov chain that cannot be observed directly and is represented by an auxiliary process. The maximum a posteriori (MAP) estimator is widely used to estimate states of this hidden Markov model through available observations. The MAP path estimator based on a finite number of observations is calculated by the Viterbi algorithm, and is often referred to as the Viterbi path. It was recently shown in, and, (see also and) that under mild conditions, the sequence of estimators of a given state converges almost surely to a limiting regenerative process as the number of observations approaches infinity. This in particular implies a law of large numbers for some functionals of hidden states and finite Viterbi paths. The aim of this paper is to provide the corresponding large deviation estimates.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::01b32045de9d66523e497901657da259 https://doi.org/10.1109/tit.2011.2132550 Zobrazit plný text záznamu