Markov chain tree theorem

Key takeaways

Markov chain tree theorem belongs to mathematics; place it in that map before memorising details.
Learn the definition first, then one example that makes the definition concrete.
Connect Markov chain tree theorem to a quantity you can measure, compute or draw — that is where exam questions come from.
Reproduce the core statement of Markov chain tree theorem from memory before moving on to harder problems.

Reference excerpt

In the mathematical theory of Markov chains, the Markov chain tree theorem is an expression for the stationary distribution of a Markov chain with finitely many states. It sums up terms for the rooted spanning trees of the Markov chain, with a positive combination for each tree. The Markov chain tree theorem is closely related to Kirchhoff's theorem on counting the spanning trees of a graph, from which it can be derived. It was first stated by Hill (1966), for certain Markov chains arising in thermodynamics, and proved in full generality by Leighton & Rivest (1986), motivated by an application in limited-memory estimation of the probability of a biased coin. A finite Markov chain consists of a finite set of states, and a transition probability p i , j {\displaystyle p_{i,j}} for changing from state i {\displaystyle i} to state j {\displaystyle 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 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, directed toward a designated root, in which all directed edges are valid transitions of the given Markov chain. If a transition from state i {\displaystyle i} to state j {\displaystyle j} has transition probability p i , j {\displaystyle p_{i,j}} , then a tree T {\displaystyle T} with edge set E ( T ) {\displaystyle E(T)} is defined to have weight equal to the product of its transition probabilities:

w ( T ) = ∏ ( i , j ) ∈ E ( T ) p i , j . {\displaystyle w(T)=\prod _{(i,j)\in E(T)}p_{i,j}.}

Let T i {\displaystyle {\mathcal {T}}_{i}} denote the set of all spanning trees having state i {\displaystyle i} at their root. Then, according to the Markov chain tree theorem, the stationary probability π i {\displaystyle \pi _{i}} for state i {\displaystyle i} is proportional to the sum of the weights of the trees rooted at i {\displaystyle i} . That is,

π i = 1 Z ∑ T ∈ T i w ( T ) , {\displaystyle \pi _{i}={\frac {1}{Z}}\sum _{T\in {\mathcal {T}}_{i}}w(T),}

where the normalizing constant Z {\displaystyle Z} is the sum of w ( T ) {\displaystyle w(T)} over all spanning trees.

References

Worked examples

Example 1 — a first encounter with Markov chain tree theorem

Start with the simplest possible case. Write down what Markov chain tree theorem claims or describes in one sentence, then invent the smallest concrete situation in which that sentence is true. In mathematics, the smallest case is usually a single object, a single equation or a single measurement. Check that every symbol or term in your sentence has a meaning in that case.

Example 2 — changing one variable

Take the situation from Example 1 and change exactly one quantity: double it, halve it, or set it to zero. Predict what should happen to Markov chain tree theorem before you calculate. Comparing your prediction with the result is the fastest way to find out whether you understand the idea or only the words.

Example 3 — an exam-style question

Typical questions about Markov chain tree theorem ask you to (a) state it precisely, (b) apply it to given data, and (c) explain a limitation. Practise writing all three answers in under five minutes; the third part is what separates a full-mark answer from an average one.

Applications of Markov chain tree theorem

In research: Markov chain tree theorem appears in mathematics research whenever the underlying quantities have to be modelled precisely. Papers usually cite it as a starting assumption and then explore where it breaks down.
In technology and industry: Engineering practice reuses Markov chain tree theorem in design rules, simulations and safety margins. Knowing the idea lets you read a specification sheet and understand why the numbers look the way they do.
In the classroom: Markov chain tree theorem is common in secondary-school and first-year university syllabi. It links to neighbouring topics Markov processes, Spanning tree, Theorems about stochastic processes, so understanding it makes those chapters shorter.
In everyday life: Look for Markov chain tree theorem outside the textbook — in sport, cooking, traffic, electronics or the sky above you. An example you found yourself is remembered far longer than one you were given.

How to study Markov chain tree theorem in 20 minutes

Read the reference excerpt below once, without taking notes.
Close the page and write down what Markov chain tree theorem means in your own words.
Compare your version with the excerpt and mark what you missed.
Work through the three examples above with pen and paper.
Explain Markov chain tree theorem out loud to somebody else — or to Teacher Smith in the lgStudy chat.

Frequently asked questions

What is Markov chain tree theorem in simple terms?

In the mathematical theory of Markov chains, the Markov chain tree theorem is an expression for the stationary distribution of a Markov chain with finitely many states. It sums up terms for the rooted spanning trees of the Markov chain, with a positive combination for each tree.

Why does Markov chain tree theorem matter?

Because it connects several mathematics ideas at once: it gives you a definition you can apply, a quantity you can calculate, and a way to check whether a result is plausible.

How should I study Markov chain tree theorem?

Read the excerpt, restate it from memory, then work through the examples and applications listed on this page. The five-step study plan above takes about twenty minutes.

What does this page cover?

It gives you a compact reference excerpt plus original lgStudy explanations, examples, applications and study material on Markov chain tree theorem.