Home | Contents | Submissions, editors, etc. | Login | Search | EJP
 Electronic Communications in Probability > Vol. 5 (2000) > Paper 4 open journal systems 


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: PDF

Pages: 39-50

Published on: December 3, 1999
Bibliography
  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
















Research
Support Tool
Capture Cite
View Metadata
Printer Friendly
Context
Author Address
Action
Email Author
Email Others


Home | Contents | Submissions, editors, etc. | Login | Search | EJP

Electronic Communications in Probability. ISSN: 1083-589X