Convergence of a Second Order Markov Chain

In this paper, we consider convergence properties of a second order Markov chain. Similar to a column stochastic matrix is associated to a Markov chain, a so called em transition probability tensor P of order 3 and dimension n is associated to a second order Markov chain with n states. For this P, define FP as FP(x):=Px2 on the n-1 dimensional standard simplex Deltan. If 1 is not an eigenvalue of nabla FP on Deltan and P is irreducible, then there exists a unique fixed point of FP on Deltan. In particular, if every entry of P is greater than frac12n, then 1 is not an eigenvalue of nabla FP on Deltan. Under the latter condition, we further show that the second order power method for finding the unique fixed point of FP on Deltan is globally linearly convergent and the corresponding second order Markov process is globally R-linearly convergent.