A Proof of the Markov Chain Tree Theorem.

 dc.contributor.author Anantharam, Venkat en_US dc.contributor.author Tsoucas, P. en_US dc.date.accessioned 2007-05-23T09:42:21Z dc.date.available 2007-05-23T09:42:21Z dc.date.issued 1988 en_US dc.identifier.uri http://hdl.handle.net/1903/4823 dc.description.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. en_US dc.format.extent 288060 bytes dc.format.mimetype application/pdf dc.language.iso en_US en_US dc.relation.ispartofseries ISR; TR 1988-97 en_US dc.title A Proof of the Markov Chain Tree Theorem. en_US dc.type Technical Report en_US dc.contributor.department ISR en_US
﻿