In the mathematical theory of

Markov chain A Markov chain or Markov process is a stochastic model describing a sequence of possible events in which the probability of each event depends only on the state attained in the previous event. Informally, this may be thought of as, "What happe ...

s, the Markov chain tree theorem is an expression for the

stationary distribution Stationary distribution may refer to: * A special distribution for a Markov chain such that if the chain starts with its stationary distribution, the marginal distribution of all states at any time will always be the stationary distribution. Assum ...

of a Markov chain with finitely many states. It sums up terms for the rooted

spanning tree In the mathematical field of graph theory, a spanning tree ''T'' of an undirected graph ''G'' is a subgraph that is a tree which includes all of the vertices of ''G''. In general, a graph may have several spanning trees, but a graph that is not ...

s of the Markov chain, with a positive combination for each tree. The Markov chain tree theorem is closely related to

Kirchhoff's theorem In the mathematical field of graph theory, Kirchhoff's theorem or Kirchhoff's matrix tree theorem named after Gustav Kirchhoff is a theorem about the number of spanning trees in a graph, showing that this number can be computed in polynomial time f ...

on counting the spanning trees of a graph, from which it can be derived. It was first stated by , for certain Markov chains arising in

thermodynamics Thermodynamics is a branch of physics that deals with heat, work, and temperature, and their relation to energy, entropy, and the physical properties of matter and radiation. The behavior of these quantities is governed by the four laws of the ...

, and proved in full generality by , motivated by an application in limited-memory estimation of the probability of a

biased coin In probability theory and statistics, a sequence of independent Bernoulli trials with probability 1/2 of success on each trial is metaphorically called a fair coin. One for which the probability is not 1/2 is called a biased or unfair coin. In the ...

. A finite Markov chain consists of a finite set of states, and a transition probability

p_

for changing from state

i

to state

j

, such that for each state the outgoing transition probabilities sum to one. From an initial choice of state (which turns out to be irrelevant to this problem), each successive state is chosen at random according to the transition probabilities from the previous state. A Markov chain is said to be irreducible when every state can reach every other state through some sequence of transitions, and aperiodic if, for every state, the possible numbers of steps in sequences that start and end in that state have

greatest common divisor In mathematics, the greatest common divisor (GCD) of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers. For two integers ''x'', ''y'', the greatest common divisor of ''x'' and ''y'' is ...

one. An irreducible and aperiodic Markov chain necessarily has a stationary distribution, a probability distribution on its states that describes the probability of being on a given state after many steps, regardless of the initial choice of state. The Markov chain tree theorem considers spanning trees for the states of the Markov chain, defined to be

trees In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, including only woody plants with secondary growth, plants that are u ...

, directed toward a designated root, in which all directed edges are valid transitions of the given Markov chain. If a transition from state

i

to state

j

has transition probability

p_

, then a tree

T

with edge set

E(T)

is defined to have weight equal to the product of its transition probabilities:

w(T)=\prod_ p_.

Let

\mathcal_i

denote the set of all spanning trees having state

i

at their root. Then, according to the Markov chain tree theorem, the stationary probability

\pi_i

for state

i

is proportional to the sum of the weights of the trees rooted at

i

. That is,

\pi_i=\frac\sum_ w(T),

where the normalizing constant

Z

is the sum of

w(T)

over all spanning trees.

References

{{reflist, refs= {{citation , last = Hill , first = Terrell L. , date = April 1966 , doi = 10.1016/0022-5193(66)90137-8 , issue = 3 , journal = Journal of Theoretical Biology , pages = 442–459 , title = Studies in irreversible thermodynamics IV: diagrammatic representation of steady state fluxes for unimolecular systems , volume = 10 {{citation , last1 = Leighton , first1 = Frank Thomson , author1-link = F. Thomson Leighton , last2 = Rivest , first2 = Ronald L. , author2-link = Ron Rivest , doi = 10.1109/TIT.1986.1057250 , issue = 6 , journal = IEEE Transactions on Information Theory , pages = 733–742 , title = Estimating a probability using finite memory , volume = 32 , year = 1986 {{citation , last = Williams , first = Lauren K. , author-link = Lauren Williams (mathematician) , arxiv = 2202.00214 , date = May 2022 , issue = 500 , journal = London Mathematical Society Newsletter , pages = 50–59 , title = The combinatorics of hopping particles and positivity in Markov chains Markov processes Spanning tree