A Proof of the Markov Chain Tree Theorem.

Abstract

Let X be a finite set, P a stochastic matrix on X, and P{BAR} = lim{AS n GOES TO x} (1/n){SIGMA k=0 to n-1, P^k}. Let G = (X, E) be the weighted directed graph on X associated to P, with weights P_ij. An arborescence is a subset a {IS AN ELEMENT OF} E which has at most one edge out of every node, contains no cycles, and has maximum possible cardinality. The weight of an arborescence is the product of its edge weights. Let A denote the set of all arborescences. Let A_ij denote the set of all arborescences which have j as a root and in which there is a directed path from i to j. Let ||A||, resp. ||A_ij||, be the sum of the weights of the arborescences in A, resp. A_ij. The Markov chain tree theorem states that p_ij = ||A_i,j||/||A||. We give a proof of this theorem which is probabilitistic in nature.