Opening book details…
Can I read Dependent Percolation and Colliding Random Walks on EtoBox?
Dependent Percolation and Colliding Random Walks by Peter Winkler is a Mathematics article available to read on EtoBox.
What is Dependent Percolation and Colliding Random Walks about?
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.
Who reads Dependent Percolation and Colliding Random Walks?
It is typically read by researchers, students, and practitioners in Mathematics.
- Author
- Peter Winkler
- Publisher
- John Wiley and Sons; Wiley (John Wiley & Sons); John Wiley & Sons Inc.; Wiley (ISSN 1042-9832)
- Published
- 2000
- Language
- EN
- Field
- Mathematics (Physical Sciences)