Language selection

Government of Canada / Gouvernement du Canada

Search

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

From National Research Council Canada

DOIResolve DOI: https://doi.org/10.1016/j.ipl.2016.09.012
AuthorSearch for: ; Search for:
FormatText, Article
SubjectMarkov 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
PublisherElsevier
In
  • Information Processing Letters 118: 53–57.
LanguageEnglish
Peer reviewedYes
NRC publication
This is a non-NRC publication

"Non-NRC publications" are publications authored by NRC employees prior to their employment by NRC.

NPARC number23003079
Export citationExport as RIS
Report a correctionReport a correction (opens in a new tab)
Record identifieraf470682-a960-4529-80d5-73e80ea70641
Record created2018-04-18
Record modified2020-03-16
Date modified: