Loop-Erased Random Walks, Spanning Trees and Hamiltonian Cycles

Philippe Marchal (Université Paris 6)

Abstract


We establish a formula for the distribution of loop-erased random walks at certain random times. Several classical results on spanning trees, including Wilson's algorithm, follow easily, as well as a method to construct random Hamiltonian cycles.

Full Text: Download PDF | View PDF online (requires PDF plugin)

Pages: 39-50

Publication Date: December 3, 1999

DOI: 10.1214/ECP.v5-1016

References

  1. D. Aldous and J. Fill. Reversible Markov Chains. To appear.
  2. R. Burton and R. Pemantle. Local characteristics, entropy and limit theorems for spanning trees and domino tilings via transfer-impedances. Ann. Probab. 21 (1993), no. 3, 1329--1371. Math. Review 94m:60019
  3. G.F. Lawler. Loop-erased random walk. Perplexing Problems in Probability, Birkhauser-Boston (1999), 197--217.
  4. I. Benjamini, R. Lyons, Y. Peres and O. Schramm. Uniform spanning forests. To appear, Ann Probab.
  5. G. Kirchhoff. Über die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Verteilung galvanischer Ströme geführt wird. Ann. Phys. Chem. 72 (1847) 497--08.
  6. R. Kenyon. The asymptotic determinant of the discrete Laplacian. Preprint (1999).
  7. R. Lyons and Y. Peres. Probability on Trees and Networks. To appear.
  8. J.G. Propp and D.B. Wilson. How to get a perfectly random sample from a generic Markov chain and generate a random spanning tree of a directed graph. 7th Annual ACM-SIAM Symposium on Discrete Algorithms (Atlanta, GA, 1996). J. Algorithms 27 (1998), no. 2, 170--217. Math. Review 99g:60116
  9. E. Seneta. (1973). Non-negative matrices and Markov chains. Springer. Math. Review 85i:60058
Bookmark and Share


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.