Deterministic Random Walk

点击翻译按钮获取中文摘要

The rotor-router model, which is sometimes called deterministic random walk, is a deterministic process analogous to a random walk on a graph. In this project, we have investigated the rotor-router model, aiming at a new scheme for derandomization of randomized algorithms. While most previous works concerning the rotor-router model dealt with simple random walks on regular graphs, we have proposed some extended models to deal with general transition probability, and have developed techniques for analysis of discrepancies between the models and random walks