Fully polynomial-time computation of maximum likelihood trajectories in Markov chains

DOI	Resolve DOI: https://doi.org/10.1016/j.ipl.2016.09.012
Author	Search for: Grinberg, Yuri; Search for: Perkins, Theodore J.
Format	Text, Article
Journal title	Information Processing Letters
ISSN	0020-0190
Volume	118
Pages	53–57
Subject	Markov chains; graph algorithms; computational complexity
Abstract	Given a Markov chain with n states, the initial state, the final state, and the trajectory length t, we consider the problem of finding the most likely trajectory of length t that the chain traversed. This is a well known problem typically addressed by a special case of the Viterbi algorithm, whose computational complexity depends linearly on t, and thus exponentially in the number of bits needed to specify t. In this work, we propose a particular decomposition of the Markov chain into a collection of cycles and walks, computable in polynomial time independent of t. For sufficiently large values of t (>n2+12n(n+1)), the most probable trajectory has a convenient characterization in terms of the above decomposition, and can be computed in time O(n log t).
Publication date	2016-10-04
Publisher	Elsevier
Language	English
Peer reviewed	Yes
NRC publication	This is a non-NRC publication "Non-NRC publications" are publications authored by NRC employees prior to their employment by NRC.
NPARC number	23003079
Export citation	Export as RIS
Report a correction	Report a correction
Record identifier	af470682-a960-4529-80d5-73e80ea70641
Record created	2018-04-18
Record modified	2020-03-16