Deterministic Random Walk on Finite Graphs

Joint ACO and ARC Seminar
Tuesday, January 19, 2016 - 13:05
1 hour (actually 50 minutes)
Skiles 006
Kyushu University
The rotor-router model, also known as the Propp machine, is a deterministic process analogous to a simple random walk on a graph. In this talk, we are concerned with a generalized model, functional-router model, which imitates a Markov chain possibly containing irrational transition probabilities. We investigate the discrepancy of the number of tokens between the functional-router model and its corresponding Markov chain, and give some upper bounds in terms of the mixing time of the Markov chain.