Evasive random walks and the clairvoyant demon
Aaron D. Abrams, Henry Landau, Zeph A. Landau, James Pommersheim, Eric Zaslow · Random Structures and Algorithms · 2002
A pair of random walks (R, S) on the vertices of a graph G is successful if two tokens moving one at a time can be scheduled (moving only one token at a time) to travel along R and S without colliding. We consider questions related to P. Winkler's clairvoyant demon problem, which asks whether for random walks R and S on G, Pr[(R, S)is successful] >0. We introduce the notion of an evasive walk on G: a walk S so that for a random walk R on G, Pr[(R, S)is successful] >0. We characterize graphs G having evasive walks, giving explicit constructions on such G. Also, we show that on a cycle, the tokens must collide quickly with high probability. © 2002 Wiley Periodicals, Inc. Random Struct. Alg. 20: 220–229, 2002