Premium
Evasive random walks and the clairvoyant demon
Author(s) -
Abrams Aaron,
Landau Henry,
Landau Zeph,
Pommersheim James,
Zaslow Eric
Publication year - 2002
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.999
Subject(s) - random walk , demon , security token , combinatorics , struct , mathematics , graph , discrete mathematics , computer science , statistics , physics , computer security , quantum mechanics , programming language
Abstract 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