Statistical complexity of the power method for markov chains

AbstractRecently, attention has been focused on the statistical behavior of some of the classical algorithms of numerical and combinatorial analysis. For recent examples, see the work of Smale and others cited in the references. In his thesis, E. Kostlan (1985, “Statistical Complexity of Numerical Linear Algebra,” Thesis, University of California, Berkeley) showed that the average time for convergence of the squaring algorithm of numerical analysis for finding dominant ϵ-eigenvectors of n × n real symmetric and Hermitian matrices is O(log (n − log ϵ)), 0 < ϵ < 1, the average being taken over Gaussian ensembles of such matrices. We prove a complementary result for ensembles of n × n stochastic matrices, to the effect that for a large class of measures, (1 + σ) log (n) + log (− log ϵ) + O(1) iterations suffice with probability 1 − n−σ, where σ 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(n2) steps to reach equilibrium as n tends to ∞