The Order Mass Identity of Rooted Forests, with a Direct Proof of the Extended Aldous-Broder Theorem
Abstract
The Aldous-Broder algorithm constructs a spanning tree from the first-entrance edges of a covering random walk. Its distribution is known, but deriving it by summing over the orders in which a fixed tree can be discovered remains difficult. In this paper, we evaluate this sum by establishing an order-mass identity for rooted forests. For real matrices with zero row sums, the identity expresses the sum of order weights associated with each root as a principal cofactor of a matrix on the roots, under a nonsingularity condition involving only the sets encountered along the growth orders of the given forest. We prove the identity using linear algebraic tools. With one root, the sum equals one, giving a direct proof of the extended Aldous-Broder theorem for every finite irreducible Markov chain started at a fixed state. With multiple roots, we derive the forest law produced by the stopped covering walk and show how it differs from the weight-proportional forest law. The identity and the resulting tree and forest laws are formalized in Lean 4.
Related
- Rooted spanning forests in wheel graphs: Fibonacci-Lucas formulas and extremal root configurations
- A Formal Proof of Riemann Hypothesis from Existence Alone, the Sign Excepted by Theorem: The Constructed Witness, the Identity Cone over the Fixed Locus, the Grounded Counter-Model, and the Cure Theorem Proved in Lean 4 and Re-executed in Fortran
- Direct Optimization of Generators for Search in Automated Theorem Proving
- Palindromic real-rooted polynomials and h-vectors of polytopes
- Extremal function for rooted K5 minors
BibTeX
@misc{zheng2026order,
title = {{The Order Mass Identity of Rooted Forests, with a Direct Proof of the Extended Aldous-Broder Theorem}},
author = {Hugh Zheng},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.13063},
eprint = {2610.13063},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.13063},
note = {CC0},
}
RIS
TY - UNPB
TI - The Order Mass Identity of Rooted Forests, with a Direct Proof of the Extended Aldous-Broder Theorem
AU - Hugh Zheng
PY - 2026
DA - 2026/10/23
PB - arXiv
DO - 10.48550/arxiv.2610.13063
UR - https://arxiv.org/abs/2610.13063
AB - The Aldous-Broder algorithm constructs a spanning tree from the first-entrance edges of a covering random walk. Its distribution is known, but deriving it by summing over the orders in which a fixed tree can be discovered remains difficult. In this paper, we evaluate this sum by establishing an order-mass identity for rooted forests. For real matrices with zero row sums, the identity expresses the sum of order weights associated with each root as a principal cofactor of a matrix on the roots, under a nonsingularity condition involving only the sets encountered along the growth orders of the given forest. We prove the identity using linear algebraic tools. With one root, the sum equals one, giving a direct proof of the extended Aldous-Broder theorem for every finite irreducible Markov chain started at a fixed state. With multiple roots, we derive the forest law produced by the stopped covering walk and show how it differs from the weight-proportional forest law. The identity and the resulting tree and forest laws are formalized in Lean 4.
ER -