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.

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
**

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 dierent distribution. An example is the Ising model, which has several dierent 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
**

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)
**

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
**

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

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
**

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
**

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)
**

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
**

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.

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)

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)

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

**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

**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

**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

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**

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

**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