Evasive random walks and the clairvoyant demon | Zendy

Abrams Aaron | Zendy; Landau Henry | Zendy; Landau Zeph | Zendy; Pommersheim James | Zendy; Zaslow Eric | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

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

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

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research