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

DOI10.1016/J.IPL.2016.09.012MaRDI QIDQ344537zbMATH OpenOpenAlexFDO

Authors Yuri Grinberg, Theodore J. Perkins

Publication date 23 November 2016

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2016.09.012

zbMATH Keywords

computational complexityMarkov chainsgraph algorithms

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Algorithms for determining the state-time probabilities and the limit matrix in Markov chains
• Viterbi sequences and polytopes
• The entropy of Markov trajectories
• scientific article; zbMATH DE number 1029228
• A dynamic programming approach for finite Markov processes and algorithms for the calculation of the limit matrix in Markov chains

Cites work

• A characterization of the minimum cycle mean in a digraph
• Error bounds for convolutional codes and an asymptotically optimum decoding algorithm
• Viterbi sequences and polytopes

Cited in

(2)

• Parametric Markov chains: PCTL complexity and fraction-free Gaussian elimination
• A Polynomial Approximation Algorithm for Real-Time Maximum-Likelihood Estimation

This page was built for publication: Fully polynomial-time computation of maximum likelihood trajectories in Markov chains

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q344537)