Loop-erased random walks, spanning trees and Hamiltonian cycles (Q1977463)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Loop-erased random walks, spanning trees and Hamiltonian cycles
scientific article

    Statements

    Loop-erased random walks, spanning trees and Hamiltonian cycles (English)
    0 references
    0 references
    18 May 2000
    0 references
    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.
    0 references
    Markov chain
    0 references
    random walk
    0 references
    spanning tree
    0 references
    cycle
    0 references
    Wilson's algorithm
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references