Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Markov chain tree formula: μz′=pz′/∑xpx′\mu'_z = p'_z / \sum_x p'_xμz′​=pz′​/∑x​px′​ is the unique stationary distribution

Proved
YoungConventions.Perturbed.markov_chain_tree_formula

by mikedeng1 · Oct 6, 2026 · Mathlib 0df444a (Lean v4.33.1)

arborescencemarkov-chainp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1stationary-distribution

Let P′P'P′ be the transition matrix of an aperiodic, irreducible Markov chain on a nonempty finite set XXX. For z∈Xz \in Xz∈X let

pz′=∑T∈Tz∏(x,y)∈TPxy′,p'_z = \sum_{T \in \mathcal T_z} \prod_{(x,y) \in T} P'_{xy},pz′​=T∈Tz​∑​(x,y)∈T∏​Pxy′​,

where Tz\mathcal T_zTz​ is the set of zzz-trees (spanning in-trees directed toward zzz) on XXX. Then pz′>0p'_z > 0pz′​>0 for every zzz, and

μz′=pz′∑x∈Xpx′\mu'_z = \frac{p'_z}{\sum_{x \in X} p'_x}μz′​=∑x∈X​px′​pz′​​

is a stationary distribution of P′P'P′ (μ′P′=μ′\mu' P' = \mu'μ′P′=μ′), and it is the unique stationary distribution of P′P'P′.

This is the lemma of Freidlin and Wentzell (1984, Ch. 6, Lemma 3.1) that Young applies to PεP^\varepsilonPε in the proof of Lemma 1: it writes με\mu^\varepsilonμε as a ratio of polynomials in the entries of PεP^\varepsilonPε, whose orders of magnitude are read off from the resistances.

Formalization Note Both hypotheses printed on the page (aperiodic and irreducible) are kept, although irreducibility suffices. Trees through zero entries are included in the sum and contribute 000.

Preamble
import Mathlib
import Definitions.Def_YoungConventions_Perturbed_FiniteChain
import Definitions.Def_YoungConventions_Perturbed_InTree

open Finset
Formal statement
namespace YoungConventions.Perturbed

/-- The Markov chain tree formula (Freidlin–Wentzell 1984, Ch. 6, Lemma 3.1), as quoted in the proof
of Lemma 1 (Young 1993, Econometrica 61:57–84, Appendix, p. 79, PDF p. 24).

Let `P′` be the transition matrix of an aperiodic, irreducible Markov chain on the finite set
`X`, and for `z ∈ X` let `p′_z = ∑_{T ∈ 𝒯_z} ∏_{(x,y) ∈ T} P′_{xy}` (`treeWeight`). Then every
`p′_z` is positive, `μ′_z = p′_z / ∑_x p′_x` is a stationary distribution of `P′`, and it is the
unique stationary distribution of `P′`.

**Formalization Note.** Both hypotheses of the page (aperiodic and irreducible) are kept, although
irreducibility alone suffices. The state type is nonempty: on an empty type both conditions
hold vacuously, but no probability distribution can have total mass `1`. `z`-trees are in-trees
(edges point toward `z`), so for two states `p′_1 = P′_{21}` and `p′_2 = P′_{12}`. -/
theorem markov_chain_tree_formula {X : Type*} [Fintype X] [DecidableEq X] [Nonempty X]
    (A : Matrix X X ℝ) (hA : A ∈ Matrix.rowStochastic ℝ X)
    (hirr : A.IsIrreducible) (hap : IsAperiodic A) :
    (∀ z, 0 < treeWeight A z) ∧
    IsStationaryDist A (fun z => treeWeight A z / ∑ x, treeWeight A x) ∧
    ∀ ν : X → ℝ, IsStationaryDist A ν → ν = fun z => treeWeight A z / ∑ x, treeWeight A x := by sorry

end YoungConventions.Perturbed
Source
Young (1993), The Evolution of Conventions, Econometrica 61:57–84, Appendix, proof of Lemma 1, p. 79 (PDF p. 24); Freidlin and Wentzell (1984), Random Perturbations of Dynamical Systems, Ch. 6, Lemma 3.1
Human review
  • Endorsed by Shuze Chen · Oct 6, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 6, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me