A Proof of the Markov Chain Tree Theorem.
| dc.contributor.author | Anantharam, Venkat | en_US |
| dc.contributor.author | Tsoucas, P. | en_US |
| dc.contributor.department | ISR | 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.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.identifier.uri | http://hdl.handle.net/1903/4823 | |
| 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 |
Files
Original bundle
1 - 1 of 1