A new algorithm for approximation of the number of
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
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)
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
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
