This site supported by NSF CAREER grant DMS-05-48153. In this section the slides for many research talks that I have given can be uploaded. Because I usually give more than one talk on a given subject, the talks are organized by topic, and then chronologically from most recent to oldest within a topic.

Adaptive cooling schedules for the product estimator

The product estimator has been of enormous theoretical importance in computer science, but has been little used in statistical applications. Two reasons include difficulty in building a cooling schedule, and the large constant in the running time. This work is an attempt to change that, by introducing an algorithm called "The Tootsie Pop Algorithm", or TPA, that takes care of both problems. The cooling schedule is automatically generated in the algorithm, and the constant in front can be eliminated.

Claremont Colleges Colloquim, 18 Nov, 2009

Better numerical integration through randomness

Joint Statistical Meetings, 5 Aug, 2009

Speeding up the product estimator using random temperatures


Reductions for the Ising model

Polynomial time reductions between problems have long been used to delineate problem classes. Simulation reductions also exist, where an oracle for simulation from a probability distribution is employed together with an oracle for Bernoulli draws to obtain a draw from a di erent distribution. An example is the Ising model, which has several di erent characterizations, including the random cluster view and the spins view. The well-known Swendsen-Wang algorithm gives simulation reductions from random clusters to spins, and from spins to random clusters. Here a third characterization of the Ising model called the subgraphs view is considered. In this work it is shown how to draw a subgraphs state given a random cluster state, and a random cluster state given a subgraphs state. This answers a long standing question of whether such a direct relationship between the subgraphs view and other versions of the Ising model existed. Moreover, these reductions result in the rst method for perfect simulation from the subgraphs world and a new Swendsen-Wang style Markov chain for the Ising model. The method used is to write the desired distribution with set parameters as a mixture of distributions where the parameters are at their extreme values.

AMS Fall Western Sectional Meeting, 8 Nov, 2009

Simulation reductions for the Ising model


Inference using repusive point processes

Spatial data are often more dispersed than would be expected if the points were independently placed. Such data can be modeled with repulsive point processes, where the points appear as if they are repelling one another. Various models have been created to deal with this phenomenon. Matérn created three algorithms that generate repulsive processes. The difficulty in using these methods for Bayesian inference lies in numerically integrating over a high dimensional space. In this work, a perfect sampling method and product estimator are developed for using Matérn Type III processes to approximate the likelihood and posterior values for data.

EPSRC Symposium Workshop on Markov Chain-Monte Carlo, 17 March, 2009

Perfect simulation of Matérn Type III point processes

Cornell University School of Operations Research and Industrial Engineering Colloquium,16 September, 2008

Perfect Simulation of Matérn Type III Repulsive Point Processes

ISBA 2008: 9th ISBA World Meeting

Perfect Simulation of Matérn Type III Repulsive Point Processes (poster)


Linear Extensions of a Poset

A partially ordered set (or poset for short) is a collection of relations that are consistent with many permutations. These permutations are called linear extensions. Counting how many linear extensions a poset has is a #P problem, and so approximation algorithms are used. In this talk, the speed of the fastest method for approximation is improved by a factor of n / (ln n)^2. This is accomplished by generalizing an earlier method of mine for generating uniformly from the set of permutations consistent with a poset. Applications of this approach arise in machine learning and convex rank tests in nonparameteric inference.

CASTA (Computational Algebraic Statistics, Theory and Applications) 2008

A new algorithm for approximation of the number of linear extensions of a poset


An overview of Perfect Sampling

Perfect sampling algorithms generate samples exactly from a target distribution that is typically described by an unnormalized density, where the normalization constant is difficult to compute. Early perfect samplers were based on classical Markov chain approaches, but newer approaches employ very different methods. In this talk I will give an overview of four different methodologies for creating perfect sampling algorithms: Coupling From the Past, the Randomness Recycler, Sequential Acceptance/Rejection, and Partial Recursive Acceptance/Rejection, illustrating their use through examples and simple analyses of their running times.

Workshop on Analysis of Monte Carlo Methods 2007 Dec 1 and 2

Perfect sampling


Perfect simulation for the permanent

