# Mark Huber Publications

The Randomness Recycler: A new technique for perfect sampling

J. A. Fill, M. L. Huber,
Proceedings of the 41th Annual IEEE Symposium on the Foundations
of Computer Science (2001), pp. 503–511.

*Abstract: *
For many probability distributions of interest, it is quite
difficult to obtain samples efficiently. Often, Markov chains
are employed to obtain approximately random samples from
these dsitributions. The primary drawback to traditional
Markov chain methods is that the mixing time of the chain
is usually unknown, which makes it impossible to determine
how close the output samples are to having the target distribution.
Here we present a new protocol, the randomness recycler (RR), that
overcomes this difficulty. Unlike classical Markov chain
approaches, and RR-based algorithm creates samples drawn exactly
Markov chains, but RR does not use the traditional Markov chain
at all. While by no means universally useful, RR does apply to
a wide variety of problems. In restricted instaqnces of certain
problems, it gives the first expected linear time algorithms for
generating samples. Here we apply RR to self-organzing lists,
the Ising model, random independent sets, random colorings, and the
random cluster model.

This site supported by NSF CAREER grant DMS-05-48153. Last update: 04 December 2009. Note: All downloads provided solely for use within the restrictions of the Fair Use Act, and all copyrights remain with their respective owners.