Algorithms for Perfect Sampling

Broadly speaking, Perfect Sampling refers to a method by which a stochastic input can be translated to a corresponding stochastic output with no estimation or addition of noise. In the Markov chain literature, this is when the desired output is the stationary distribution of a Markov chain, the input being observations from the chain. See David Wilson's primer on the history of the method, notably the development of Coupling From the Past.

Projects:

• Exact Simulation and Error-Controlled Sampling via Regeneration and a Bernoulli Factory, with Jose Blanchet. This version was presented at the New England Statistics Symposium in 2007 and won an IBM T.J. Watson Student Paper Award. This incorporates two separate sampling methods:
  • A Bernoulli Factory, which takes an input of a stream of Bernoulli random variables (coin flips) with unknown but fixed success probability p and outputs a stream of Bernoullis with success probability f(p), where the function itself is known.
  • A regeneration scheme, wherein a Markov chain can be divided into subsections that are independent to each other and identically distributed.