Determinants, their applications to Markov processes, and a random walk proof of Kirchhoff's matrix tree theorem
From MaRDI portal
Publication:6242545
arXiv1306.2059MaRDI QIDQ6242545FDOQ6242545
Authors: Michael J. Kozdron, Larissa M. Richards, Daniel W. Stroock 
Publication date: 9 June 2013
Abstract: Kirchhoff's matrix tree theorem is a well-known result that gives a formula for the number of spanning trees in a finite, connected graph in terms of the graph Laplacian matrix. A closely related result is Wilson's algorithm for putting the uniform distribution on the set of spanning trees. We will show that when one follows Greg Lawler's strategy for proving Wilson's algorithm, Kirchhoff's theorem follows almost immediately after one applies some elementary linear algebra. We also show that the same ideas can be applied to other computations related to general Markov chains and processes on a finite state space.
This page was built for publication: Determinants, their applications to Markov processes, and a random walk proof of Kirchhoff's matrix tree theorem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6242545)
