Markov Chain Intersections and the Loop-Erased Walk

Abstract

Let X and Y be independent transient Markov chains on the same state space that have the same transition probabilities. Let L denote the ``loop-erased path'' obtained from the path of X by erasing cycles when they are created. We prove that if the paths of X and Y have infinitely many intersections a.s., then L and Y also have infinitely many intersections a.s.

To appear in Ann. Inst. H. Poincaré Probab. Statist

Cited by in corpus (7)

• A Birthday Paradox for Markov chains with an optimal bound for collision in the Pollard Rho algorithm for discrete logarithm
• The dimension of loop-erased random walk in 3D
• Near Optimal Bounds for Collision in Pollard Rho for Discrete Log
• Scaling limits of the three-dimensional uniform spanning tree and associated random walk
• Logarithmic corrections to scaling in the four-dimensional uniform spanning tree
• Uniqueness of the infinite tree in low-dimensional random forests
• Minkowski sum of fractal percolation and random sets