Accelerating Power Methods for Higher-order Markov Chains.

Higher-order Markov chains play a very important role in many fields, ranging from weather forecast to financial modeling. In this paper, we propose two accelerated higher-order power methods for computing the limiting probability distribution of higher-order Markov chains, namely higher-order power method with momentum and higher-order quadratic extrapolation method. The convergence analysis is given for the proposed methods. Numerical experiments show that the new algorithms are more efficient than the existing methods in the literature.