On the sequence of powers of a stochastic matrix with large exponent

We consider the class of primitive stochastic n x n matrices A, whose expon ent is at least [(n(2) - 2n + 2)/2] + 2. It is known that for such an A, th e associated directed graph has cycles of just two different lengths, say k and j with k > j, and that there is an alpha between 0 and 1 such that the characteristic polynomial of A is lambda(n) - alpha lambda(n-j) - (1 - alp ha)lambda(n-k). In this paper, we prove that for any m greater than or equa l to n, if alpha less than or equal to 1/2, then \\ A(m+k) _ A(m)\\infinity less than or equal to \\ A(m) - 1w(T)\\infinity, where 1 is the all-ones v ector and w(T) is the left-Perron vector for A, normalized so that w(T)1 = 1. We also prove that if j greater than or equal to n/2, n greater than or equal to 31 and alpha > (-9 + 3 root 17/4, then \\ A(m+j) _ A(m) \\infinity less than or equal to \\ A(m) - 1w(T)\\infinity for all sufficiently large m. Both of these results lead to lower bounds on the rate of convergence o f the sequence A(m). (C) 2000 Elsevier Science Inc. All rights reserved.