New ways of solving large Markov chains

This article is about solving large Markov chains in a new way. This traditional topic, that is of direct relevance to queueing systems, has been receiving a lot of attention since Google PageRank was introduced in 1998 to rank web pages [4]. PageRank is the stationary distribution of a random walk with restart on the graph of web pages connected by hyperlinks. Most common approach for computing a stationary distribution of a Markov chain, is power iterations (PI), when the initial probability vector is iteratively multiplied by the transition matrix till convergence. Here I will explain a new Red-Light-Green-Light (RLGL) algorithm that we developed with Konstantin Avrachenkov and Patrick Brown [2]. RLGL is fast, and generalizes many methods, including PI, and the state-of-the-art Gauss-Southwell method for PageRank.