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.
Description
Determinants, their applications to Markov processes, and a random walk
proof of Kirchhoff's matrix tree theorem
%0 Generic
%1 kozdron2013determinants
%A Kozdron, Michael J.
%A Richards, Larissa M.
%A Stroock, Daniel W.
%D 2013
%K determinants markov
%T Determinants, their applications to Markov processes, and a random walk
proof of Kirchhoff's matrix tree theorem
%U http://arxiv.org/abs/1306.2059
%X 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.
@misc{kozdron2013determinants,
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.},
added-at = {2014-07-12T02:00:44.000+0200},
author = {Kozdron, Michael J. and Richards, Larissa M. and Stroock, Daniel W.},
biburl = {https://www.bibsonomy.org/bibtex/201c65ab472a96db7162e06834b66d447/pitman},
description = {Determinants, their applications to Markov processes, and a random walk
proof of Kirchhoff's matrix tree theorem},
interhash = {3b3d5e79e951e093afad046728ca4e02},
intrahash = {01c65ab472a96db7162e06834b66d447},
keywords = {determinants markov},
note = {cite arxiv:1306.2059Comment: v1: 14 pages, 5 figures},
timestamp = {2014-07-12T02:00:44.000+0200},
title = {Determinants, their applications to Markov processes, and a random walk
proof of Kirchhoff's matrix tree theorem},
url = {http://arxiv.org/abs/1306.2059},
year = 2013
}