On a finite connected unweighted graph, the graph path between and in a uniform spanning tree has the law of loop-erased random walk from to . Root Wilson's algorithm at and process first: the first attached graph path is exactly that loop erasure, and later attachments cannot change it. Changing the root to proves reversibility of loop-erased random walk, even though chronological loop erasure does not commute with reversing each individual random-walk trajectory.
Articles by others on the same topic
There are currently no matching articles.