Backend
The Order Mass Identity of Rooted Forests, with a Direct Proof of the Extended Aldous--Broder Theorem
arXiv stat.TH0 views
arXiv:2610.13063v1 Announce Type: cross Abstract: 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.
Source:https://arxiv.org/abs/2610.13063PreviousAn efficient stochastic generalized method of moments estimator for nonlinear moment modelsNextThe Harmonic Entropy Estimator: Minimax Optimality and Semiparametric Efficiency for Infinite Alphabets
Related posts
Three dates that catch a hard-coded time-zone bug in a session clock
0dev.to
Laravel N+1 Query Problem: How to Find and Fix It
0dev.to
LongCat-2.5 at $0.30/$1.20: Thinking Locks Temperature, 1M Context, and Vendor Benches Between Opus 4.8 and 5
0dev.to
Shipped: two packages, a registry listing, and the first seals
0dev.to
AI Agent Memory Needs Garbage Collection, Not Just Storage
0dev.to

Securing the Analytics Pipeline and Pivoting for Demo Day
0dev.to