ABSTRACT
Chapter 2 presented the acceptance/rejection (AR) protocol, which runs into trouble when naively applied to permutation problems such as estimating the permanent and high-dimensional Markov random field problems, such as sampling from the Ising model. This is because typically the number of combinatorial objects in a set grows exponentially in the dimension. In this chapter three ideas are introduced to deal with this problem, sequential acceptance/rejection (SAR), partially recursive acceptance/rejection (PRAR), and popping. Together with the ability to preprocess a given problem instance, SAR gave the first perfect simulation algorithms for estimating the permanent that has provably polynomial time over a nontrivial subclass of nonnegative matrices. PRAR allows the acceptance/rejection approach to be applied to Markov random fields such as the Ising or autonormal model without involving Markov chains in any way. Popping allows the pieces of the sample that are blocking acceptance to be pruned away, giving a perfect simulation algorithm for sampling from the rooted trees of a graph.
