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

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(nlog⁡t).