Tech Report CS-10-04

An Elementary Proof of the Markov Chain Tree Theorem

Alex Kruckman, Amy Greenwald and John Wicks

August 2010

Abstract:

The Markov Chain Tree Theorem is a classical result which expresses the stable distribution of an irreducible Markov matrix in terms of directed spanning trees of its associated graph. In this article, we present what we believe to be an original elementary proof of the theorem. Our proof uses only linear algebra and graph theory, and in particular, it does not rely on probability theory. For this reason, this article could serve as a pedagogical tool or a gentle introduction to the theory of Markov matrices for undergraduate computer science and mathematics students.

(complete text in pdf)