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.

A random walk on $\mathbb{Z}^d$ is excited if the first time it visits a vertex there is a bias in one direction, but on subsequent visits to that vertex the walker picks a neighbor uniformly at random. We show that…

We show how the evolving set methodology of Morris and Peres can be used to show Cheeger inequalities for bounding the spectral gap of a finite Markov kernel. This leads to sharp versions of several previous Cheeger inequalities, including ones…

We examine the question of whether a collection of random walks on a graph can be coupled so that they never collide.  In particular, we show that on the complete graph on n vertices, with or without loops, there is…

In this note, we demonstrate an instance of bounded-degree graphs of size $n$, for which the total variation mixing time for the random walk is decreased by a factor of $\log n/ \log\log n$ if we multiply the edge-conductances by…

We consider moments of the return times (or first hitting times) in an irreducible discrete time discrete space Markov chain. It is classical that the finiteness of the first moment of a return time of one state implies the finiteness…