Damped random walks and the characteristic polynomial of the weighted Laplacian on a graph

Abstract

For $\lambda >0$, we define a $\lambda$-damped random walk to be a random walk that is started from a random vertex of a graph and stopped at each step with probability $\frac{\lambda }{1+\lambda }$, otherwise continued with probability $\frac{1}{1+\lambda }$. We use the Aldous-Broder algorithm (\cite{aldous, broder}) of generating a random spanning tree and the Matrix-tree theorem to relate the values of the characteristic polynomial of the Laplacian at $\pm \lambda$ and the stationary measures of the sets of nodes visited by $i$ independent $\lambda$-damped random walks for $i\in \mathbb{N}$. As a corollary, we obtain a new characterization of the non-zero eigenvalues of the Weighted Graph Laplacian.

arXiv commentThis paper does not contain essentially new results