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. The authors 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. The authors use a novel potential function argument to show that in the worst case M = (4/27 + o(1))n3.