The Markov Chain Tree Theorem
Let M be a finite first-order stationary Markov chain. We define an arborescence to be a set of edges in the directed graph for M having at most one edge out of every vertex, no cyles, and maximum cardinality. The weight of an arborescence is defined to be the product over each edge in the arboresce...
| Main Authors: | , |
|---|---|
| Published: |
2023
|
| Online Access: | https://hdl.handle.net/1721.1/149059 |
| _version_ | 1826198445195526144 |
|---|---|
| author | Leighton, Frank Thomson Rivest, Ronald L. |
| author_facet | Leighton, Frank Thomson Rivest, Ronald L. |
| author_sort | Leighton, Frank Thomson |
| collection | MIT |
| description | Let M be a finite first-order stationary Markov chain. We define an arborescence to be a set of edges in the directed graph for M having at most one edge out of every vertex, no cyles, and maximum cardinality. The weight of an arborescence is defined to be the product over each edge in the arborescence of the probability of the transition associated with the edge. We prove that if M starts in state i, its limiting average probability of being in state j is proportional to the sum of the weights of all arborescences having a path from i to j and no edge out of j. We present two proofs. The first is derived from simple graph theoretic identities. The second is derived from the closely-related Matrix Tree Theorem. |
| first_indexed | 2024-09-23T11:05:03Z |
| id | mit-1721.1/149059 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T11:05:03Z |
| publishDate | 2023 |
| record_format | dspace |
| spelling | mit-1721.1/1490592023-03-30T03:56:34Z The Markov Chain Tree Theorem Leighton, Frank Thomson Rivest, Ronald L. Let M be a finite first-order stationary Markov chain. We define an arborescence to be a set of edges in the directed graph for M having at most one edge out of every vertex, no cyles, and maximum cardinality. The weight of an arborescence is defined to be the product over each edge in the arborescence of the probability of the transition associated with the edge. We prove that if M starts in state i, its limiting average probability of being in state j is proportional to the sum of the weights of all arborescences having a path from i to j and no edge out of j. We present two proofs. The first is derived from simple graph theoretic identities. The second is derived from the closely-related Matrix Tree Theorem. 2023-03-29T14:23:48Z 2023-03-29T14:23:48Z 1983-11 https://hdl.handle.net/1721.1/149059 MIT-LCS-TM-249 application/pdf |
| spellingShingle | Leighton, Frank Thomson Rivest, Ronald L. The Markov Chain Tree Theorem |
| title | The Markov Chain Tree Theorem |
| title_full | The Markov Chain Tree Theorem |
| title_fullStr | The Markov Chain Tree Theorem |
| title_full_unstemmed | The Markov Chain Tree Theorem |
| title_short | The Markov Chain Tree Theorem |
| title_sort | markov chain tree theorem |
| url | https://hdl.handle.net/1721.1/149059 |
| work_keys_str_mv | AT leightonfrankthomson themarkovchaintreetheorem AT rivestronaldl themarkovchaintreetheorem AT leightonfrankthomson markovchaintreetheorem AT rivestronaldl markovchaintreetheorem |