Statistical complexity of the power method for Markov chains
type: Item
instance of: scholarly article
title: Statistical complexity of the power method for Markov chains
zbMATH Open document ID: 0675.65027
DOI: 10.1016/0885-064X(89)90001-0
author: Paul Wright
published in: Journal of Complexity
publication date: 1989-01-01T00:00:00Z
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\).
Mathematics Subject Classification ID: 65F15
Mathematics Subject Classification ID: 60J10
Mathematics Subject Classification ID: 15B51
zbMATH DE Number: 4106128
zbMATH Keywords: statistical complexity
zbMATH Keywords: power method
zbMATH Keywords: dominant eigenvectors
zbMATH Keywords: convergence
zbMATH Keywords: squaring algorithm
zbMATH Keywords: symmetric and Hermitian matrices
zbMATH Keywords: stochastic matrices
zbMATH Keywords: Markov chains
reviewed by: Prem Narain
MaRDI profile type: MaRDI publication profile
cites work: On the time taken by random walks on finite groups to visit every state
cites work: Q5512461
cites work: Q3671491
cites work: Q4279732
cites work: Bounds for eigenvalues of certain stochastic matrices
cites work: Q5518575
cites work: Q4221096
cites work: Q4405392
cites work: Q5667036
cites work: Non-negative matrices and Markov chains.
cites work: Computational Complexity: On the Geometry of Polynomials and a Theory of Cost: II
cites work: The fundamental theorem of algebra and complexity theory
cites work: On the average number of steps of the simplex method of linear programming
cites work: Q3346084
cites work: On the efficiency of algorithms of analysis
cites work: Q3290778
Recommended article: Q4281293
Recommended article: Finding the stationary states of Markov chains by iterative methods
Recommended article: On "Sluggish Transients" in Markov Chains
Recommended article: On time of convergence to the equilibrium in large finite Markov chains
Recommended article: Statistical complexity of dominant eigenvector calculation
description: scientific article; zbMATH DE number 4106128