{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,26]],"date-time":"2026-06-26T02:51:49Z","timestamp":1782442309929,"version":"3.54.5"},"reference-count":47,"publisher":"Oxford University Press (OUP)","issue":"2","license":[{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/pages\/standard-publication-reuse-rights"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025,3,16]]},"abstract":"<jats:title>Summary<\/jats:title>\n               <jats:p>Tree graphs are used routinely in statistics. When estimating a Bayesian model with a tree component, sampling the posterior remains a core difficulty. Existing Markov chain Monte Carlo methods tend to rely on local moves, often leading to poor mixing. A promising approach is to instead directly sample spanning trees on an auxiliary graph. Current spanning tree samplers, such as the celebrated Aldous\u2013Broder algorithm, rely predominantly on simulating random walks that are required to visit all the nodes of the graph. Such algorithms are prone to getting stuck in certain subgraphs. We formalize this phenomenon using the bottlenecks in the random walk\u2019s transition probability matrix. We then propose a novel fast-forwarded cover algorithm that can break free from bottlenecks. The core idea is a marginalization argument that leads to a closed-form expression that allows for fast-forwarding to the event of visiting a new node. Unlike many existing approximation algorithms, our algorithm yields exact samples. We demonstrate the enhanced efficiency of the fast-forwarded cover algorithm, and illustrate its application in fitting a Bayesian dendrogram model on a Massachusetts crime and community dataset.<\/jats:p>","DOI":"10.1093\/biomet\/asaf031","type":"journal-article","created":{"date-parts":[[2025,4,15]],"date-time":"2025-04-15T17:40:56Z","timestamp":1744738856000},"source":"Crossref","is-referenced-by-count":3,"title":["Exact sampling of spanning trees via fast-forwarded random walks"],"prefix":"10.1093","volume":"112","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4469-1168","authenticated-orcid":false,"given":"Edric","family":"Tam","sequence":"first","affiliation":[{"name":"Department of Biomedical Data Science, Stanford University , 300 Pasteur Drive , Palo Alto, California 94304,","place":["USA"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"David B","family":"Dunson","sequence":"additional","affiliation":[{"name":"Department of Statistical Science and Department of Mathematics, Duke University , Box 90251 , Durham, North Carolina 27708,","place":["USA"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Leo L","family":"Duan","sequence":"additional","affiliation":[{"name":"Department of Statistics, University of Florida , 101C Griffin-Floyd Hall, P.O. Box 118545 , Gainesville, Florida 32611,","place":["USA"]}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"286","published-online":{"date-parts":[[2025,4,15]]},"reference":[{"key":"2025062607282393700_asaf031-B1","doi-asserted-by":"crossref","first-page":"450","DOI":"10.1137\/0403039","article-title":"The random walk construction of uniform spanning trees and uniform labelled trees","volume":"3","author":"Aldous","year":"1990","journal-title":"SIAM J. Discrete Math."},{"key":"2025062607282393700_asaf031-B2","doi-asserted-by":"crossref","first-page":"1366","DOI":"10.1137\/21M1418010","article-title":"Metropolized forest recombination for Monte Carlo sampling of graph partitions","volume":"83","author":"Autry","year":"2023","journal-title":"SIAM J. Appl. Math."},{"key":"2025062607282393700_asaf031-B3","first-page":"442","volume-title":"30th Ann. Symp. Foundat. Comp. Sci","author":"Broder","year":"1989"},{"key":"2025062607282393700_asaf031-B4","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1007\/BF01048273","article-title":"Bounds on the cover time","volume":"2","author":"Broder","year":"1989","journal-title":"J. Theor. Prob"},{"key":"2025062607282393700_asaf031-B5","doi-asserted-by":"crossref","first-page":"3482","DOI":"10.1214\/21-AOS2093","article-title":"Uncertainty quantification for Bayesian CART","volume":"49","author":"Castillo","year":"2021","journal-title":"Ann. Statist."},{"key":"2025062607282393700_asaf031-B6","doi-asserted-by":"crossref","first-page":"935","DOI":"10.1080\/01621459.1998.10473750","article-title":"Bayesian CART model search","volume":"93","author":"Chipman","year":"1998","journal-title":"J. Am. Statist. Assoc"},{"key":"2025062607282393700_asaf031-B7","doi-asserted-by":"crossref","first-page":"266","DOI":"10.1214\/09-AOAS285","article-title":"BART: Bayesian additive regression trees","volume":"4","author":"Chipman","year":"2010","journal-title":"Ann. Appl. Statist"},{"key":"2025062607282393700_asaf031-B8","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s00026-005-0237-z","article-title":"Laplacians and the Cheeger inequality for directed graphs","volume":"9","author":"Chung","year":"2005","journal-title":"Ann. Combinat."},{"key":"2025062607282393700_asaf031-B9","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1093\/biomet\/85.2.363","article-title":"A Bayesian CART algorithm","volume":"85","author":"Denison","year":"1998","journal-title":"Biometrika"},{"key":"2025062607282393700_asaf031-B10","first-page":"1","article-title":"Bayesian spanning tree: estimating the backbone of the dependence graph","volume":"24","author":"Duan","year":"2023","journal-title":"J. Mach. Learn. Res"},{"key":"2025062607282393700_asaf031-B11","doi-asserted-by":"crossref","first-page":"2140","DOI":"10.1080\/01621459.2023.2250098","article-title":"Spectral clustering, Bayesian spanning forest, and forest process","volume":"119","author":"Duan","year":"2024","journal-title":"J. Am. Statist. Assoc"},{"key":"2025062607282393700_asaf031-B12","first-page":"1","volume-title":"Advances in Neural Information Processing Systems","author":"Elidan","year":"2008"},{"key":"2025062607282393700_asaf031-B13","first-page":"918","article-title":"Subtree prune and regraft: a reversible real tree-valued Markov process","volume":"34","author":"Evans","year":"2005","journal-title":"Ann. Prob"},{"key":"2025062607282393700_asaf031-B14","doi-asserted-by":"crossref","first-page":"430","DOI":"10.1002\/rsa.21101","article-title":"A combinatorial proof of Aldous\u2013Broder theorem for general Markov chains","volume":"62","author":"Fredes","year":"2023","journal-title":"Random Struct. Algor"},{"key":"2025062607282393700_asaf031-B15","doi-asserted-by":"crossref","first-page":"367","DOI":"10.1214\/09-BA414","article-title":"Improved criteria for clustering based on the posterior similarity matrix","volume":"4","author":"Fritsch","year":"2009","journal-title":"Bayesian Anal."},{"key":"2025062607282393700_asaf031-B16","first-page":"54","article-title":"Minimum spanning trees and single linkage cluster analysis","volume":"18","author":"Gower","year":"1969","journal-title":"J. R. Statist. Soc. C"},{"key":"2025062607282393700_asaf031-B17","doi-asserted-by":"crossref","first-page":"1119","DOI":"10.1198\/016214508000000689","article-title":"Bayesian treed Gaussian process models with an application to computer modeling","volume":"103","author":"Gramacy","year":"2008","journal-title":"J. Am. Statist. Assoc"},{"key":"2025062607282393700_asaf031-B18","doi-asserted-by":"crossref","first-page":"214","DOI":"10.1016\/0196-6774(83)90022-6","article-title":"Random spanning tree","volume":"4","author":"Guenoche","year":"1983","journal-title":"J. Algor."},{"key":"2025062607282393700_asaf031-B19","doi-asserted-by":"crossref","first-page":"522","DOI":"10.1007\/978-3-662-49529-2_39","volume-title":"LATIN 2016: Theoretical Informatics Lecture Notes Comp. Sci. 9644)","author":"Harvey","year":"2016"},{"key":"2025062607282393700_asaf031-B20","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1198\/016214505000000187","article-title":"A quantitative study of gene regulation involved in the immune response of anopheline mosquitoes: an application of Bayesian hierarchical clustering of curves","volume":"101","author":"Heard","year":"2006","journal-title":"J. Am. Statist. Assoc"},{"key":"2025062607282393700_asaf031-B21","first-page":"297","volume-title":"Proc. 22nd Int. Conf. Mach. Learn","author":"Heller","year":"2005"},{"key":"2025062607282393700_asaf031-B22","doi-asserted-by":"crossref","first-page":"754","DOI":"10.1093\/bioinformatics\/17.8.754","article-title":"MRBAYES: Bayesian inference of phylogenetic trees","volume":"17","author":"Huelsenbeck","year":"2001","journal-title":"Bioinformatics"},{"key":"2025062607282393700_asaf031-B23","doi-asserted-by":"crossref","first-page":"48","DOI":"10.1090\/S0002-9939-1956-0078686-7","article-title":"On the shortest spanning subtree of a graph and the traveling salesman problem","volume":"7","author":"Kruskal","year":"1956","journal-title":"Proc. Am. Math. Soc"},{"key":"2025062607282393700_asaf031-B24","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1016\/0196-6774(90)90002-V","article-title":"Generating random combinatorial objects","volume":"11","author":"Kulkarni","year":"1990","journal-title":"J. Algor"},{"key":"2025062607282393700_asaf031-B25","author":"Lauritzen","year":"1996"},{"key":"2025062607282393700_asaf031-B26","doi-asserted-by":"crossref","DOI":"10.1090\/mbk\/107","volume-title":"Markov Chains and Mixing Times","author":"Levin","year":"2017","edition":"2nd ed"},{"key":"2025062607282393700_asaf031-B27","doi-asserted-by":"crossref","first-page":"1087","DOI":"10.1111\/rssb.12293","article-title":"Bayesian regression tree ensembles that adapt to smoothness and sparsity","volume":"80","author":"Linero","year":"2018","journal-title":"J. R. Statist. Soc. B"},{"key":"2025062607282393700_asaf031-B28","doi-asserted-by":"crossref","first-page":"593","DOI":"10.1002\/jgt.3190170505","article-title":"A note on the last new vertex visited by a random walk","volume":"17","author":"Lov\u00e1sz","year":"1993","journal-title":"J. Graph Theory"},{"key":"2025062607282393700_asaf031-B29","first-page":"1748","article-title":"A Bayesian contiguous partitioning method for learning clustered latent variables","volume":"22","author":"Luo","year":"2021","journal-title":"J. Mach. Learn. Res"},{"key":"2025062607282393700_asaf031-B30","doi-asserted-by":"crossref","first-page":"2105","DOI":"10.1080\/01621459.2023.2249642","article-title":"A nonstationary soft partitioned Gaussian process model via random spanning trees","volume":"119","author":"Luo","year":"2024","journal-title":"J. Am. Statist. Assoc"},{"key":"2025062607282393700_asaf031-B31","first-page":"2019","author":"Madry","year":"2015"},{"key":"2025062607282393700_asaf031-B32","doi-asserted-by":"crossref","first-page":"1215","DOI":"10.1214\/aop\/1176991686","article-title":"Covering problems for Markov chains","volume":"16","author":"Matthews","year":"1988","journal-title":"Ann. Prob"},{"key":"2025062607282393700_asaf031-B33","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1007\/s11222-006-5535-3","article-title":"Tractable Bayesian learning of tree belief networks","volume":"16","author":"Meil\u0103","year":"2006","journal-title":"Statist. Comp"},{"key":"2025062607282393700_asaf031-B34","first-page":"1","article-title":"Learning with mixtures of trees","volume":"1","author":"Meil\u0103","year":"2000","journal-title":"J. Mach. Learn. Res."},{"key":"2025062607282393700_asaf031-B35","volume-title":"Matrix Analysis and Applied Linear Algebra","author":"Meyer","year":"2023"},{"key":"2025062607282393700_asaf031-B36","first-page":"619","article-title":"Density modeling and clustering using Dirichlet diffusion trees","volume":"7","author":"Neal","year":"2003","journal-title":"Bayesian Statist"},{"key":"2025062607282393700_asaf031-B37","doi-asserted-by":"crossref","DOI":"10.1093\/biomtc\/ujad009","article-title":"A Bayesian survival treed hazards model using latent Gaussian processes","volume":"80","author":"Payne","year":"2024","journal-title":"Biometrics"},{"key":"2025062607282393700_asaf031-B38","doi-asserted-by":"crossref","first-page":"1389","DOI":"10.1002\/j.1538-7305.1957.tb01515.x","article-title":"Shortest connection networks and some generalizations","volume":"36","author":"Prim","year":"1957","journal-title":"Bell Syst. Tech. J"},{"key":"2025062607282393700_asaf031-B39","doi-asserted-by":"crossref","DOI":"10.1137\/1.9780898718003","volume-title":"Iterative Methods for Sparse Linear Systems","author":"Saad","year":"2003"},{"key":"2025062607282393700_asaf031-B40","doi-asserted-by":"crossref","first-page":"214","DOI":"10.1145\/3188745.3188852","volume-title":"Proc. 50th Ann. ACM SIGACT Symp. Theory Comp","author":"Schild","year":"2018"},{"key":"2025062607282393700_asaf031-B41","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1007\/s00026-006-0279-5","article-title":"Properties of subtree-prune-and-regraft operations on totally-ordered phylogenetic trees","volume":"10","author":"Song","year":"2006","journal-title":"Ann. Combinat"},{"key":"2025062607282393700_asaf031-B42","doi-asserted-by":"crossref","first-page":"1001","DOI":"10.1093\/oxfordjournals.molbev.a003872","article-title":"Bayesian selection of continuous-time Markov chain evolutionary models","volume":"18","author":"Suchard","year":"2001","journal-title":"Molec. Biol. Evol"},{"key":"2025062607282393700_asaf031-B43","first-page":"1","article-title":"Bayesian space-time partitioning by sampling and pruning spanning trees","volume":"20","author":"Teixeira","year":"2019","journal-title":"J. Mach. Learn. Res."},{"key":"2025062607282393700_asaf031-B44","doi-asserted-by":"crossref","first-page":"e0131739","DOI":"10.1371\/journal.pone.0131739","article-title":"Overfitting Bayesian mixture models with an unknown number of components","volume":"10","author":"Van Havre","year":"2015","journal-title":"PloS One"},{"key":"2025062607282393700_asaf031-B45","first-page":"296","volume-title":"Proc. 28th Ann. ACM Symp. Theory Comp","author":"Wilson","year":"1996"},{"key":"2025062607282393700_asaf031-B46","doi-asserted-by":"crossref","first-page":"44","DOI":"10.1198\/106186007X180426","article-title":"Bayesian CART: prior specification and posterior simulation","volume":"16","author":"Wu","year":"2007","journal-title":"J. Comp. Graph. Statist"},{"key":"2025062607282393700_asaf031-B47","doi-asserted-by":"crossref","first-page":"580","DOI":"10.1007\/s11336-022-09887-1","article-title":"A tensor-EM method for large-scale latent class analysis with binary responses","volume":"88","author":"Zeng","year":"2023","journal-title":"Psychometrika"}],"container-title":["Biometrika"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/biomet\/advance-article-pdf\/doi\/10.1093\/biomet\/asaf031\/62932103\/asaf031.pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/biomet\/article-pdf\/112\/2\/asaf031\/62932103\/asaf031.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/biomet\/article-pdf\/112\/2\/asaf031\/62932103\/asaf031.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,26]],"date-time":"2025-06-26T11:28:37Z","timestamp":1750937317000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/biomet\/article\/doi\/10.1093\/biomet\/asaf031\/8113846"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"references-count":47,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,3,16]]}},"URL":"https:\/\/doi.org\/10.1093\/biomet\/asaf031","relation":{},"ISSN":["1464-3510"],"issn-type":[{"value":"1464-3510","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2025]]},"published":{"date-parts":[[2025]]},"article-number":"asaf031"}}