UC Davis Mathematics

Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Advanced acceptance/rejection methods for Monte Carlo algorithms

Mathematical Physics & Probability

Speaker: Mark Huber, Duke University
Location: 2112 MSB
Start time: Tue, Mar 14 2006, 3:10PM

Simple acceptance/rejection has been a valuable tool for over half a century for obtaining variates from distributions with unknown normalizing constants. Unfortunately their performance typically degrades exponentially in the size of the problem. I will look here at three methods that solve this difficulty for three different problems. First I will examine generating variates from the tails of sums of random variables, then look at generating perfect matchings of regular graphs, and finally employ the Randomness Recycler method on the Ising model.