Fully polynomial-time computation of maximum likelihood trajectories in Markov chains
详细信息 查看全文
- 作者：Yuri Grinberga ; 1 ; yuri.grinberg@mail.mcgill.ca" class="auth_mail" title="E-mail the corresponding author ; Theodore J. Perkinsa ; b ; tperkins@ohri.ca" class="auth_mail" title="E-mail the corresponding author
- 关键词：Markov chains ; Graph algorithms ; Computational complexity
- 刊名：Information Processing Letters
- 出版年：2017
- 出版时间：February 2017
- 年：2017
- 卷：118
- 期：Complete
- 页码：53-57
- 全文大小：254 K
文摘
- •
The problem of finding a maximum likelihood trajectory in a Markov chain of a given length is considered.
- •
A decomposition of the Markov chain, seen as a directed weighted graph, is proposed based on the mean-weight cycle analysis.
- •
The proposed decomposition makes it possible to design a polynomial-time algorithm to address the above problem.