Sélection de la langue

Gouvernement du Canada / Government of Canada

Recherche

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

Par Conseil national de recherches du Canada

DOITrouver le DOI : https://doi.org/10.1016/j.ipl.2016.09.012
AuteurRechercher : ; Rechercher :
FormatTexte, Article
SujetMarkov chains; graph algorithms; computational complexity
Résumé
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).
Date de publication
Maison d’éditionElsevier
Dans
  • Information Processing Letters 118 : 53–57.
Langueanglais
Publications évaluées par des pairsOui
Publication du CNRC
Cette publication n’est pas du CNRC

Ce sont des publications qui ont été rédigées par un auteur du CNRC, mais avant que celui-ci soit employé du CNRC.

Numéro NPARC23003079
Exporter la noticeExporter en format RIS
Signaler une correctionSignaler une correction (s'ouvre dans un nouvel onglet)
Identificateur de l’enregistrementaf470682-a960-4529-80d5-73e80ea70641
Enregistrement créé2018-04-18
Enregistrement modifié2020-03-16
Date de modification :