99bcfcd754a98ce89cb86f73acc04645-Reviews.html

This paper introduces a new randomized algorithm for deciding properties of the stationary distribution of discrete time, irreducibile, aperiodic, positive recurrent Markov Chains (MC). Specifically, it considers the problem of deciding whether a state of a MC has a probability (according to the stationary distribution) that is larger than some threshold. The idea is to estimate this probability by running a sequence of random walks from the state, truncated at geometrically increasing length thresholds. The length of these random walks is used to estimate the return time, which is then used to estimate the stationary probability. Some correctness and convergence properties of the algorithm are proved by the authors, and are evaluated in simulation for a PageRank and an MM1 queue MC. This is mainly a theoretical paper.