Dependent Percolation and Colliding Random Walks

Let G be a connected, undirected graph and X = X sub 0 X sub 1 X sub 2... and Y = Y sub 0 Y sub 1 Y sub 2... two simple random walks on G. Let NboxN be the non-negative quadrant of the plane grid, and H the subgraph of NboxN induced by the sites (i, j) for which X sub i =/ Y sub 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 sub 4, the complete graph on four nodes, is navigable but K sub 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, Bollobas and Stacey, using different methods; our classification theorem relies on a surprising diamond lemma which may be of independent interest.