Perfect sampling methods for random forests

Hongsheng Dai

Research output: Contribution to journalArticlepeer-review


A weighted graph G is a pair (V, E) containing vertex set V and edge set E, where each edge e ∈ 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.
Original languageEnglish
Pages (from-to)897-917
Number of pages21
JournalAdvances in Applied Probability
Issue number3
Publication statusPublished - 2008


  • Coupling from the past
  • MCMC
  • perfect sampling
  • rejection sampling
  • trees and forests


Dive into the research topics of 'Perfect sampling methods for random forests'. Together they form a unique fingerprint.

Cite this