Red light green light method for solving large Markov chains (Q2674164)

Discrete-time discrete-state Markov chains play a very important role in many fields. Often, one key task is to compute the stationary distribution of the corresponding Markov chain. The paper under review proposes a new general method for computing the stationary distribution of a large Markov chain. The method is called red light green light method, since the mechanism mimics a childen's game \textit{Statues}, also called \textit{RLGL (red light, green light)}, where a player, every so often, receives green light to move towards the goal while others stay fit. The new 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. The authors prove exponential convergence of their method, demonstrate its high efficiency, and derive straightforward control strategies that achieve convergence rates faster than state-of-the-art algorithms.