Statistical complexity of the power method for Markov chains

DOI10.1016/0885-064X(89)90001-0MaRDI QIDQ1122306zbMATH OpenFDO

Authors Paul Wright

Publication date 1989

Published in Journal of Complexity (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0885-064X(89)90001-0

zbMATH Keywords

convergencedominant eigenvectorsMarkov chainspower methodsquaring algorithmstatistical complexitystochastic matricessymmetric and Hermitian matrices

Mathematics Subject Classification ID

Stochastic matrices (15B51) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Numerical computation of eigenvalues and eigenvectors of matrices (65F15)

Review text

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\).

Recommendations

• scientific article; zbMATH DE number 510826
• Finding the stationary states of Markov chains by iterative methods
• On "Sluggish Transients" in Markov Chains
• On time of convergence to the equilibrium in large finite Markov chains
• Statistical complexity of dominant eigenvector calculation

Cites work

• Computational Complexity: On the Geometry of Polynomials and a Theory of Cost: II
• Bounds for eigenvalues of certain stochastic matrices
• scientific article; zbMATH DE number 3172038 (Why is no real title available?)
• scientific article; zbMATH DE number 3880432 (Why is no real title available?)
• scientific article; zbMATH DE number 3824228 (Why is no real title available?)
• scientific article; zbMATH DE number 1234098 (Why is no real title available?)
• scientific article; zbMATH DE number 503393 (Why is no real title available?)
• scientific article; zbMATH DE number 3437452 (Why is no real title available?)
• scientific article; zbMATH DE number 3223982 (Why is no real title available?)
• scientific article; zbMATH DE number 3230499 (Why is no real title available?)
• scientific article; zbMATH DE number 3399886 (Why is no real title available?)
• Non-negative matrices and Markov chains.
• On the average number of steps of the simplex method of linear programming
• On the efficiency of algorithms of analysis
• On the time taken by random walks on finite groups to visit every state
• The fundamental theorem of algebra and complexity theory

Cited in

(6)

• Statistical complexity of dominant eigenvector calculation
• The ensemble of random Markov matrices
• Power of discrete scan statistics: a finite Markov chain imbedding approach
• Iterative rank-one matrix completion via singular value decomposition and nuclear norm regularization
• Markov power min-moment problem with periodic gaps
• Asymptotic behavior of eigenvalues and random updating schemes

This page was built for publication: Statistical complexity of the power method for Markov chains

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1122306)