Dependent percolation and colliding random walks

✍ Scribed by Peter Winkler

• Publisher: John Wiley and Sons
• Year: 2000
• Tongue: English
• Weight: 315 KB
• Volume: 16
• Category: Article
• ISSN: 1042-9832
• DOI: 10.1002/(sici)1098-2418(200001)16:1<58::aid-rsa5>3.0.co;2-e

✦ Synopsis

Let G be a connected, undirected graph and

Let N N be the nonnegative quadrant of the plane grid, and H the subgraph of N N 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.