Statistical complexity of the power method for Markov chains (Q1122306)

Recently it was shown that the average time for convergence of the squaring algorithm of numerical analysis for finding dominant \(\epsilon\)- eigenvectors of \(n\times n\) real symmetric and Hermitian matrices is O(log(n-log \(\epsilon)\)), \(0<\epsilon <1\), the average being taken over Gaussian ensembles of such matrices. In this paper the author proves a complementary result for ensembles of \(n\times n\) stochastic matrices, to the effect that for a large class of measures, \((1+\delta)\log n+\log (- \log \epsilon)+O(1)\) iterations suffice with probability \(>1-n^{- \delta}\), where \(\delta\) is an arbitrary positive constant. This result has a direct translation which says that with asymptotically rare exceptions, Markov chains of size n require roughly at most \(O(n^ 2)\) steps to reach equilibrium as \(n\to \infty\).