Show simple item record

A Proof of the Markov Chain Tree Theorem.

dc.contributor.authorAnantharam, Venkaten_US
dc.contributor.authorTsoucas, P.en_US
dc.description.abstractLet 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.extent288060 bytes
dc.relation.ispartofseriesISR; TR 1988-97en_US
dc.titleA Proof of the Markov Chain Tree Theorem.en_US
dc.typeTechnical Reporten_US

Files in this item


This item appears in the following Collection(s)

Show simple item record