Posts Tagged PRAR
The talk that I gave at UMSL can now be downloaded here. This talk describes two different protocols for perfect simulation. The first, Partially Recursive Acceptance Rejection, gives an easy way to generate perfect samples from loosely coupled Markov random fields (such as the Ising model) in linear time without building a Markov chain at all for the problem.
The second part discusses Sequential Acceptance Rejection, a method that has proved useful for problems like approximating the permanent in dense problem instances.