The Markov chain tree theorem and the state reduction algorithm in commutative semirings
arXiv:1312.7094 · doi:10.1016/j.laa.2014.06.028
Abstract
We extend the Markov chain tree theorem to general commutative semirings, and we generalize the state reduction algorithm to commutative semifields. This leads to a new universal algorithm, whose prototype is the state reduction algorithm which computes the Markov chain tree vector of a stochastic matrix.
13 pages