The invited talk that I presented at the 2011 Information Theory and Applications conference at UC San Diego has now been posted to my webpage here. This is a short talk that introduces the use of the Partially Recursive Acceptance Rejection.
Abstract. The Acceptance/Rejection (AR) protocol can be used to design perfect simulation algorithms: methods that draw random variates exactly from an unnormalized target distribution by employing a recursive structure. For high dimensional problems such as the Ising model, the recursive calls in AR can result in a tree that is exponentially large in the size of the problem. In this talk, I will introduce a new protocol for perfect sampling called Partially Recursive Acceptance Rejection (PRAR). The idea is to prune the recursion tree as much as possible by ignoring branches that do not affect the final output. The result is a method for perfect simulation that can often be proved to run in polynomial time. For the Ising model, the method can be shown to run in time linear in the number of nodes and edges for parameters that lie above a threshold. This behavior is similar to what is known for another popular perfect simulation protocol, Coupling From the Past.