Statistical complexity of the power method for Markov chains
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\).
scientific article; zbMATH DE number 4106128
scientific article