  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. Without loss of generality, and drawing our motivation from
applications to large networks, we interpret this problem as one of computing
the stationary distribution of a random walk on a graph. We propose a new
controlled, easily distributed algorithm for this task, briefly summarized as
follows: at the beginning, each node receives a fixed amount of cash (positive
or negative), and at each iteration, some nodes receive `green light' to
distribute their wealth or debt proportionally to the transition probabilities
of the Markov chain; the stationary probability of a node is computed as a
ratio of the cash distributed by this node to the total cash distributed by all
nodes together. Our method includes as special cases a wide range of known,
very different, and previously disconnected methods including power iterations,
Gauss-Southwell, and online distributed algorithms. We prove exponential
convergence of our method, demonstrate its high efficiency, and derive
scheduling strategies for the green-light, that achieve convergence rate faster
than state-of-the-art algorithms.
