Evasive Random Walks and the Clairvoyant Demon

Aaron Abrams*, Henry Landau, Zeph Landau, James Pommersheim, Eric Zaslow

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

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. Winklers 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.

Original languageEnglish (US)
Pages (from-to)239-248
Number of pages10
JournalRandom Structures and Algorithms
Volume20
Issue number2
DOIs
StatePublished - Mar 1 2002

ASJC Scopus subject areas

  • Software
  • Mathematics(all)
  • Computer Graphics and Computer-Aided Design
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Evasive Random Walks and the Clairvoyant Demon'. Together they form a unique fingerprint.

Cite this