A proof of the Markov chain tree theorem
Let X be a finite set, P be a stochastic matrix on X, and = limn --> [infinity] (1/n)[summation operator]n-1k=0Pk. Let G = (X, E) be the weighted directed graph on X associated to P, with weights pij. An arborescence is a subset a [subset, double equals] 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 denote the set of all arborescences. Let 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 [short parallel][short parallel], resp. [short parallel]ij[short parallel], be the sum of the weights of the arborescences in , resp. ij. The Markov chain tree theorem states that ij = [short parallel]ij[short parallel]/[short parallel][short parallel]. We give a proof of this theorem which is probabilistic in nature.
Volume (Year): 8 (1989)
Issue (Month): 2 (June)
|Contact details of provider:|| Web page: http://www.elsevier.com/wps/find/journaldescription.cws_home/622892/description#description|
|Order Information:|| Postal: http://www.elsevier.com/wps/find/supportfaq.cws_home/regional|
When requesting a correction, please mention this item's handle: RePEc:eee:stapro:v:8:y:1989:i:2:p:189-192. See general information about how to correct material in RePEc.
If references are entirely missing, you can add them using this form.