Collisions among Random Walks on a Graph

A token located at some vertex v of a connected, undirected graph G on n vertices is said to be taking a "random walk" on G if, whenever it is instructed to move, it moves with equal probability to any of the neighbors of v. We consider the following problem: suppose that two tokens are placed on G, and at each tick of the clock a certain demon decides which of them is to make the next move. The demon is trying to keep the tokens apart as long as possible. What is the expected time M before they meet? The problem arises in the study of self-stabilizing systems, a topic of recent interest in distributed computing. Since previous upper bounds for M were exponential in n, the issue was to obtain a polynomial bound. We use a novel potential function argument to show that in the worst case M = \Gamma 4 27 + o(1) \Delta n 3 . 1 Introduction Let G be a connected graph on n vertices, and let v be a fixed vertex of G. A random walk on G, beginning at v, is a stochastic process whose stat..