Finding the permanent of a matrix with nonnegative entries is a long studied problem with many innovative approaches. To date, the Markov chain methods have been successful in creating a polynomial time algorithm, but the degree of the running time is still very large. In this talk an acceptance/rejection method is constructed that has much faster running time on a restricted set of matrices.

DIMACS Workshop on Markov chain Monte Carlo methods. June 5, 2007

Fast approximation of the permanent of very dense matrices using sequential acceptance/rejection


Swap moves for point processes on continuous regions

Regular birth-death chains for point process allow either a birth where a single point is added to the configuration, or a death where a single point is removed. The introduction of a swap move, where a point is added and another removed in the same step, can be helpful in accelerating the mixing time of a Markov chain. While this move had been in use in discrete contexts for some time, it had never made it over to continuous settings. In this work, the theoretical justification for these swap moves on continuous state spaces is established, as well as perfect sampling algorithms using these moves. These are then tested to explore how much improvement can be obtained from this type of move.

University of Aalborg. 20 May 2009

Perfect simulation for repulsive point processes: Why swapping at birth is a good thing

University of Minnesota School of Statistics Seminar. October 11, 2007

Perfect simulation for repulsive point processes

Duke Mathematics Graduate-Faculty Seminar. April 13, 2007

Swapped at birth: Building a better spatial point process


History of Monte Carlo techniques

This is an overview talk of some of the history of Monte Carlo methods, specifically focusing on problems where the existence of a phase transition can mean the difference between a rapidly mixing and a slowly mixing Markov chain. It includes a brief look at basic Monte Carlo Markov chain methodology, as well as a look at the Randomness Recycler for the hard core gas model.

Duke graduate recruiting weekend. March 4, 2007

Why water freezes (a probabilistic view of phase transitions)


Randomness Recycler on arbitrary state spaces

The randomness recyler (RR) protocol has been utilized to create perfect sampling algorithms for several problems on discrete state spaces. In this talk I show how to extend the RR methodology to arbitrary spaces. As an example, this new approach is applied to sampling from the autonormal model, which arises in Bayesian image analysis. Under certain ranges of parameters of the problem this yields an interruptible linear time algorithm for generating random variates.

New Developments in MCMC workshop at University of Warwick. August 23, 2006

Perfect Simulation with the Randomness Recycler for arbitrary state spaces


Advanced Acceptance/Rejection techniques

UC Davis Department of Mathematics Seminar. March 05, 2006

Advanced Acceptance/Rejection Methods for Monte Carlo Algorithms

This is a survey talk of methods related to the acceptance/rejection algorithm. Both the Randomness Recycler (RR) and Sequential Acceptance/Rejection can be viewed as extensions of this basic technique. Therefore in this talk I first explore the basic acceptance/rejection technique, before going on to illustrate Sequential A/R with the permanent problem and RR with the Ising model.


Non-Markovian coupling for Markov chains

IMS meeting on Monte Carlo Markov chain methods in Singapore, March 11, 2004

Time dependent update functions for perfect sampling

Perfect sampling algorithms generate random variates drawn exactly from a target distribution without the need to know mixing times of Markov chains. The most widespread technique for perfect sampling, Coupling From the Past (CFTP) used a time homogeneous update function: at every time step the state was advanced by using a random draw from the same family of functions. However, the basic technique remains the same if the update function is allowed to change with each time step. By varying the family of functions that is used based on prior outcomes, algorithms can be made both faster and easier to implement. This technique is equivalent to using a non-Markovian coupling of the chain. Examples for discrete and continuous state spaces will be considered.

(OpenOffice 1.1.0) (pdf)


Hardy-Weinberg Equilibrium

One of the topics studied by the Stochastic Computation program at SAMSI in 2002-2003 was Hardy-Weinberg equilibrium, a driving principle in population genetics. I gave several talks on the subject to different audiences. Each talk is different, but contains common elements, such as a description of Mendelian genetics and the basic Hardy Weinberg model.

Stat 395-Talk aimed at graduate students in statistics 9-29-2003
Exact Sampling for Hardy Weinberg Equilibrium (OpenOffice 1.1.0)(pdf)


The Randomness Recycler

These two talks were given in Germany in December of 2003. The first talk here gives a general description of perfect sampling, with a description of coupling from the past, bounding chains, and a description of the Randomness Recycler. The second talk is even more extensive, and also gives a reducible approach to Monte Carlo estimation of integrals where the variance of the function does not affect the quality of the estimate.

