The Fundamental Theorem of Perfect Simulation

03/31/2015 - 12:15pm
03/31/2015 - 1:10pm
Mark Huber (CMC)

In an induction, a problem is reduced recursively to a base case. In perfect simulation, there is no base case. Instead, a problem is randomly reduced to one of two problems, one of which is the original problem! The Fundamental Theorem of Perfect Simulation says that as long as the chance that the reduction does not require the original problem is greater than zero, then such a procedure terminates with probability 1 in finite time. In this talk, I'll explore and prove this fascinating theorem, and consider multiple ways in which it can be used to draw samples from one of the cornerstone models of statistical physics, the Ising model.

Mudd Science Library 126, Pomona College