Premium
Dependent percolation and colliding random walks
Author(s) -
Winkler Peter
Publication year - 2000
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/(sici)1098-2418(200001)16:1<58::aid-rsa5>3.0.co;2-e
Subject(s) - random walk , combinatorics , markov chain , mathematics , lemma (botany) , discrete mathematics , graph , ecology , statistics , poaceae , biology
Let G be a connected, undirected graph and X = X 0 X 1 X 2 ⋅⋅⋅ and Y = Y 0 Y 1 Y 2 ⋅⋅⋅ two simple random walks on G . Let ℕ□ℕ be the nonnegative quadrant of the plane grid, and H the subgraph of ℕ□ℕ induced by the sites ( i , j ) for which X i ≠ Y j . We say that G is “navigable” if with probability greater than 0, the origin belongs to an infinite component of H . We determine which finite graphs are navigable, in particular that K 4 , the complete graph on four nodes, is navigable but K 3 is not. Navigability of G is equivalent to the statement that with positive probability, two tokens taking random walks on G can be moved forward and backward along their paths, and ultimately advanced arbitrarily far, without colliding. The problem is generalized to finite‐state Markov chains, and a complete characterization of navigable chains is given. Similar results have been obtained simultaneously and independently by Balister, Bollobás and Stacey, using different methods; our classification theorem relies on a surprising diamond lemma which may be of independent interest. ©2000 John Wiley & Sons, Inc. Random Struct. Alg., 16, 58–84, 2000