Statistical inference in hidden Markov models using k-segment constraints. Eprint arXiv:1311.1189

Hidden Markov models (HMMs) are one of the most widely used statistical methods for analyzing se-quence data. However, the reporting of output from HMMs has largely been restricted to the presentation of the most-probable (MAP) hidden state sequence, found via the Viterbi algorithm, or the sequence of most proba-ble marginals using the forward-backward (F-B) algorithm. In this article, we expand the amount of information we could obtain from the posterior distribution of an HMM by introducing linear-time dynamic programming algorithms that, we collectively call k-segment algorithms, that allow us to i) find MAP sequences, ii) compute posterior probabilities and iii) simulate sample paths conditional on a user specified number of segments, i.e. contiguous runs in a hidden state, possibly of a particular type. We illustrate the utility of these methods using simulated and real examples and highlight the application of prospective and retrospective use of these method