Red Light Green Light Method for Solving Large Markov Chains

Konstantin Avrachenkov*, Patrick Brown, Nelly Litvak

*Corresponding author for this work

Research output: Contribution to journalArticleAcademicpeer-review

1 Downloads (Pure)


Discrete-time discrete-state finite Markov chains are versatile mathematical models for a wide range of real-life stochastic processes. One of most common tasks in studies of Markov chains is computation of the stationary distribution. We propose a new general controlled, easily distributed algorithm for this task. The algorithm includes as special cases a wide range of known, very different, and previously disconnected methods including power iterations, versions of Gauss-Southwell formerly restricted to substochastic matrices, and online distributed algorithms. We prove exponential convergence of our method, demonstrate its high efficiency, and derive straightforward control strategies that achieve convergence rates faster than state-of-the-art algorithms.
Original languageEnglish
Article number18
Pages (from-to)1-43
Number of pages43
JournalJournal of scientific computing
Issue number18
Early online date30 Aug 2022
Publication statusPublished - Oct 2022


  • Markov Chains
  • Numerical methods
  • Gauss-Southwell methods
  • Coupling
  • 22/3 OA procedure


Dive into the research topics of 'Red Light Green Light Method for Solving Large Markov Chains'. Together they form a unique fingerprint.

Cite this