← All papers
First page of The Order Mass Identity of Rooted Forests, with a Direct Proof of the Extended Aldous–Broder Theorem

The Order Mass Identity of Rooted Forests, with a Direct Proof of the Extended Aldous–Broder Theorem

Hugh Zheng

math.PR Oct 9, 2026 · v1 math.CO math.ST
The order-mass identity, the extended Aldous–Broder theorem, and the stopped-forest law are formalized in Lean 4 with Mathlib, with a public repository.
Random spanning forests provide probability models for partitions and Monte Carlo methods on graphs. In these applications, the distribution produced by a sampler determines which forest functionals can be estimated. The Aldous–Broder algorithm constructs a spanning tree from the first-entrance edges of a covering random walk. Its distribution is known, but a direct calculation requires summing over all orders in which a fixed tree can be discovered. We evaluate this sum through an identity for rooted forests and real matrices with zero row sums. Under a nonsingularity condition on the principal submatrices encountered during growth, the sum of products of harmonic extension entries equals a principal cofactor of a matrix on the roots. With one root, the sum is one. The identity gives a direct proof of the extended Aldous–Broder theorem for every finite irreducible Markov chain started at a fixed state, without assuming reversibility or bidirectional transition support. It also gives the conditional distribution of the discovery order and the law of the forest obtained by stopping after all nonroot vertices have been visited. A completion weight describes the difference between this stopped-walk law and the weight-proportional forest law, including the support restriction needed for importance correction. Numerical examples illustrate the sampling implications. The identity, the Aldous–Broder theorem, and the stopped-forest law are formalized in Lean4.

The Aldous–Broder algorithm builds a spanning tree from the first-entrance edges of a covering random walk. A direct derivation of its tree law requires summing over all orders in which a fixed tree can be discovered. The law of the forest obtained by stopping once all nonroot vertices are visited is also needed for Monte Carlo use.

An order-mass identity is proved for rooted forests and real matrices with zero row sums. It states that, under nonsingularity of the principal submatrices met during growth, the sum of products of harmonic extension entries equals a principal cofactor on the roots. The proof is by induction, using a one-vertex transfer lemma that moves the first discovered vertex into the root set. The results are formalized in Lean 4 on top of Mathlib.

With a single root the order mass equals one, giving a direct proof of the extended Aldous–Broder theorem for any finite irreducible chain, without assuming reversibility. The identity also yields the conditional law of the discovery order and the stopped-forest law, including a completion weight for importance correction.