# Recurrent Graphs where Two Independent Random Walks Collide Finitely Often

@article{Krishnapur2004RecurrentGW, title={Recurrent Graphs where Two Independent Random Walks Collide Finitely Often}, author={Manjunath Krishnapur and Yuval Peres}, journal={Electronic Communications in Probability}, year={2004}, volume={9}, pages={72-81} }

We present a class of graphs where simple random walk is recurrent, yet two independent walkers meet only finitely many times almost surely. In particular, the comb lattice, obtained from $Z^2$ by removing all horizontal edges off the $x$-axis, has this property. We also conjecture that the same property holds for some other graphs, including the incipient infinite cluster for critical percolation in $Z^2$.

#### Figures from this paper

#### 39 Citations

Collisions of Random Walks in Reversible Random Graphs

- Mathematics
- 2015

We prove that in any recurrent reversible random rooted graph, two independent simple random walks started at the same vertex collide infinitely often almost surely. This applies to the Uniform… Expand

Collisions of random walks

- Mathematics
- 2010

A recurrent graph G has the infinite collision property if two independent random walks on G, started at the same point, collide infinitely often a.s. We give a simple criterion in terms of Green… Expand

A note on the finite collision property of random walks

- Mathematics
- 2008

We consider a wedge comb of and two independent random walks on it with continuous time parameter. They meet each other infinitely many times if the height of the comb increases at most of the order… Expand

Two random walks on the open cluster of ℤ2 meet infinitely often

- Mathematics
- 2010

We prove that two independent continuous-time simple random walks on the infinite open cluster of a Bernoulli bond percolation in the lattice ℤ2 meet each other infinitely many times. An application… Expand

Collisions of Random Walks in Dynamic Random Environments

- Mathematics
- 2020

We study dynamic random conductance models on $\mathbb{Z}^2$ in which the environment evolves as a reversible Markov process that is stationary under space-time shifts. We prove under a second moment… Expand

About the distance between random walkers on some graphs

- Mathematics, Computer Science
- Period. Math. Hung.
- 2017

We consider two or more simple symmetric walks on $$\mathbb {Z}^d$$Zd and the 2-dimensional comb lattice, and in case of finite collision, we investigate the properties of the distance among the… Expand

Directed Polymers on Infinite Graphs

- Mathematics
- 2020

We study the directed polymer model for general graphs (beyond $\mathbb Z^d$) and random walks. We provide sufficient conditions for the existence or non-existence of a weak disorder phase, of an… Expand

Strong Limit Theorems for a Simple Random Walk on the 2-Dimensional Comb

- Mathematics
- 2009

We study the path behaviour of a simple random walk on the $2$-dimensional comb lattice $C^2$ that is obtained from $\mathbb{Z}^2$ by removing all horizontal edges off the $x$-axis. In particular, we… Expand

Symmetric simple random walks

- Mathematics
- 2017

Random walks denote a general class of stochastic processes for which the definition significantly varies across the literature. Since the ultimate target of this textbook is spatial stochastic… Expand

Gaussian bounds and Collisions of variable speed random walks on lattices with power law conductances

- Mathematics
- 2015

We consider a weighted lattice $Z^d$ with conductance $\mu_e=|e|^{-\alpha}$. We show that the heat kernel of a variable speed random walk on it satisfies a two-sided Gaussian bound by using an… Expand

#### References

SHOWING 1-10 OF 15 REFERENCES

Random Walks on Infinite Graphs and Groups

- Mathematics
- 2000

Part I. The Type Problem: 1. Basic facts 2. Recurrence and transience of infinite networks 3. Applications to random walks 4. Isoperimetric inequalities 5. Transient subtrees, and the classification… Expand

Some problems concerning the structure of random walk paths

- Mathematics
- 1963

1. In t roduct ion . We restrict our consideration to symmetric random walk, defined in the following way. Consider the lattice formed by the points of d-dimensional Euclidean space whose coordinates… Expand

The incipient infinite cluster in two-dimensional percolation

- Mathematics
- 1986

SummaryLetPp be the probability measure on the configurations of occupied and vacant vertices of a two-dimensional graphG, under which all vertices are independently occupied (respectively vacant)… Expand

A characterization of the invariant measures for an infinite particle system with interactions

- Mathematics
- 1973

ABSTRACT. Let p(x,y) be the transition function for a symmetric, irreducible, transient Markov chain on the countable set S. Let 71 be the infinite particle system on S with the simple exclusion… Expand

Subdiffusive behavior of random walk on a random cluster

- Mathematics
- 1986

On considere deux cas de marche aleatoire {X n } n≥0 sur un graphe aleatoire #7B-G. Dans le cas ou #7B-G est l'arbre d'un processus de branchement critique, conditionne par la non-extinction, si h(x)… Expand

An Introduction To Probability Theory And Its Applications

- Computer Science
- 1950

A First Course in Probability (8th ed.) by S. Ross is a lively text that covers the basic ideas of probability theory including those needed in statistics. Expand

Probability Trees

- Computer Science
- Graphics Interface
- 1997

A k D tree representation of probability distribu tions is generalized to support generation of samples from conditional distributions An interpretation of the approach as a piecewise linear warping… Expand