Mark Huber Publications

Perfect Sampling with Bounding Chains
M. L. Huber, Ph.D. thesis, Cornell University (1999).

Abstract:

In Monte Carlo simulation samples are drawn from a distribution to estimate properties of the distribution that are too diffcult to compute analytically. This has applications in numerous fields including optimization, statistics, statistical mechanics, genetics, and the design of approximation algorithms.

In the Monte Carlo Markov chain method, a Markov chain is constructed which has the target distribution as its stationary distribution. After running the Markov chain long enough, the distribution of the final state will be close to the stationary distribution of the chain. Unfortunately, for most Markov chains, the time needed to converge to the stationary distribution (the mixing time) is completely unknown.

Here we develop several new techniques for dealing with unknown mixing times. First we introduce the idea of a bounding chain which delivers a wealth of information about the chain. Once a bounding chain is created for a particular chain it is possible to empirically estimate the mixing time of the chain. Using ideas such as coupling from the past and the Fill-Machida-Murdoch-Rosenthal algorithm bounding chains can also become the basis of perfect sampling algorithms. Unlike traditional MonteCarlo Markov chain methodsm these algorithms draw samples which are exactly distributed according to the stationary distribution.

We develop bounding chains for several Markov chains of practical interest chains from statistical mechanics like the Swendsen-Wang chain for the Ising model the Dyer-Greenhill chain for the discrete hard core gas model, and the continuous Widom-Rowlinson mixture model with more than three components in the mixture. We also give techniques for sampling from weighted permutations which have applications in database access and nonparametric statistical tests. In addition, we present here bounding chains for a variety of Markov chains of theoretical interest, such as the k coloring chain, the sink free orientation chain, and the antiferromagnetic Potts model with more than three colors. Finally we develop new Markov chains and bounding chains for the continuous hard core gas model and the Widom-Rowlinson model which are provably faster in practice.