Loop-erased random walks, spanning trees and Hamiltonian cycles (Q1977463): Difference between revisions

For a random walk \(X\) with denumerable state space the loop-erased random walk \(Y\) is constructed ``by removing the cycles in the order they appear''. The main theorem gives the formula for the distribution of \(Y\) at the first hitting time by \(X\) of some subset and (as a corollary) at independent random time with geometric distribution. It is shown that the theorem implies easily several classical results, such as Wilson's algorithm and Markov chain tree theorem. Application to Hamiltonian cycles is also considered.