Archive for category Information Theory and Applications
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.
I’m excited to be attending the 2011 Information Theory and Applications (ITA) Workshop in San Diego, CA. Their organization is interesting. The organizers invite keynote speakers, one of whom this year is Xiao-Li Meng. Then the keynote speakers are allowed to invite a second tier of people to bolster the talks in an area. Since Xiao-Li is speaking on Monte Carlo methods, he extended me an invitation. Not 100% sure yet what I’ll be talking about, but a good guess is that perfect simulation will be involved somehow!