Finding the stationary states of Markov chains by iterative methods

Nesterov, Yurii;Nemirovski, Arkadi
(2015) Applied Mathematics and Computation — Vol. 255, p. 58-65 (2015)

Files

document.pdf
  • Restricted Access
  • Adobe PDF
  • 323.55 KB
Request a copy

Details

Authors
  • Nesterov, YuriiUCLouvain
    Author
  • Nemirovski, Arkadi
    Author
Abstract
In this paper, we develop new methods for approximating dominant eigenvector of column-stochastic matrices. We analyze the Google matrix, and present an averaging scheme with linear rate of convergence in terms of 1-norm distance. For extending this convergence result onto general case, we assume existence of a positive row in the matrix. Our new numerical scheme, the Reduced Power Method (RPM), can be seen as a proper averaging of the power iterates of a reduced stochastic matrix. We analyze also the usual Power Method (PM) and obtain convenient conditions for its linear rate of convergence with respect to 1-norm.
Affiliations

Citations

  • APA
  • Chicago
  • FWB

Nesterov, Y., & Nemirovski, A. (2015). Finding the stationary states of Markov chains by iterative methods. Applied Mathematics and Computation, 255, 58-65. https://doi.org/10.1016/j.amc.2014.04.053 (Original work published 2015)