Oberwolfach December 2003 Applied Probability Plenary lecture
(OpenOffice 1.1.0)(pdf)

University of Ulm December 2003 Mathematics Colloquium
(OpenOffice 1.1.0)(pdf)


Perfect Sampling for some Mixtures of Distributions

When trying to determine an unknown mixing parameter from data, a Bayesian analysis can be performed via Monte Carlo simulation from a high dimensional distribution (the number of dimensions is the number of data points taken) where the normalizing constant is unknown. The Randomness Recycler method can be applied to this problem to obtain samples quickly under certain conditions.

SAMSI September 2002

(OpenOffice 1.1.0)(pdf)

Introduction to the Randomness Recycler

This is a basic tutorial to the Randomness Recycler (RR) method, which allows sampling from high dimensional distributions where the normalizing constant is unknown without the need to find the normalizing constant. RR is an example of a perfect sampling method: the samples generated come exactly from the desired distribution. Unlike earlier perfect sampling methods, RR does not use the classical Markov chain method as a starting point, instead attempting the build up the sample one dimension at a time.

Cape Cod September 2002

(OpenOffice 1.1.0)(pdf)

A New Approach to Perfect Sampling From Nasty Distributions

The problem of how to generate samples from high dimensional distributions has applications in a wide variety of areas, from statistical mechanics to Bayesian statistics. Commonly, Monte Carlo Markov chain techniques are used, where a Markov chain is run "for a long time". Our approach to these problems is fundamentally different, and requires no knowledge of how long to run the chain. Unlike other perfect sampling techniques, our method is not bound to the classic Markov chains for these problems, and so is the first to achieve linear time algorithms for sampling from these distributions.

Stanford Statistics Colloquium July 11, 2000

(postscript)

A New Approach to Perfect Sampling From Nasty Distributions

The problem of how to generate samples from high dimensional distributions has applications in a wide variety of areas, from statistical mechanics to Bayesian statistics. Commonly, Monte Carlo Markov chain techniques are used, where a Markov chain is run "for a long time". Our approach to these problems is fundamentally different, and requires no knowledge of how long to run the chain. Unlike other perfect sampling techniques, our method is not bound to the classic Markov chains for these problems, and so is the first to achieve linear time algorithms for sampling from these distributions.

IBM Almaden Sept. 14, 2000

(postscript)


Bounding Chains

To use protocols such as coupling from the past (CFTP) for perfect sampling, some means of determining when complete coupling has occurred. Bounding chains are one method for doing so. They often can be useful in obtaining a bound on the running time of the procedure as well. While not as strong theoretically as other methods such as monotonicity, they are far more widely applicable.

Electrical and Computer Engineering NC State Feb. 14, 2003

Bounding Chain Techniques for Perfect Sampling

(OpenOffice 1.1.0)(pdf)


Random Topics

Stanford Probability Seminar Febuary 7, 2000

Acceptance/Rejection Sampling from Restricted Permutations

In restricted permutations, each element $i$ may only be moved to a restricted set of positions $S_i$. The problem of sampling uniformly from the set of restricted permutations turns out to be quite difficult. Applications for such samples include estimating the permanent, generating random Latin rectangles, and finding the level of nonparametric tests for correlation in doubly truncated data sets. We build two approaches for this problem based on acceptance/rejection techniques. One approach is the first to generate exact samples in polynomial time in polynomial time over a nontrivial set of restrictions. The second approach proves useful when dealing with interval permutations, and we apply it to a problem of quasar luminosity evolution studied by Efron and Petrosian.

Graduate/Faculty Seminar Duke University

(postscript)

Numerical Integration Monte Carlo style

This talk describes how to use the reducibility of the problem of integration together with Monte Carlo samples, to achieve approximations to integrals that are correct with high probability.

Graduate/Faculty Seminar Duke University

(OpenOffice 1.1.0) (pdf)

Stochastic Computation

This was a short 10 minute talk designed to introduce undergraduates to work going on at SAMSI in the Stochastic Computation program. It illustrates Markov chain Monte Carlo techniques with a contingency table example.

(OpenOffice 1.1.0) (pdf)


Back to Mark's Home Page