Hostname: page-component-586b7cd67f-g8jcs Total loading time: 0 Render date: 2024-11-28T04:47:39.891Z Has data issue: false hasContentIssue false
  • English
  • Français

Perfect sampling methods for random forests

Part of: Probabilistic methods, simulation and stochastic differential equations Graph theory

Published online by Cambridge University Press:  01 July 2016

Hongsheng Dai
Hongsheng Dai*
Affiliation:
Lancaster University
*
∗ Postal address: Department of Mathematics and Statistics, Fylde College, Lancaster University, Lancaster LA1 4YF, UK. Email address: [email protected]
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

A weighted graph G is a pair (V, ℰ) containing vertex set V and edge set ℰ, where each edge e ∈ ℰ is associated with a weight We. A subgraph of G is a forest if it has no cycles. All forests on the graph G form a probability space, where the probability of each forest is proportional to the product of the weights of its edges. This paper aims to simulate forests exactly from the target distribution. Methods based on coupling from the past (CFTP) and rejection sampling are presented. Comparisons of these methods are given theoretically and via simulation.

Keywords

Coupling from the pastMCMCperfect samplingrejection samplingtrees and forests

MSC classification

Primary: 65C05: Monte Carlo methods 65C50: Other computational problems in probability
Secondary: 05C80: Random graphs
Type
General Applied Probability
Information
Advances in Applied Probability , Volume 40 , Issue 3 , September 2008 , pp. 897 - 917
Copyright
Copyright © Applied Probability Trust 2008 

References

Aldous, D. J. (1990). The random walk construction of uniform spanning trees and uniform labelled trees. SIAM J. Discrete Math. 3, 450–465.CrossRefGoogle Scholar
Broder, A. (1989). Generating random spanning trees. In Proc. 30th IEEE Symp. Foundations of Computer Science, IEEE, New York, pp. 442–447.Google Scholar
Calkin, N., Merino, C., Noble, S. and Noy, M. (2003). Improved bounds for the number of forests and acyclic orientations in the square lattice. Electron. J. Combinatorics 10, R4.CrossRefGoogle Scholar
Colbourn, C. J., Day, R. R. J. and Nel, L. D. (1989). Unranking and ranking spanning trees of a graph. J. Algorithms 10, 271–286.CrossRefGoogle Scholar
Dai, H. (2007). Perfect simulation methods for Bayesian applications. , University of Oxford.Google Scholar
Dawid, A. P. and Lauritzen, S. L. (1993). Hyper Markov laws in the statistical analysis of decomposable graphical models. Ann. Statist. 21, 1272–1317.CrossRefGoogle Scholar
Giudici, P. (1996). Learning in graphical Gaussian models. In Bayesian Statistics 5, Oxford University Press, pp. 621–628.CrossRefGoogle Scholar
Guenoche, A. (1983). Random spanning tree. J. Algorithms 4, 214–220.CrossRefGoogle Scholar
Huber, M. (2004). Perfect sampling using bounding chains. Ann. Appl. Prob. 14, 734–753.CrossRefGoogle Scholar
Jones, B. et al. (2005). Experiments in stochastic computation for high-dimensional graphical models. Statist. Sci. 4, 388–400.Google Scholar
Jones, B. D., Pittel, B. G. and Verducci, J. S. (1999). Tree and forest weights and their application to nonuniform random graphs. Ann. Appl. Prob. 9, 197–215.CrossRefGoogle Scholar
Møller, J. (1999). Perfect simulation of conditionally specified models. J. R. Statist. Soc. B 61, 251–264.CrossRefGoogle Scholar
Propp, J. G. and Wilson, D. B. (1996). Exact sampling with coupled Markov chains and applications to statistical mechanics. Random Structures Algorithms 9, 223–252.3.0.CO;2-O>CrossRefGoogle Scholar
Propp, J. G. and Wilson, D. B. (1998). How to get an exact sample from a generic Markov chain and sample a random spanning tree from a directed graph, both within the cover time. J. Algorithms 27, 170–217.CrossRefGoogle Scholar
Takács, L. (1990). On the number of distinct forests. SIAM J. Discrete Math. 3, 574–581.CrossRefGoogle Scholar