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

DOI10.1016/J.IPL.2016.09.012zbMATH Open1392.68203OpenAlexW2528195968MaRDI QIDQ344537FDOQ344537

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

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

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)

Cites Work

• Error bounds for convolutional codes and an asymptotically optimum decoding algorithm
• A characterization of the minimum cycle mean in a digraph
• 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)