Random sampling has found numerous applications in physics, statistics, and computer science. Perhaps the most versatile method of generating random samples from a probability space is to run a Markov chain. But for how many steps?

In most cases one simply does not know how many Markov chain steps are needed to get a sufficiently random state. There is a large literature of heuristic algorithms for inferring when enough steps have been taken, but they are non-rigorous, and one never knows for sure that an adequate number of steps have been taken. These heuristic algorithms are beyond the scope of this bibliography, but the interested reader is referred to some lecture notes by Sokal and the MCMC Preprint Service.

In the past decade there is been much research on obtaining rigorous bounds of how many Markov chain steps are needed to generate a random sample. Sometimes these bounds are tight, sometimes they are unduly pessimistic. The interested reader is referred to a survey by Diaconis and Saloff-Coste and a survey by Jerrum and Sinclair; the size of this literature makes it beyond the scope of this bibliography.

In recent years there have been a large number of algorithms developed for sampling from the steady state distribution of suitably well-structured Markov chains, which require no a priori knowledge of how long the Markov chains take to get mixed. The algorithms determine on their own, during run time, how many steps to run the Markov chain. It is these algorithms that are the focus of this bibliography. Most of these algorithms return samples that are distributed exactly according to the stationary distribution of the Markov chain, but a few return samples that have some bias ε that the user can make as small as desired. Since the focus of this bibliography is on working computer algorithms, the symbol is placed next to those articles that contain simulation results or give sample outputs. Each annotated entry contains links relevant to the paper, giving the article's abstract (click on the title) and authors' homepages when available, as well as links to online preprints. Several of the annotations were contributed by people other than the maintainer.

It has been pointed out that ``stationary stopping times'' may also be considered to be algorithms for sampling from a Markov chain's stationary distribution. However, these Markov chains typically have state spaces such as the symmetric group or the hypercube, for which one already knows how to effectively generate a random sample on a computer. Rather, the point of studying these stopping times is to understand interesting mathematical processes, such as shuffling a deck of cards. (A notable exception is Fill's algorithm.) Since the literature on these stopping times is sizable, only those articles with an algorithmic theme are included. The reader interested in stopping times is referred to the articles by Aldous and Diaconis and Diaconis and Fill, which contain many references.

Also relevant to the present bibliography is a literature on backwards compositions of random maps. The backwards composition of random maps can be used to define a ``stochastically recursive sequence'' of points from the state space. The articles from this literature study when this sequence of points converge almost surely, since convergence implies the existence of a stationary distribution for the Markov chain. (Existence can be nontrivial for infinite state spaces.) If one has the additional conditions that 1) the convergence occurs after a finite number steps, and 2) one can determine when this convergence has occurred, then one may use the technique of ``coupling from the past'', which is used in several the articles listed below, to generate random samples from the state space. (There are numerous examples in which conditions 1 or 2 do not hold.) Diaconis and Freedman give a survey of the literature on stochastically recursive sequences; a few representative articles are listed below.

David J. Aldous. A random walk construction of uniform spanning trees and uniform labelled trees. SIAM Journal on Discrete Mathematics, 3(4):450--465, 1990.

These two articles give the same independently discovered random-walk based algorithm for generating random spanning trees of a graph. The algorithm uses a Markov chain on the set of spanning trees of an undirected graph to return a (perfectly) random spanning tree. Broder uses the algorithm to analyze the random walk on a ring. Aldous uses the algorithm to determine the properties of random trees and to compute some non-trivial probabilities pertaining to the random walk in the plane. (There is another random tree algorithm based on computing determinants.)

This paper explores what is possible and what is not, and was the first paper to show that it is possible to obtain unbiased samples from the steady state distribution of a finite Markov chain by observing it, provided it is irreducible and one knows how many states it has. Equivalently, there is a universal randomized stationary stopping time that works for all (irreducible) Markov chains with a given (finite) number of states.

Abstract: We present an algorithm which, given a n-state Markov chain whose steps can be simulated, outputs a random state whose distribution is within ε of the stationary distribution, using O(n) space and O(ε^-2 τ) time, where τ is a certain ``average hitting time" parameter of the chain.

Remarks: While not exact, this algorithm was much more efficient than the previous one, and directly stimulated the development of two subsequent exact sampling algorithms. This paper gives the only nontrivial lower bound on the running time of an algorithm for exact sampling from generic Markov chains.

Abstract: We present a polynomial time Monte Carlo algorithm for almost uniformly generating and approximately counting self-avoiding walks in rectangular lattices Z^d. These are classical problems that arise, for example, in the study of long polymer chains. While there are a number of Monte Carlo algorithms used to solve these problems in practice, these are heuristic and their correctness relies on unproven conjectures. In contrast, our algorithm depends on a single, widely-believed conjecture that is weaker than preceding assumptions, and, more importantly, is one which the algorithm itself can test. Thus our algorithm is reliable, in the sense that it either outputs answers that are guaranteed, with high probability, to be correct, or finds a counter-example to the conjecture.

Abstract: We give a simple stopping rule which will stop an unknown, irreducible $n$-state Markov chain at a state whose probability distribution is exactly the stationary distribution of the chain. The expected stopping time of the rule is bounded by a polynomial in the maximum mean hitting time of the chain. Our stopping rule can be made deterministic unless the chain itself has no random transitions.

Remarks: This paper gives the first (universal) exact sampling algorithm that runs in time that is polynomial in certain parameters associated with the Markov chain. Gives a deterministic stationary stopping time that works when the Markov chain itself is not deterministic. The paper also contains a pretty lemma on random trees that is of independent interest.

Abstract: For many applications it is useful to sample from a finite set of objects in accordance with some particular distribution. One approach is to run an ergodic (i.e., irreducible aperiodic) Markov chain whose stationary distribution is the desired distribution on this set; after the Markov chain has run for M steps, with M sufficiently large, the distribution governing the state of the chain approximates the desired distribution. Unfortunately it can be difficult to determine how large M needs to be. We describe a simple variant of this method that determines on its own when to stop, and that outputs samples in exact accordance with the desired distribution. The method uses couplings, which have also played a role in other sampling schemes; however, rather than running the coupled chains from the present into the future, one runs from a distant point in the past up until the present, where the distance into the past that one needs to go is determined during the running of the algorithm itself. If the state space has a partial order that is preserved under the moves of the Markov chain, then the coupling is often particularly efficient. Using our approach one can sample from the Gibbs distributions associated with various statistical mechanics models (including Ising, random-cluster, ice, and dimer) or choose uniformly at random from the elements of a finite distributive lattice.

Remarks: This paper gives an algorithm, monotone coupling from the past, for exact sampling with Markov chains on huge state spaces. Since monotone-CFTP relies on the Markov chain having special structure, it is not ``universal'' as several of the above algorithms are, but it is practical for a surprising number of previously studied Markov chains. Includes simulation results for the random cluster and dimer models.

Abstract: I describe a simple procedure for investigating the convergence properties of Markov Chain Monte Carlo sampling schemes. The procedure employs multiple runs from a sampler, using the same random deviates for each run. When the sample paths from all sequences converge, it is argued that approximate equilibrium conditions hold. The procedure also provides a simple diagnostic for detecting modes in multimodal posteriors. Several examples of the procedure are provided. In Ising models, the relation between the correlation parameter and the convergence rate of rudimentary Gibbs samplers is investigated. In another example, the effects of multiple modes on the convergence of coupled paths are explored using mixtures of bivariate normal distributions. The technique is also used to evaluate the convergence properties of a Gibbs sampling scheme applied to a model for rat growth rates (Gelfand et al 1990).

Remarks: While technically not a paper on exact sampling, this paper investigates how the mixing time of a Markov chain may be inferred by running a large number of coupled simulations until they coalesce. The initial states of the Markov chains are chosen at random, and if the probability of rejection in rejection sampling is known, then rigorous estimates of the mixing time are given. Includes the (independently made) observation that for monotone Markov chains, only two coupled states need to be simulated. Includes simulation results. Additional articles that take a similar approach are available from Johnson's homepage.

Abstract: Consider the following Markov chain, whose states are all domino tilings of a 2n X 2n chessboard: starting from some arbitrary tiling, pick a 2 X 2 window uniformly at random. If the four squares appearing in this window are covered by two parallel dominoes, rotate the dominoes in place. Repeat many times. This process is used in practice to generate a random tiling, and is a key tool in the study of the combinatorics of tilings and the behavior of dimer systems in statistical physics. Analogous Markov chains are used to randomly generate other structures on various two-dimensional lattices. This paper presents techniques which prove for the first time that, in many interesting cases, a small number of random moves suffice to obtain a uniform distribution.

Remarks: This paper gives three new Markov chains for sampling certain dimer and ice systems. The focus of this paper is provable running time bounds. Monotone-CFTP may be applied to each of their Markov chains to get an exact algorithm; when this is done, their proofs may be interpreted as a priori bounds on the running time of CFTP, though in practice the exact algorithm runs much more quickly than the bounds suggest.

Remarks: For the particular case of the 2n X 2n chessboard, it is much faster to generate a random spanning tree, and then use a Temperley-like bijection to convert it to a (perfectly) random domino tiling. Their methods apply to more general regions for which such a Temperleyan bijection does not exist.

Abstract: A general problem in computational probability theory is that of generating a random sample from the state space of a Markov chain in accordance with the steady-state probability law of the chain. Another problem is that of generating a random spanning tree of a graph or spanning arborescence of a directed graph in accordance with the uniform distribution, or more generally in accordance with a distribution given by weights on the edges of the graph or digraph. This paper gives algorithms for both of these problems, improving on earlier results and exploiting the duality between the two problems. Each of the new algorithms hinges on the recently-introduced technique of coupling from the past or on the linked notions of loop-erased random walk and ``cycle-popping''.

Remarks: This article gives what are so far the best algorithms for exact sampling on generic Markov chains, as well as the first application of CFTP to a huge non-monotone state space. It gives a universal randomized stationary stopping time that is within a constant factor of optimal, and another algorithm that is faster when the Markov chain can be simulated starting from any state rather than just observed in action. Surprisingly, both algorithms are intimately related to the generation of random spanning trees of a weighted directed graph, and this paper gives tree algorithms that are both faster and more general than the Broder/Aldous algorithm. The algorithms use various versions of CFTP (voter-CFTP, coalescing-CFTP, cover-CFTP, and tree-CFTP), and another technique called cycle popping. (An upcoming book by Lyons and Peres makes use of the cycle-popping algorithm when analyzing essential spanning forests of infinite graphs.) Includes a sample output from the tree algorithm.

Shows how to use the algorithms for random spanning tree generation to solve other random sampling problems. Per Eppstein's description: Shows how to find for any edge weighted graph G an equivalent graph EG such that the minimum spanning trees of G correspond one-for-one with the spanning trees of EG. The equivalent graph can be constructed in time O(m+n log n) given a single minimum spanning tree of G. As a consequence one can find fast algorithms for counting, listing, and randomly generating MSTs. Also discusses similar equivalent graph constructions for shortest paths, minimum cost flows, and bipartite matching.

Abstract: We study the generation of uniformly distributed linear extensions using Markov chains. In particular we show that monotone coupling from the past can be applied in the case of linear extensions of two-dimensional orders. For width two orders a mixing rate of O(n^3 log n) is proved. We conjecture that this is the mixing rate in the general case and support the conjecture by empirical data. On the course we obtain several nice structural results concerning Bruhat order and weak Bruhat order of permutations.

Remarks: Subsequent work confirmed their conjecture.

Abstract: The ideas of Propp and Wilson ("Exact sampling with coupled Markov chains and applications to statistical mechanics", Random Structures and Algorithms, 1996, 9:223-252) for exact simulation of Markov chains are extended to deal with perfect simulation of attractive area-interaction point processes in bounded windows. A simple modification of the basic algorithm is described which provides perfect simulation of the non-monotonic case of the repulsive area-interaction point process. Results from simulations using a C computer program are reported; these confirm the practicality of this approach in both attractive and repulsive cases. The paper concludes by mentioning other point processes which can be simulated perfectly in this way, and by speculating on useful future directions of research.

Remarks: Shows how to do perfect simulations of the area-interaction point process, though the techniques extend to more general point processes. A unique feature of this application is that the Markov chain used is not uniformly ergodic, i.e. its mixing time is infinite. (The state space is an infinite partially ordered set with no top state, and one can find states from which the Markov chain takes arbirtrarily long to equilibrate.) To deal with this problem, Kendall modified monotone-CFTP, replacing references to the (nonexistent) top state with references to a stochastically dominating process. Kendall also shows how to apply CFTP to repulsive point processes, which are anti-monotone. Includes simulation results.

Following up on the previous article, shows how to apply CFTP to attractive birth-death processes and exclusion processes.

Abstract: For a large class of examples arising in statistical physics known as attractive spin systems (e.g., the Ising model), one seeks to sample from a probability distribution π on an enormously large state space, but elementary sampling is ruled out by the infeasibility of calculating an appropriate normalizing constant. The same difficulty arises in computer science problems where one seeks to sample randomly from a large finite distributive lattice whose precise size cannot be ascertained in any reasonable amount of time. The Markov chain Monte Carlo (MCMC) approximate sampling approach to such a problem is to construct and run ``for a long time'' a Markov chain with long-run distribution π. But determining how long is long enough to get a good approximation can be both analytically and empirically difficult. Recently, Jim Propp and David Wilson have devised an ingenious and efficient algorithm to use the same Markov chains to produce perfect (i.e., exact) samples from π. However, the running time of their algorithm is an unbounded random variable whose order of magnitude is typically unknown a priori and which is not independent of the state sampled, so a naive user with limited patience who aborts a long run of the algorithm will introduce bias. We present a new algorithm which (1) again uses the same Markov chains to produce perfect samples from π, but is based on a different idea (namely, acceptance/rejection sampling); and (2) eliminates user-impatience bias. Like the Propp-Wilson algorithm, the new algorithm applies to a general class of suitably monotone chains, and also (with modification) to ``anti-monotone'' chains. When the chain is reversible, naive implementation of the algorithm uses fewer transitions but more space than Propp-Wilson. When fine-tuned and applied with the aid of a typical pseudorandom number generator to an attractive spin system on n sites using a random site updating Gibbs sampler whose mixing time tau is polynomial in n, the algorithm runs in time of the same order (bound) as Propp-Wilson [expectation O(tau log n)] and uses only logarithmically more space [expectation O(n log n), vs. O(n) for Propp-Wilson].

Among other things, this article shows that so long as the user insists on waiting long enough to get at least one random sample, a deadline will not introduce bias. This holds for any sampling procedure, whether the deadline is in terms of Markov chain steps, real time, or any other measure.

Abstract: The elementary problem of exhaustively sampling a finite population without replacement is used as a nonreversible test case for comparing two recently proposed MCMC algorithms for perfect sampling, one based on backward coupling and the other on strong stationary duality. The backward coupling algorithm runs faster in this case, but the duality-based algorithm is unbiased for user impatience. An interesting by-product of the analysis is a new and simple stochastic interpretation of a mixing-time result for the move-to-front rule.

Remark: See also this paper.

Abstract: The area-interaction process and the continuum random-cluster model are characterised in terms of certain functional forms of their respective conditional intensities. In certain cases, these two point process models can be derived from a bivariate point process model which in many respects is simpler to analyse and simulate. Using this correspondence we devise a two-component Gibbs sampler, which can be used for fast and exact simulation by extending the recent ideas of Propp and Wilson. We further introduce a Swendsen-Wang type algorithm. The relevance of the results within spatial statistics as well as statistical physics is discussed.

Remarks: Shows how to apply monotone-CFTP to sample from the Widom-Rowlinson point process. Here there is no top or bottom state, but (in contrast to Kendall's chain) such states can be adjoined to the state space. (The authors instead use two other states, already in the state space, that are just as effective at testing coalescence.) The Widom-Rowlinson model can be marginalized to obtain the attractive area-interaction point process and the continuum random cluster model (with positive integral q). Sampling from the area-interaction process in this way turns out to be faster than (though not as generalizable as) Kendall's approach. The paper also describes a Swendsen-Wang type algorithm, and includes simulation results.

Surveys the spatial point processes, including recent work on exact sampling, and includes simulation results.

Abstract: This survey article describes a method for choosing uniformly at random from any finite set whose objects can be viewed as constituting a distributive lattice. The method is based on ideas of the author and David Wilson for using ``coupling from the past'' to remove initialization bias from Monte Carlo randomization. The article describes several applications to specific kinds of combinatorial objects such as tilings, constrained lattice paths, an alternating sign matrices.

Abstract: A new approach to Markov chain Monte Carlo simulation was recently proposed by Propp and Wilson. This approach, unlike traditional ones, yield samples which have exactly the desired distribution. The Propp-Wilson algorithm requires this distribution to have a certain structure called monotonicity. In this paper an idea of Kendall is applied to show how the algorithm can be extended to the case where monotonicity is replaced by anti-monotonicity. As illustrating examples, simulations of the hard-core model and the random-cluster model are presented.

Abstract: We present a fully-polynomial scheme to approximate the number of independent sets in graphs with maximum degree four. In general, for graphs with maximum degree Δ≥4, the scheme approximates a weighted sum of independent sets. The weight of each independent set is expressed in terms of a positive parameter λ≤ 1/(Δ-3), where the weight of independent set S is λ^|S|. We also prove complementary hardness of approximation results, which show that it is hard to approximate the weighted sum for values of λ > c/Δ for some constant c > 0.

Remarks: Gives a new Markov chain for generating random independent sets with activity λ. When the maximum degree Δ≥4 and λ ≤ 1/(Δ-3), they show that this Markov chain is rapidly mixing. CFTP may be efficiently applied to their Markov chain; when this is done, their proofs (but not the theorem itself) may be interpreted as a priori bounds on the running time of CFTP.

An article by Dyer and Greenhill extends and improves on this one, though itself is not connected to CFTP.

Abstract: Propp and Wilson (1995) described a protocol, called coupling from the past, for exact sampling from a finite distribution using a coupled Markov chain Monte Carlo algorithm. In this paper we extend coupling from the past to various MCMC samplers on a continuous state space; rather than following the monotone sampling device of Propp and Wilson, our approach uses methods related to gamma-coupling and rejection sampling to simulate the chain, and direct accounting of sample paths to check whether they have coupled.

Remarks: Describes a variety of scenarios for which CFTP may be applied to a (non-monotone) continuous state space, giving a sequence of algorithms that start out simple, but become increasingly sophisticated. The methods used are related to gamma-coupling and rejection sampling, and appear to be applicable to Bayesian parameter estimation. Includes a case study comparing the performance of each technique when used to sample from the posterior distribution of a set of pump reliability parameters.

Abstract: In this paper we investigate the application of perfect simulation, in particular Coupling from The Past (CFTP), to the simulation of random point processes. We give a general formulation of the method of dominated CFTP and apply it to the problem of perfect simulation of general locally stable point processes as equilibrium distributions of spatial birth-and-death processes. We then investigate discrete-time Metropolis-Hastings samplers for point processes, and show how a variant which samples systematically from cells can be converted into a perfect version. An application is given to the Strauss point process.

See also the document describing the implementation.

Shows how to take a generic probability distribution on a space, together with a reference distribution from which it is already known how to sample, and construct a certain particular Metropolis-type monotone Markov chain. Coalescence occurs precisely when the rejection sampler with the same reference measure would accept.

Abstract: Algorithms for perfect or exact simulation of random samples from the invariant measure of a Markov chain have received considerable recent attention following the introduction of the "coupling-from-the-past" (CFTP) technique of Propp and Wilson. Here, we place such algorithms in the context of backward coupling of stochastically recursive sequences. We show that although general backward couplings can be constructed for chains with finite mean forward coupling times, and can even be thought of as extending the classical "Loynes schemes" from queuing theory, successful "vertical" CFTP algorithms such as those of Propp and Wilson can be constructed if and only if the chain is uniformly geometric ergodic. We also relate the convergence moments for backward coupling methods to those of forward coupling times: the former typically lose at most one moment compared to the latter.

Remarks: Relates CFTP to more general stochastically recursive sequences, for which one has a sequence of random variables that with probability one converge to a particular value with the right distribution, but for which one isn't necessarily able to determine when this convergence has happened. Studies the moments of the convergence time of stochastically recursive sequences, some of which may be finite with others being infinite.

Show how to apply monotone-CFTP to sample from the steady-state distribution of certain storage systems. Rather than the linear data-flow used in traditional monotone-CFTP, the flow of data through the algorithm is two-dimensional.

Abstract: We discuss how the ideas of producing perfect simulations based on coupling from the past for finite state space models naturally extend to multivariate distributions with infinite or uncountable state spaces such as auto-gamma, auto-Poisson and autonegative binomial models, using Gibbs sampling in combination with sandwiching methods originally introduced for perfect simulation of point processes.

Remarks: Shows how to apply CFTP to sample from a class of Markov random fields, in which the individual variables (from a finite, countable, or continuous space) depend upon one another in a monotone or anti-monotone way. For the continuous distributions, the user specifies an ε, which controls not the bias (which is 0), but instead the numerical precision of the output. The application to the auto-gamma distribution, which includes the pump-reliability application above, appears to be faster than the approach of Murdoch and Green.

For the continuous distributions there is an even faster method, which also takes the numerical error ε to zero.

The aforementioned sandwiching methods are the ones introduced for antimonotone CFTP by Kendall and Häggström-Nelander.

Abstract: A survey is given of the ideas of perfect simulation involving Coupling From The Past (CFTP) as introduced by Propp and Wilson (1996), and its application to the perfect simulation of spatial point processes. A sketch is given of an extension to the perfect simulation of point processes defined over all R^2.

Sommaire: Voici un exposé des idées de la simulation parfaite au moyen de Coupling From The Past (CFTP) selon Propp et Wilson (1996), et son application à la simulation des processus ponctuels en espace. Une indication est fournie du moyen de conduire la simulation parfaite des processus ponctuels étendus à travers tout R^2.

Abstract: We develop an algorithm for simulating approximate random samples from the invariant measure of a Markov chain using backward coupling of embedded regeneration times. Related methods have been used effectively for finite chains and for stochastically monotone chains: here we propose a method of implementation which avoids these restrictions by using a ``cycle-length'' truncation. We show that the coupling times have good theoretical properties and describe benefits and difficulties of implementing the methods in practice.

Remarks: Gives a method for approximately sampling from the steady-state distribution of a Markov chain when the state of the chain takes on a certain particular value on a semi-regular basis. The Markov chain of interest is lifted to one that keeps track of 1) the original chain's state, and 2) the number of steps since the original chain's state took on that special value. The lifted chain is then truncated to force a return to the special state whenever the second coordinate gets too big. Using an independent set of coins for each value of time and each value of the second coordinate of the modified lifted chain, the authors show how to effectively test for coalescence. Includes discussion for how to choose the truncation parameter, though this not mechanized to the extent where the user could specify a desired maximum bias. Includes a case study on a two-server re-entrant queueing network.

Abstract: Recently Propp and Wilson have proposed an algorithm, called Coupling from the Past (CFTP), which allows not only an approximate but perfect (i.e. exact simulation of the stationary distribution of certain finite state space Markov chains. Perfect Sampling using CFTP has been successfully extended to the context of point processes, amongst other authors, by Häggström et al.. In Häggström et al. Gibbs Sampling is applied to a bivariate point process, the pentrable spheres mixture model. Fill also introduced an exact sampling algorithm, which, in contrast to CFTP, is unbiased for user impatience. Fill's algorithm is a form of rejection sampling and similar to CFTP requires sufficient monotonicity properties of the transition kernel used. We show how Fill's version of rejection sampling can be extended to produce perfect samples of the penetrable spheres mixture process and related models. Following Häggström et al. we use Gibbs sampling and make use of the partial order of the mixture model state space. Thus we construct an algorithm which protects agains bias caused by user impatience and which delivers samples not only of the mixture model but also of the attractive area-interaction and the continuum random-cluster process.

An expository paper describing a variety of very different situations for which coupling-from-the-past may be applied, and gives advice on recognizing additional applications. Includes some caveats for the practitioner.

Abstract: A general framework for exact simulation of Markov random fields using the Propp-Wilson coupling from the past approach is proposed. Our emphasis is on situations lacking the monotonicity properties that have been exploited in previous studies. A critical aspect is the convergence time of the algorithm; this we study both theoretically and experimentally. Our main theoretical result in this direction says, roughly, that if interactions are sufficiently weak, then the expected running time of a carefully designed implementation is O(N log N), where N is the number of interacting components of the system. Computer experiments are carried out for random q-colourings and for the Widom-Rowlinson lattice gas model.

Some of the techniques in this paper were independently developed by Huber.

Abstract: We study the existence of finitary codings (also called finitary homomorphisms or finitary factor maps) from a finite-valued i.i.d. process to certain random fields. For Markov random fields we show, using ideas of Marton and Shields, that the presence of a phase transition is an obstruction for the existence of the above coding: this yields a large class of Bernoulli shifts for which no such coding exists. Conversely, we show that for the stationary distribution of a monotone exponentially ergodic probabilistic cellular automaton such a coding does exist. The construction of the coding is partially inspired by the Propp-Wilson algorithm for exact simulation. In particular, combining our results with a theorem of Martinelli and Olivieri, we obtain the fact that for the plus state for the ferromagnetic Ising model on Z^d, d≥2, there is (not) such a coding when the interaction parameter is below (above) its critical value.

Abstract: We develop an algorithm for simulating ``perfect'' random samples from the invariant measure of a Harris recurrent Markov chain. The method uses backward coupling of embedded regeneration times, and works most effectively for finite chains, or on continuous spaces for stochastically monotone chains, where paths may be sandwiched between ``upper'' and ``lower'' processes. Examples show that more naive approaches to constructing such bounding processes may be considerably biased, but that the algorithm can be simplified in certain cases to make it easier to run. We give explicit analytic bounds on the backward coupling times in the stochastically monotone case. An application of the algorithm to bounded storage models is given, and we also develop a random ``upper'' process for analyzing unbounded storage models.

Remarks: For the given storage model application there are more effective algorithms.

Abstract: This reports gives a review of the new exact simulation algorithms using Markov chains. The first part covers the discrete case. We consider two different algorithms, Propp and Wilsons ``coupling from the past'' (CFTP) technique and Fills rejection sampler. The algorithms are tested on the Ising model, with and without an external field. The second part covers continuous state spaces. We present several algorithms developed by Murdoch and Green, all based on ``coupling from the past''. We discuss the applicability of these methods on a Bayesian analysis problem of surgical failure rates.

Abstract: Propp and Wilson (1996) described a protocol, called coupling from the past, for exact sampling from a target distribution using a coupled Markov chain Monte Carlo algorithm. In this paper we discuss the implementation of coupling from the past for samplers on a continuous state space; our ultimate objective is Bayesian MCMC with guaranteed convergence. We make some progress towards this objective, but our methods are still not automatic or generally applicable.

Per author's description: Describes several coupling techniques aimed at routine application in the context of Bayesian inference using random walk Metropolis: the ``bisection coupler'', calculation of automatic cell bounds and the adaptation of the Kendall (1996)/Haggstrom et al (1996) idea of bounded CFTP. Includes simulations of the posterior in two 2-parameter blood type datasets with a Dirichlet prior, a 3 dimensional Dirichlet distribution, and a N(0,1) distribution.

Abstract: Simulation plays an important rôle in stochastic geometry and related fields, because all but the simplest random set models tend to be intractable to analysis. Many simulation algorithms deliver (approximate) samples of such random set models, for example by simulating the equilibrium distribution of a Markov chain such as a spatial birth-and-death process. The samples usually fail to be exact because the algorithm simulates the Markov chain for a long but finite time, and thus convergence to equilibrium is only approximate. The seminal work by Propp and Wilson made an important contribution to simulation by proposing a coupling method, Coupling from the Past (CFTP), which delivers perfect, that is to say exact, simulations of Markov chains. In this paper we introduce this new idea of perfect simulation and illustrate it using two common models in stochastic geometry: the dead leaves model and a Boolean model conditioned to cover a finite set of points.

Here is an animated comparison (image size 128Kb) of imperfect and perfect simulations of the dead-leaves tessellation.

Abstract: ``Perfect sampling'' enables exact draws from the invariant measure of a Markov chain. We show that the independent Metropolis-Hastings chain has certain stochastic monotonicity properties that enable a perfect sampling algorithm to be implemented, at least when the candidate is overdispersed with respect to the target distribution. We prove that the algorithm has an optimal geometric convergence rate, and applications show that it may converge extremely rapidly.

Abstract: Iterated random functions are used to draw pictures or simulate large Ising models, among other applications. They offer a method for studying the steady state distribution of a Markov chain, and give useful bounds on rates of convergence in a variety of examples. The present paper surveys the field and presents some new examples. There is a simple unifying idea: the iterates of random Lipschitz functions converge if the functions are contracting on the average.

Abstract: Figures are presented to illustrate some examples of iterated random functions of the kind described in the article in this issue by Diaconis and Freedman.

Abstract: Fill's algorithm for perfect simulation for attractive finite state space models, unbiased for user impatience, is presented in terms of stochastic recursive sequences and extended in two ways. Repulsive discrete Markov random fields with two coding sets like the auto-Poisson distribution on a lattice with 4-neighbourhood can be treated as monotone systems if a particular partial ordering and quasimaximal and quasi-minimal states are used. Fill's algorithm then applies directly. Combining Fill's rejection sampling with sandwiching leads to a version of the algorithm, which works for general discrete conditionally specified repulsive models. Extensions to other types of models are briefly discussed.

Per author's description: This paper introduces the idea of a bounding chain for determining when complete coupling has occurred so that Coupling From the Past may be run on the chain to obtain exact samples. A bounding chain for the antiferromagnetic Potts model is given which is shown to couple completely in polynomial time given either a large number of colors or a sufficiently high temperature. The same analytical techniques also show the single-site update model of Propp and Wilson (ferromagnetic Ising) and Häggström and Nelander (antiferromagnetic Ising) run in polynomial time given high enough temperature.

Some of the techniques in this paper were independently developed by Häggström and Nelander.

Abstract: We study the beach model of Burton and Steif. The model is an example of a strongly irreducible subshift of finite type which, when the parameter of the model exceeds a critical value, has more than one measure of maximal entropy. We are interested in the critical value and how it depends on dimension. By way of simulations, we find that the critical value seems to be decreasing as a function of the dimension. We also present a conjecture for the whereabouts of the critical value in 2 dimensions. Our simulations are made with Markov chain Monte Carlo methods. For some parameter values and sizes of systems we are able to use the Propp-Wilson algorithm for exact simulation. For other combinations of parameter value and size we use a variant of the Swendsen-Wang algorithm.

Abstract: In this paper we study the notion of an efficient coupling of Markov processes. Informally, an efficient coupling is one which couples at the maximum possible exponential rate, as given by the spectral gap. This notion is of interest not only for its own sake, but also of growing importance arising from the very recent advent of methods of perfect simulation: it helps to establish the price of perfection' for such methods. In general one can always achieve efficient coupling if the coupling is allowed to cheat (if each component's behaviour is affected by future behaviour of the other component), but the situation is more interesting if the coupling is required to be co-adapted. We present an informal heuristic for the existence of an efficient coupling, and justify the heuristic by proving rigorous results and examples in the contexts of finite reversible Markov chains and of reflecting Brownian motion in planar domains.

Per author's description: This preprint uses the bounding chain approach to get exact samples from the Ising model using the Swendsen-Wang chain. We prove that over a range of parameters, the Swendsen-Wang chain completely couples in polynomial time, and give an algorithm for determining when complete coupling has occurred. This not only implies that the chain is rapidly mixing over this set of parameters, but also allows coupling from the past to be used to exactly sample from the chain.

Abstract: By developing and applying a broad framework for rejection sampling using auxiliary randomness, we provide an extension of the perfect sampling algorithm of Fill (1998) to general chains on quite general state spaces, and describe how use of bounding processes can ease computational burden. Along the way, we unearth a simple connection between the Coupling From The Past (CFTP) algorithm originated by Propp and Wilson (1996) and our extension of Fill's algorithm.

Remarks: The two versions of the four-authored paper supersede the 1998 preprint
Duncan J. Murdoch and Jeffrey S. Rosenthal. ``An extension of Fill's exact sampling algorithm to non-monotone chains.''

Abstract: In this paper, we combine two previous works, the first being by the first author and K. Nelander, and the second by J. van den Berg and the second author, to show (1) that one can carry out a Propp--Wilson exact simulation for all Markov random fields on Z^d satisfying a certain high noise assumption, and (2) that all such random fields are a finitary image of a finite state i.i.d. process. (2) is a strengthening of the previously known fact that such random fields are Bernoulli shifts.

Abstract: This paper studies the implementation of the coupling from the past (CFTP) method of Propp and Wilson (1996) in the set-up of two and three component mixtures with known components. We show that monotonicity structures can be exhibited in both cases, but that CFTP can still be costly for three component mixtures. We conclude with a simulation experiment exhibiting an almost perfect sampling scheme where we only consider a subset of the exhaustive set of starting values.

Abstract: In this article we demonstrate how to generate independent and identically distributed samples from the model space of the Bayes linear model with orthogonal predictors. We use the method of coupled Markov chains from the past as introduced by Propp and Wilson (1996). This procedure alleviates any concerns over convergence and sample mixing. We present a number of examples including a perfect simulation of Bayesian wavelet selection in a 1024 dimensional model space, a knot selection problem for spline smoothers and, a standard linear regression variable selection problem.

Abstract: Perfect sampling allows exact simulation of random variables from the stationary measure of a Markov chain. By exploiting monotonicity properties of the slice sampler we show that a perfect version of the algorithm can be easily implemented, at least when the target distribution is bounded. Various extensions, including perfect product slice samplers, and examples of applications are discussed.

Chapter 1, ``Markov chain Monte Carlo methods'' by Christian P. Robert and Sylvia Richardson, has a section 4 on ``Perfect sampling.''

Chapter 6, ``Convergence assessment in latent variable models: DNA applications'' by F. Muri, D. Chauveau, and D. Cellier, has a section 4 on ``Coupling from the past for the M1-M0 model,'' which includes a section 4.3 on ``Application to the bIL67 bacteriophage.''

Abstract: We explore and relate two notions of monotonicity, stochastic and realizable, for a system of probability measures on a common finite partially ordered set (poset) S when the measures are indexed by another poset A. We give counterexamples to show that the two notions are not always equivalent, but for various large classes of S we also present conditions on the poset A that are necessary and sufficient for equivalence. When A = S, the condition that the cover graph of S have no cycles is necessary and sufficient for equivalence. This case arises in comparing applicability of the perfect sampling algorithms of Propp and Wilson and the first author of the present paper.

Abstract: We consider the problem of randomly sampling from the set of indpendent sets of a graph, where the probability of selecting a particular independent set is proportional to λ raised to the size of the independent set. This distribution is the hard core gas model in statistical physics. If Δ is the maximum degree of the graph, Dyer and Greenhill gave a method for efficiently approximately sampling from this distribution when λ≤2/(Δ-2) by utilizing a rapidly mixing Markov chain. We show here how to use their chain to exactly sample from this distribution. This method is shown to run slightly faster than the method of Dyer and Greenhill, and as a corollary gives a better bound on the mixing time of their chain.

Abstract: We consider the problem of exactly sampling from the stationary distribution of a Markov chain, a problem with numerous Monte Carlo applications. The earliest method for accomplishing this was construction of a strong stationary times, a stopping time that when reached, left the chain in the stationary distribution. Unfortunately for many chains of interest, these stopping times were very difficult to compute. Here we show how an algorithm of Murdoch and Rosenthal leads to construction of strong stationary times for many chains of practical interest. In addition, we analyze the running time of their algorithm, and compare to the running time of another successful algorithm for exact sampling, coupling from the past. We show how to test whether these stopping times have been reached for several chains for distributions of interest, the hard core gas model, proper k colorings of a graph, and the continuous Widom-Rowlinson mixture model.

Abstract: Markov Chain Monte Carlo samplers have become popular tools for Bayesian computation. However, these techniques are computationally expensive. In order to speed them up, this paper presents portable, parallel and linear scalable computer implementations in the Bulk Synchronous Parallel model and in Java. Optimality in scalability and asymptotic optimality in speed is proved. It is shown how this parallel approach can be used for exact sampling using Propp and Wilson's algorithm. In 40 seconds it performs more than one million iterations using a 8192 X 8192 transition matrix of double precision floating point numbers on a SGI with 32 R10000 processors. For time-critical computational applications, an efficient use of the sample values generated via a repeated coupling from the past algorithm is made. Therefore many more samples per time are obtained, though these samples are not drawn from the true stationary distribution. How to develop and analyze a parallel solution in two rather different models of computation is explained. Reference to the complete code with documentation is provided in [20].

Abstract: This document describes a C implementation of a perfect algorithm for a Metropolis-Hastings simulation of a point process, based on

• a decomposition into types relating to different square sub-regions, and
• a dominating process which is composed of independent discrete-time M/M/1) queues, one for each square sub-region, each in equilibrium.

• this document gives a full listing of the program,
• this document does not discuss the underlying theory, which is covered in depth in Kendall & Møller (1999a).

A full Nuweb source for this program (in gzipped tarfile form, together with figures) is available at my [Kendall's] [homepage of available perfect simulation programs].

Abstract:
A system (P_a: a in A) of probability measures on a common finite set S indexed by another finite set A can be "realized" by a system (X_a: a in A) of S-valued random variables on some probability space so that X_a is distributed as P_a for each a in A. Assuming that A and S are each equipped with a partial order, we pose the following question: When can a given system (P_a: a in A) be realized by a system (X_a: a in A) with the monotonicity property that X_a ≤ X_b almost surely whenever a < b? When such a realization is possible, we call the system (P_a: a in A) realizably monotone. Such a system necessarily is stochastically monotone, that is, satisfies P_a ≤ P_b in stochastic ordering whenever a < b. We give counterexample(s) to show that stochastic monotonicity is not in general sufficient for realizable monotonicity.

Given particular partial orderings, however, these two notions of monotonicity can be equivalent. For various large classes of partially ordered sets (posets) S, we present various conditions on the poset A that are necessary and sufficient for equivalence. Furthermore, for a certain broad class of acyclic posets S, we develop inverse probability transforms from [0,1) into S and show how to utilize them to explicitly construct systems (X_a: a in A) with the monotonicity property from a single uniform random variable U.

If A = S and both are equipped with the same partial ordering, the condition that the poset is acyclic is necessary and sufficient for monotonicity equivalence. This case arises in comparing applicability of two perfect sampling algorithms, one via coupling from the past introduced by Propp and Wilson, and the other based on rejection sampling introduced by Fill.

Click here for the remainder of Machida's short hypertext presentation.

Abstract: Perfect simulation algorithms based on Propp and Wilson (1996) have so far been of limited use for sampling problems of interest in statistics. We specify a new family of perfect sampling algorithms obtained by combining MCMC tempering algorithms with dominated coupling from the past, and demonstrate that our algorithms will be useful for sample based inference. Perfect tempering algorithms are less efflcient than the MCMC algorithms on which they typically depend. However, samples returned by perfect tempering are distributed according to the intended distribution, so that these new sampling algorithms do not suffer from the convergence problems of MCMC. Perfect tempering is related to rejection sampling. When rejection sampling has been tried, but has proved impractical, it may be possible to convert the rejection algorithm into a perfect tempering algorithm, with a significant gain in algorithm efflciency.

Abstract: In Monte Carlo Markov chain algorithms, a random sample is generated by running a Markov chain ``for a long time''. This technique has applications in many areas, including statistical physics and approximation algorithms. Two questions about this procedure arise, first, how long does the chain need to be run before the sample obtained is close to being in the desired distribution, and secondly, how should chains be designed to make the running time as low as possible? Here we present a method for increasing the speed of Markov chains that we call the swap move. First applied by Broder to approximate the permanent, here we apply it to several models from statistical physics. In each case we are able to create improved Markov chains for the problem. More importantly, we show how the concept of bounding chains may be applied to the swap move, thus allowing the use of perfect sampling algorithms such as coupling from the past. These algorithms eliminate the need to know the mixing time of the Markov chain, making these new chains always faster to use.

Abstract: Generating perfect samples from distributions using Markov chains has a wide range of applications, from statistical physics to approximation algorithms. In perfect sampling algorithms, a sample is drawn exactly from the stationary distribution of a chain, as opposed to methods that run the chain ``for a long time'' and create samples drawn from a distribution that is close to the stationary distribution. One of the primary methods for creating perfect samples, the coupling from the past protocol of Propp and Wilson, suffers from the fact that the user must be willing to commit to running the algorithm in its entirety in order to obtain unbiased, perfect samples. By using another method, the acceptance rejection method of Fill, Murdoch, and Rosenthal (FMR), the user may abort the procedure in the middle of a run without introducing bias. In this paper, we give the first general analysis of the running time of FMR compared to the running time of of CFTP. Furthermore, we show that FMR can be used to generate a strong stationary stopping time of a Markov chain. We show how to use FMR to generate perfect sampling algorithms for two real world examples, the hard core gas model and the Widom-Rowlinson mixture model. These two examples illustrate the techniques needed to apply FMR to a wide range of discrete and infinite state space chains.

Remarks: Two references for the general form of Fill's algorithm are (1) ``Fill'' (his original article) and (2) ``Fill, Machida, Murdoch, and Rosenthal'' (which supersedes the preprint by Murdoch and Rosenthal).

Abstract: We give a new method for generating perfectly random samples from the stationary distribution of a Markov chain. The method is related to coupling from the past (CFTP), but only runs the Markov chain forwards in time, and never restarts it at previous times in the past. The method is also related to an idea known as PASTA (Poisson arrivals see time averages) in the operations research literature. Because the new algorithm can be run using a read-once stream of randomness, we call it read-once CFTP. The memory and time requirements of read-once CFTP are on par with the requirements of the usual form of CFTP, and for a variety of applications the requirements may be noticeably less. Some perfect sampling algorithms for point processes are based on an extension of CFTP known as coupling into and from the past; for completeness, we give a read-once version of coupling into and from the past, but it remains unpractical. For these point process applications, we give an alternative coupling method with which read-once CFTP may be efficiently used.

Abstract: A multistage implementation of Propp and Wilson's backward coupling scheme is proposed via cluster sampling, which can help reduce the time to coalescence. A random walk example is used to illustrate the multistage generalization and to compare it with Propp and Wilson's single-stage scheme. The use of backward cluster sampling is also proposed for stratified forward Markov chain Monte Carlo, taking advantage of the greater flexibility of the multistage framework. These proposals were inspired by a general principle in sample surveys --- multistage sampling is typically more effective than single stage sampling.

Abstract: We propose a perfect sampler for mixtures of distributions, in the spirit of Mira and Roberts (1999), building on Hobert, Robert and Titterington (1999). The method relies on a marginalisation akin to Rao-Blackwellisation which illustrates the Duality Principle of Diebolt and Robert (1994) and utilises an envelope argument which embeds the finite support distribution on the latent variables within a continuous support distribution, easier to simulate by slice sampling. We also provide a number of illustrations in the cases of normal and exponential mixtures which show that the technique does not suffer from severe slow-down when the number of observations or the number of components increases. We thus obtain a general iid sampling method for mixture posterior distributions and illustrate convincingly that perfect sampling can be achieved for realistic statistical models and not only for toy problems.

Remarks: The authors have written a corrigendum, in which they recharacterize their results as ``approximate exact sampling''.

Abstract: We discuss the interrelation between phase transitions in interacting lattice or continuum models, and the existence of infinite clusters in suitable random-graph models. In particular, we describe a random-geometric approach to the phase transition in the continuum Ising model of two species of particles with soft or hard interspecies repulsion. We comment also on the related area-interaction process and on perfect simulation.

Abstract: Propp and Wilson [10, 11] described a protocol called coupling from the past (CFTP) for exact sampling from the steady-state distribution of a Markov chain Monte Carlo (MCMC) process. In it a past time is identified from which the paths of coupled Markov chains starting at every possible state would have coalesced into a single value by the present time; this value is then a sample from the steady-state distribution.
Foss and Tweedie [3] pointed out that for CFTP to work, the underlying Markov chain must be uniformly ergodic. Unfortunately, most of the chains in common use in Bayesian inference are not, when the state space is unbounded. However, this does not mean that CFTP can't be used; in this paper we present three modifications.
The first is a simple change to the chain to induce uniform ergodicity. The second (more extensively discussed in [4]) is a modification to CFTP due to Kendall [6] that makes use of random bounds on particular realizations of the chain. Finally, the last method attempts to make use of Meng's [7] multistage coupler to address the problem.

Abstract: In this article we describe a new coupling technique which is useful in a variety of perfect sampling algorithms. A multishift coupler generates a random function f() so that for each real x, f(x)-x is governed by the same fixed probability distribution, such as a normal distribution. We develop the class of layered multishift couplers, which are simple and have several useful properties. For the standard normal distribution, for instance, the layered multishift coupler generates an f() which (surprisingly) maps an interval of length l to fewer than 2+l/2.35 points --- useful in applications which perform computations on each such image point. The layered multishift coupler improves and simplifies algorithms for generating perfectly random samples from several distributions, including and autogamma distribution, posterior distributions for Bayesian inference, and the steady state distribution for certain storage systems. We also use the layered multishift coupler to develop a Markov-chain based perfect sampling algorithm for the autonormal distribution.
At the request of the organizers, we begin by giving a primer on CFTP (coupling from the past); CFTP and Fill's algorithm are the two predominant techniques for generating perfectly random samples using coupled Markov chains.

Abstract: We discuss two simple algorithms for generating exact samples from the equilibrium distribution of a Markov chain. These algorithms are based on a single run of the Markov chain in an ordinary way. One can pick up certain samples from the run as samples from the equilibrium distribution. This is done by introducing auxiliary variables as the indicators during the run.

Alessandra Guglielmi,

Abstract: In this paper we present an important application of perfect simulation using Markov chains involving a continuous and unbounded state space. We demonstrate how to sample exactly a linear functional of a random probability measure chosen from a Dirichlet process, which has application in Bayesian nonparametric problems. We use ideas of coupling from the past and in particular point out that if interest is in the output from a computing machine then one need go no further than the work of Propp & Wilson (1996), who considered perfect simulation involving finite state spaces.

Abstract: Markov Chain Monte Carlo (MCMC) methods are used to sample from complicated multivariate distributions with normalizing constants that may not be computable and from which direct sampling is not feasible. A fundamental problem is to determine convergence of the chains. Propp & Wilson (1996) devised a Markov chain algorithm called Coupling From The Past (CFTP) that solves this problem, as it produces exact samples from the target distribution and determines automatically how long it needs to run. Exact sampling by CFTP and other methods is currently a thriving research topic. This paper gives a review of some of these ideas, with emphasis on the CFTP algorithm. The concepts of coupling and monotone CFTP are introduced, and results on the running time of the algorithm presented. The interruptible method of Fill (1998) and the method of Murdoch & Green (1998) for exact sampling for continuous distributions are presented. Novel simulation experiments are reported for exact sampling from the Ising model in the setting of Bayesian image restoration, and the results are compared to standard MCMC. The results show that CFTP works at least as well as standard MCMC, with convergence monitored by the method of Raftery & Lewis (1992, 1996).

Abstract: An introduction to the Propp-Wilson method of coupling-from-the-past for the Ising model is presented. It enables one to obtain exact samples from the equilibrium spin distribution for ferromagnetic interactions. Both uniform and random quenched magnetic fields are included. The time to couple from the past and its standard deviation are shown as functions of system size, temperature, and the field strength. The time should be an estimate of the ergodic time for the Ising system.

Abstract: Markov chain Monte Carlo has long become a very useful, established tool in statistical physics and spatial statistics. Recent years have seen the development of a new, exciting generation of Markov chain Monte Carlo methods: perfect simulation algorithms. In contrast to conventional Markov chain Monte Carlo perfect simulation produces samples which are guaranteed to have the exact equilibrium distribution. In the following we provide an example-based introduction into perfect simulation focussed on the method called Coupling from the Past.

Michael Harvey.

Abstract: A common method of inference for belief networks is Gibbs sampling, in which a Markov chain converging to the desired distribution is simulated. In practice, however, the distribution obtained with Gibbs sampling differs from the desired distribution by an unknown error, since the simulation time is finite. Coupling from the past selects states from exactly the desired distribution by starting chains in every state at a time far enough back in the past that they reach the same state at time t= 0. To track every chain is an intractable procedure for large state spaces. The method proposed in this thesis uses a summary chain to approximate the set of chains. Transitions of the summary chain are efflcient for noisy-or belief networks, provided that sibling variables of the network are not directly connected, but often require more simulation time steps than would be needed if chains were tracked exactly. Testing shows that the method is a potential alternative to ordinary Gibbs sampling, especially for networks that have poor Gibbs sampling convergence, and when the user has a low error tolerance.

Abstract: The aim of this project is to study the Propp & Wilson method (Propp & Wilson, 1996) for exact simulation via Markov chain Monte Carlo.
The first part of the project involves investigating the computation time required for Propp & Wilson's algorithm in different applications. The objective is to find the optimal division of effort between `pre-sampling' which ensures the Markov chain is sampling from its ergodic distribution and the subsequent `production runs' which yield internally correlated realisations from which to draw inferences about the target distribution. In our application, it is found that the most accurate estimates are obtained by using one long run of correlated samples instead of several shorter runs, although there are other advantages of using several runs.
In the second part of the project different sampling methods based on the Propp & Wilson algorithm are studied in situations where exact sampling is not feasible. The objective of this part of the project is to develop methods that can be used as diagnostics for exact sampling in these cases. We consider a number of distributions and according to the situation, different methods are tried out. Furthermore, a test is developed to assess the methods.

Abstract: We present a perfect simulation algorithm for measures that are absolutely continuous with respect to some Poisson process and can be obtained as invariant measures of birth-and-death processes. Examples include area- and perimeter-interacting point processes (with stochastic grains), invariant measures of loss networks, and the Ising contour and random cluster models. The algorithm does not involve couplings of the process with different initial conditions and it is not tied up to monotonicity requirements. Furthermore, it directly provides perfect samples of finite windows of the infinite-volume measure, subjected to time and space ``user-impatience bias''. The algorithm is based on a two-step procedure: (i) a perfect-simulation scheme for a (finite and random) relevant portion of a (space-time) marked Poisson processes (free birth-and-death process, free loss networks), and (ii) a ``cleaning'' algorithm that trims out this process according to the interaction rules of the target process. The first step involves the perfect generation of ``ancestors'' of a given object, that is of predecessors that may have an influence on the birth-rate under the target process. The second step, and hence the whole procedure, is feasible if these ``ancestors'' form a finite set with probability one. We present a sufficiency criteria for this condition, based on the absence of infinite clusters for an associated (backwards) oriented percolation model.

Bas Straatman. Exact sampling and applications to a mite dispersal model, 1998.

This thesis does not itself come with an abstract, but the abstract for a talk given by Straatman on the topic follows.
Abstract: I have studied a Markov chain which describes the dispersal of mites on cassava fields in West Africa. Instead of obtaining a sample of this model with approximately the stationary distribution by Monte Carlo simulation, it is possible to obtain a result which is exactly distributed according to the stationary distribution. One way to do this is coupling from the past. After a short introduction of this procedure I will explain the changes I have made to the original model in order to be able to use coupling from the past and show some simulations which give exact samples.

Abstract: The paper is concerned with the Bayesian analysis of point processes which are observed with noise. It is shown how to produce exact samples from the posterior distribution of the unobserved true point process given a noisy observation. The algorithm is a perfect simulation method which applies dominated coupling from the past to a spatial birth-and-death process. Dominated coupling from the past is made amenable by augmenting the state space of the target chain. We discuss how to optimize this perfect simulation algorithm and how to use it in a statistical inference problem of pratical importance. We further describe the merits and the limitations of the method.

Abstract: The main themes of this thesis are spatial statistics and simulation algorithms. The thesis is split into five papers that may be read independently. All five papers deal with spatial models. Lund & Rudemo (1999), Lund et al. (1999), and Lund & Thönnes (1999b) deal with the same new model for point processes observed with noise, and Lund et al. (1999), Lund & Thönnes (1999b), and Lund & Thönnes (1999a) has a simulation aspect.
Lund & Rudemo (1999), Lund et al. (1999), and Lund & Thönnes (1999b) develop and analyse a new model for point processes observed with noise. Usually the analysis of spatial point patterns assume that the observed points (the true points) are a realization from a specific model. In contrast our approach is to assume the observed pattern generated by thinning and displacement of the true points, and allow for contamination by points not belonging to the true pattern.
Lund & Rudemo (1999) develop the model for point processes observed with noise. The likelihood function for an observation of a noise corrupted point pattern given the true positions is derived. As data for our analysis is indeed a realization of the underlying true process and its associated noise corrupted point pattern we need not consider a model for the underlying process. The parameters in the model describe how many of the true points are lost, how large the displacements are, and the number of contaminating surplus points. For estimation of the parameters in the noise model a deterministic, iterative, and approximative maximum likelihood estimation algorithm is developed. The likelihood function is a sum of an excessive large number of terms, and the algorithm works by finding large dominating terms. Alternative estimation methods are discussed.
Lund et al. (1999) analyse the model developed in Lund & Rudemo (1999) with respect to the now unobserved true points. We assume a noisy observation of a true point pattern and knowledge of the parameters in the model. A Bayesian point of view is now adopted and we specify a prior distribution for the underlying true process. Given the model, the prior distribution, and the noisy observation, we get the posterior distribution of the true points. This posterior distribution is investigated by samples from the distribution. These samples are obtained from a Markov chain Monte Carlo (MCMC) algorithm extending the Metropolis-Hastings sampler for point processes. A thorough discussion is provided on the choice of prior distribution and how to present the samples from the MCMC runs. The MCMC samples are used to estimate for example the K-function for the unobserved true point pattern. These estimates are clearly better than estimates based on the observed points alone.
The use of the MCMC algorithm in Lund et al. (1999) relies on the fact that a Markov chain run for a long time approaches its stationary distribution. Lund & Thönnes (1999b) uses a recent technique called Coupling From The Past (CFTP) to deliver a sample drawn from the exact posterior distribution of the unobserved true points described in Lund et al. (1999), a so-called perfect simulation. This perfect simulation algorithm is based on spatial birth-and-death processes for simulation of point processes. In order to apply CFTP in our problem the simulation is carried out on an augmented state space. The algorithm turns out to be too slow in practice and thus demonstrates possible current limits of CFTP.
Lund & Thönnes (1999a) describes a new perfect simulation algorithm for general locally stable point processes. The algorithm is based on CFTP for Metropolis-Hastings simulation of point processes and it is simpler than the previous known perfect algorithm based on Metropolis-Hastings simulation for this class of models. The present state of the algorithm is that it is far too slow to be useful in practice, and it might have some theoretical flaws. These problems are discussed in the introductory part of the thesis.
Lund (1998) develops a model for survival times of trees that take the spatial positions of the trees into account. At a finite number of timepoints it is observed whether a tree is alive or not, and thus we have interval censoring of the even aged trees. The model is a discrete time version of Cox's proportional hazards model. Positions of trees are considered as fixed, and they are used to compute competition indices that enter the model as covariates. It is shown that small trees have a higher risk of dying than large tress and the area of the experiment is inhomogeneous. In addition, Hegyi's competition index based on basal area is a significant covariate.

Abstract: This paper shows how coupling methodology can be used to give precise, a priori bounds on the convergence time of Markov chain Monte Carlo algorithms for which a partial order exists on the state space which is preserved by the Markov chain transitions. This methodology is applied to give a bound on the convergence time of the random scan Gibbs sampler used in the Bayesian restoration of an image of N pixels. For our algorithm in which only one pixel is updated at each iteration, the bound is a constant times N². The proportionality constant is given and is easy to calculate. These bounds also give an indication of the running time of coupling from the past algorithms.

Abstract: Markov chain Monte Carlo algorithms, such as the Gibbs sampler and Metropolis-Hastings algorithm, are widely used in statistics, computer science, chemistry and physics for exploring complicated probability distributions. A critical issue for users of these algorithms is the determination of the number of iterations required so that the result will be approximately a sample from the distribution of interest.
In this thesis, we give precise bounds on the convergence time of the Gibbs sampler used in the Bayesian restoration of a degraded image. We consider convergence as measured by both the usual choice of metric, total variation distance, and the Wasserstein metric. In both cases we exploit the coupling characterisation of the metric to get our results. Our results can also be applied to the coupling-from-the-past algorithm of Propp and Wilson (1996) to get bounds on its running time.
The application of our theoretical results requires the computation of parameters of the algorithm. These computations may be prohibitively difflcult in many situations. We discuss how our results can be applied in these situations through the use of auxiliary simulation to estimate these parameters.
We also give a summary of probability metrics and the relationships between them, including several new relationships.

Abstract: We consider using the ancestral selection graph to simulate samples from genetic models with selection. Currently the use of the ancestral selection graph to simulate such samples is limited. This is because the computational requirement for simulating such samples increases exponentially with the selection rate, and also due to the need to be able to simulate a sample of size 1 from the population at equilibrium. For the only case where the distribution of a sample of size one is known, that of parent independent mutations, more efflcient simulation algorithms exist. We will show that by applying the idea of coupling from the past to the ancestral selection graph, samples can be simulated from a general K-allele model without knowledge of the distribution of a sample of size 1. Further, the computation involved in generating such samples appears to be less than that of simulating the ancestral selection graph until its ultimate ancestor. In particular, in the case of genic selection with parent independent mutations, the computational requirement increases only quadratically with the selection rate. The algorithm is then used to simulate samples at microsatellite loci, and to consider the effect of selection on linked neutral sites.

From the preface: This doctoral thesis is concerned with certain aspects of spatial statistics, stochastic geometry, and Markov chain Monte Carlo methods. It is based on a monograph [L] and twenty selected papers [A--K, M--V] produced over about the last decade; see the following two pages. The papers [A, G, H, I] and [95, 140] constituted my Ph.D. thesis from 1988 entitled Stochastic Geometry and Markov Models; [A, H, I] in revised form are included in the present thesis.
The thesis consists of three parts: (i) statistical models for lattice data, spatial (marked) point patterns, and spatial birth-and-death processes, (ii) Markov chain Monte Carlo methods and statistical inference for spatial models, and (iii) random tessellations. Parts (i) and (ii) are closely related and the focus is on recent theoretical and applied statistical aspects. Part (iii) is more within the traditional framework of stochastic geometry, though new results will be discussed as well.

Remark: Section 3.2 deals with perfect simulation.

Abstract: Many generic prior models have been widely used in computer vision ranging from image and surface reconstruction to motion analysis, and these models presume that surfaces of objects be smooth, and adjacent pixels in images have similar intensity values. However, there is little rigorous theory to guide the construction and selection of prior models for a given application. Furthermore, images are often observed at arbitrary scales, but none of the existing prior models are scale-invariant. Motivated by these problems, this article chooses general natural images as a domain of application, and proposes a theory for learning prior models from a set of observed natural images. Our theory is based on a maximum entropy principle, and the learned prior models are of Gibbs distributions. A novel information criterion is proposed for model selection by minimizing a Kullback-Leibler information distance. We also investigate scale invariance in the statistics of natural images and study a prior model which has scale invariant property. In this paper, in contrast with all existing prior models, negative potentials in Gibbs distribution are first reported. The learned prior models are verified in two ways. Firstly images are sampled from the prior distributions to demonstrate what typical images they stand for. Secondly they are compared with existing prior models in experiments of image restoration.

Remarks: This paper is about image processing rather than perfect sampling per se, but the end of section 3 includes discussion of their use of the ``Propp-Wilson criterion'' for deciding how long to run their Markov chains.

Abstract: Propp and Wilson's method of coupling from the past allows one to efflciently generate exact samples from attractive statistical distributions (e.g., the ferromagnetic Ising model). This method may be generalized to non-attractive distributions by the use of summary states, as first described by Huber. Using this method, we present exact samples from a frustrated antiferromagnetic triangular Ising model and the antiferromagnetic q= 3 Potts model. We discuss the advantages and limitations of the method of summary states for practical sampling, paying particular attention to the slowing down of the algorithm at low temperature. In particular, we show that such a slowing down can occur in the absence of a physical phase transition.

Abstract: The weak limit of the normalized number of comparisons needed by the Quicksort algorithm to sort n randomly permuted items is known to be determined implicitly by a distributional fixed-point equation. We give an algorithm for perfect random variate generation from this distribution.

Abstract: In 1996, Propp and Wilson introduced Coupling from the Past (CFTP), an algorithm for generating a sample from the exact stationary distribution of a Markov chain. In 1998, Fill proposed another so-called perfect sampling algorithm. These algorithms have enormous potential in Markov Chain Monte Carlo (MCMC) problems because they eliminate the need to monitor convergence and mixing of the chain. This article provides a brief introduction to the algorithms, with an emphasis on understanding rather than technical detail.

Contents: These lecture notes (68 pages) give an elementary introduction to Markov chains, and applications to algorithms like MCMC and simulated annealing. Chapters are entitled:

0. Preface.
1. Basics of probability theory.
2. Markov chains.
3. Computer simulation of Markov chains.
4. Irreducible and aperiodic Markov chains.
5. Stationary distributions.
6. Reversible Markov chains.
7. Markov chain Monte Carlo.
8. The Propp-Wilson algorithm.
9. Simulated annealing.
10. Further reading.

Abstract: In a missing data problem we observe the result of a (known) many-to-one mapping of an unobservable `complete' dataset. The aim is to estimate some parameter of the distribution of the complete data. In this situation, the stochastic version of the EM algorithm is sometimes a viable option. It is an iterative algorithm that produces an ergodic Markov chain on the parameter space. The stochastic EM (StEM) estimator is then a sample from the equilibrium distribution of this chain. Recently, a method called `coupling from the past' was invented to generate a Markov chain in equilibrium. We investigate when this method can be used for a StEM chain and give examples where this is indeed possible.

Abstract: We study an inventory model for perishable products with a critical-number ordering policy under the assumption that demand for the product forms an i.i.d. sequence, so that the state of the system forms a Markov chain. Explicit calculation of the stationary distribution has proved impractical in cases where items have reasonably long lifetimes and for systems with large ``under-up-to'' levels. Using the recently-developed coupling-from-the-past method, we introduce a technique to estimate the stationary distribution of the Markov chain via ``perfect simulation.'' The Markov chain that results from the use of a critical-number policy is particularly amenable to these simulation techniques, despite not being ordered in its initial state, since the recursive equations satisfied by the Markov chain enable us to identify specific demand patterns where the backward coupling occurs.

Abstract: We provide a review and a unified exposition of the Propp-Wilson algorithm and various other algorithms for making perfect simulations with a view to applications in stochastic geometry. Most examples of applications are for spatial point processes.

Abstract: We present a perfect simulation algorithm for stationary processes indexed by Z, with summable memory decay. Depending on the decay, we construct the process on finite or semiinfinite intervals, explicitly from an i.i.d. uniform sequence. Even though the process has infinite memory, its value at time 0 depends only on a finite, but random, number of these uniform variables. The algorithm is based on a recent regenerative construction of these measures by Ferrari, Maass, Martinez and Ney. As applications, we discuss the perfect simulation of binary autoregressions and Markov chains on the unit interval.

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 distributions. 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, an RR-based algorithm creates samples drawn exactly from the desired distribution. Other perfect sampling methods such as coupling from the past use existing Markov chains, but RR does not use the traditionalMarkov chain at all. While by no means universally useful, RR does apply to a wide variety of problems. In restricted instances of certain problems, it gives the first expected linear time algorithms for generating samples. Here we apply RR to self-organizing lists, the Ising model, random independent sets, random colorings, and the random cluster model.

Abstract: A system (P_a: a in A) of probability measures on a common state space S indexed by another index set A can be ``realized'' by a system (X<sub>a</sub>: a in A) of S-valued random variables on some probability space in such a way that each X<sub>a</sub> is distributed as P<sub>a</sub>. Assuming that A and S are both partially ordered, we may ask when the system (P<sub>a</sub>: a in A) can be realized by a system (X<sub>a</sub>: a in A) with the monotonicity property that X<sub>a</sub> <= X<sub>b</sub> almost surely whenever a <= b. When such a realization is possible, we call the system (P<sub>a</sub>: a in A) ``realizably monotone.'' Such a system necessarily is stochastically monotone, that is, satisfies P_a <= P_b in stochastic ordering whenever a <= b. In general, stochastic monotonicity is not sufficient for realizable monotonicity. However, for some particular choices of partial orderings in a finite state setting, these two notions of monotonicity are equivalent. We develop an inverse probability transform for a certain broad class of posets S, and use it to explicitly construct a system (X_a: a in A) realizing the monotonicity of a stochastically monotone system when the two notions of monotonicity are equivalent.

Abstract: We study a Bayesian cluster model for spatial point processes in which observations are assumed to cluster around a finite collection of underlying landmarks. Perfect sampling from the posterior distribution of landmarks is investigated. In the case of Neyman-Scott cluster models, perfect sampling from the posterior is shown to be computationally feasible via a coupling-from-the-past type algorithm of Kendall and Møller. An application to data on leukemia incidence in upstate New York is developed.

Abstract: Perhaps the best known example of a random set is the Boolean model. It is the union of `grains' such as discs, squares or triangles which are placed at the points of a Poisson point process. The Poisson points are called the `germs'. We are interested in estimating the intensity, say lambda, of the Poisson process from a sample of a Boolean model of discs (the bombing model). A natural estimate is the number of germs in the observation region divided by the area of that region. Unfortunately, we do not observe the presence of a given germ when its associated disc is completely covered by other discs. On the other hand, we observe the exact location of a germ when we observe any part of its associated disc's boundary. We demonstrate how to apply Coupling From The Past to sample from the conditional distribution, given the data, of the unobserved germs. Such samples allow us to approximate the maximum likelihood estimator of the intensity. We discuss and compare two methods to do so. The first method is based on a Monte Carlo approximation of the likelihood function. The second is a stochastic version of the EM algorithm.

Abstract: Let Φ be an irreducible, aperiodic, Harris recurrent Markov chain with invariant probability measure π. We show that if a minorization condition can be established for Φ, then π can be represented as an infinite mixture from which it may be possible to sample. Making exact draws from this mixture (and hence from π requires the ability to simulate two different random variables, T^* and N_t. When the small set in the minorization condition is the entire state space (and hence Φ is uniformly ergodic), simulating these random variables is straightforward and the resulting algorithm turns out to be equivalent to Murdoch and Green's (1998) multigamma coupler. Thus, we are able to achieve perfect sampling in the uniformly ergodic case without any appeal to coupling or backward simulation. When the small set is not the state space, simulating T^* is more problematic. Fortunately, T^* is univariate and has support N. We construct an estimate of the mass function of T^* and an asymptotic bound on the error of this estimate. These results are used to address rigorously the issue of burn-in. Specifically, we form an approximation of π whose error can be controlled and which can be used as an initial distribution for Φ. We illustrate this with a realistic example. Finally, we provide a simple Markov chain Monte Carlo (MCMC) algorithm whose stationary distribution is that of T^*. Finding a perfect sampler based on our MCMC algorithm for the univariate, discrete T^* is tantamount to the ability to sample exactly from π.

Abstract: When simulating a physical system with discrete sates, one often would like to generate a sample from the stationary distribution of a Markov chain. This report focuses on three sampling methodologies which do not rely on explicitly computing the stationary distribution. Two of these lead to algorithms which can generate an exact sample in finite time. The third yields a sample whose distribution approximates, but is arbitrary close to, the stationary distribution from which one desires a sample. The approximate and one of the exact methodologies are illustrated with examples from statistical mechanics.

Abstract: For Markov chains that can be generated by iteration of i.i.d. random maps from the state space X into itself (this holds if X is Polish) it is shown that the Doeblin minorization condition is necessary and sufflcient for the method by Propp and Wilson for ``perfect'' sampling from the stationary distribution π to be successful.
Using only the transition probability P we produce in a geometrically distributed random number of steps N a ``perfect'' sample from π of size N!.

Joakim Linde, Cristopher Moore, Mats G. Nordahl. An n-dimensional generalization of the rhombus tiling, 2001. Preprint.

Abstract: Several classic tilings, including rhombuses and dominoes, possess height functions which allow us to 1) prove ergodicity and polynomial mixing times for Markov chains based on local moves, 2) use coupling from the past to sample perfectly random tilings, 3) map the statistics of random tilings at large scales to physical models of random surfaces, and and 4) are related to the ``arctic circle'' phenomenon. However, few examples are known for which this approach works in three or more dimensions. Here we show that the rhombus tiling can be generalized to n-dimensional tiles for any n≥3. For each n, we show that a certain local move is ergodic, and conjecture that it has a mixing time of O(Ln+2 log L) on regions of size L. For n=3, the tiles are rhombohedra, and the local move consists of switching between two tilings of a rhombic dodecahedron. We use coupling from the past to sample random tilings of a large rhombic dodecahedron, and show that arctic regions exist in which the tiling is frozen into a fixed state. However, unlike the two-dimensional tiling in which the arctic region is an inscribed circle, here it seems to be octahedral. In addition, height fluctuations between the boundary of the region and the center appear to be constant rather than growing logarithmically. We conjecture that this is because the physics of the model is in a ``smooth'' phase where it is rigid at large scales, rather than a ``rough'' phase in which it is elastic.

---

Kasper K. Berthelsen and

Abstract: Spatial birth-and-death processes, spatial birth-and-catastrophe processes, and more general types of spatial jump processes are studied in detail. Particularly, varied kind of coupling constructions are considered, leading to some known and some new perfect simulation procedures for different types of spatial jump processes in equilibrium. The considered equilibrium distributions include many classical Gibbs point process models and a new class of models for spatial point processes introduced in the text.

Abstract: This primer provides a self-contained exposition of the case where spatial birth-and-death processes are used for perfect simulation of locally stable point processes. Particularly, a simple dominating coupling from the past (CFTP) algorithm and the CFTP algorithms introduced in Kendall (1998), Kendall & Møller (2000), and Fernández, Ferrari & Garcia (2000) are studied. Some empirical results for the algorithms are discussed.

Julian Besag. Likelihood analysis of binary data in space and time.

Keywords: Autologistic; Conditional probability; Coupling from the past; Lattice data; Markov chain Monte Carlo; Markov random fields; Maximum likelihood; Maximum pseudolikelihood; Perfect simulation; Space and time; Spread of disease

Abstract: We show how to combine Fourier analysis with coupling arguments to bound the mixing times of a variety of Markov chains. The mixing time is the number of steps a Markov chain takes to approach its equilibrium distribution. One application is to a class of Markov chains introduced by Luby, Randall, and Sinclair to generate random tilings of regions by lozenges. For an L X L region we bound the mixing time by O(L⁴ log L), which improves on the previous bound of O(L⁷), and we show the new bound to be essentially tight. In another application we resolve a few questions raised by Diaconis and Saloff-Coste, by lower bounding the mixing time of various card-shuffling Markov chains. Our lower bounds are within a constant factor of their upper bounds. When we use our methods to modify a path-coupling analysis of Bubley and Dyer, we obtain an O(n³ log n) upper bound on the mixing time of the Karzanov-Khachiyan Markov chain for linear extensions.

Remarks: Among other things this article analyses the running time of CFTP when applied to lozenge tilings, and contains experiments pertinent to Fill's algorithm.

Kasper K. Berthelsen and

Abstract: The advantages and limitations of using perfect simulation for simulation-based inference for pairwise interaction point processes are discussed. Various aspects of likelihood inference for the Strauss process with unknown range of interaction are studied. A large part of the paper concerns non-parametric Bayesian inference for the interaction function. Markov chain Monte Carlo methods, particularly path sampling, play an important role. Several empirical results and various datasets are considered.

Abstract: Perfect sampling using the coupling from the past (CFTP) algorithm was introduced by Propp and Wilson in 1996. In much the way rejection sampling allows one to convert samplers from one distribution into samplers from another, CFTP allows one to convert Markov chain Monte Carlo algorithms from approximate samplers of the steady-state distribution into perfect ones. Since 1996 CFTP has been applied to many different Markov chains. However, its use in routine Bayesian computation is still in the early stages of development. This paper provides a couple of building blocks for its potentially routine application in Bayesian mixture priors, including a t mixture coupler, and demonstrates the types of difficulties that currently prevent CFTP from being applied routinely in Bayesian computation.

Abstract: This paper reports some initial investigations of the use of antithetic variates in perfect sampling. A simple random walk example is presented to il-lustrate the key ingredients of antithetic coupling for perfect sampling as well as its potential benefit. A key step in implementing antithetic coupling is to generate k≥2 random variates that are negatively associated, a stronger condition than negative correlation as it requires that the variates remain non-positively corre-lated after any (component-wise) monotone transformations have been applied. For k=2, this step is typically trivial (e.g., by taking U and 1-U where U~U(0,1)) and it constitutes much of the common use of antithetic variates in Monte Carlo simulation. Our emphasis is on k>2 because we have observed some general gains in going beyond the commonly used pair of antithetic variates. We discuss several ways of generating negatively associated random variates for arbitrary k, and our comparison generally favors Iterative Latin Hypercube Sampling.

Abstract: This work presents a review of some of the schemes used to perfect sample from spatial processes. As examples, the area-interaction point process, Strauss process, penetrable sphere model, Peierls contours of the Ising model and continuous loss networks are studied under Coupling from The Past Algorithm (CFTP), Acceptance and Rejection Algorithm (ARA) and Backward-Forward Algorithm(BFA).

Sung-woo Cho and

Abstract: Analysis of machine scheduling problem can get very complicated even for simple scheduling policies and simple arrival processes. The problem becomes even harder if the scheduler and the arrival process are complicated, or worse still, given to us as a black box. In such cases it is useful to obtain a typical state of the system which can then be used to deduce information about the performance of the system or to tune the parameters for either the scheduling rule or the arrival process. We consider two general scheduling problems and present an algorithm for extracting an exact sample from the stationary distribution of the system when the system forms an ergodic Markov chain. We assume no knowledge of the internals of the arrival process or the scheduler. Our algorithm assumes that the scheduler has a natural monotonic property, and that the job service times are geometric/exponential. We use the Coupling From The Past paradigm due to Propp and Wilson to obtain our result. In order to apply their general framework to our problems, we perform a careful coupling of the different states of the Markov chain.

Abstract: We demonstrate how to apply Coupling from the Past, a simulation technique for exact sampling, to Markov chains based on TCP variants. This approach provides a new, statistically sound paradigm for network simulations: instead of simulating a protocol over long times, or explicitly finding the stationary distribution of a Markov chain, use Coupling from the Past to quickly obtain samples from the stationary distribution. Coupling from the Past is most efflcient when the underlying state space satisfies a partial order and certain monotonicity conditions. To efficiently apply this general paradigm to TCP, we demonstrate that the states of a simple TCP model possess a monotonic partial order; this order appears interesting in its own right. Preliminary simulation results indicate that this approach is quite efflcient, and produces results which are similar to those obtained by simulating a TCP-Tahoe connection.

Abstract: We establish, for various scenarios, whether or not interruptible exact stationary sampling is possible when a finite-state Markov chain can only be viewed passively. In particular, we prove that such sampling is not possible using a single copy of the chain. Such sampling is possible when enough copies of the chain are available, and we provide an algorithm that terminates with probability one.

Abstract: In a previous paper by the second author, two Markov chain Monte Carlo perfect sampling algorithms - one called coupling from the past (CFTP) and the other (FMMR) based on rejection sampling - are compared using as a case study the move-to-front (MTF) self-organizing list chain. Here we revisit that case study and, in particular, exploit the dependence of FMMR on the user-chosen initial state. We give a stochastic monotonicity result for the running time of FMMR applied to MTF and thus identify the initial state that gives the stochastically smallest running time; by contrast, the initial state used in the previous study gives the stochastically largest running time. By changing from worst choice to best choice of initial state we achieve remarkable speedup of FMMR for MTF; for example, we reduce the running time (as measured in Markov chain steps) from exponential in the length n of the list nearly down to n when the items in the list are requested according to a geometric distribution. For this same example, the running time for CFTP grows exponentially in n.

Abstract: We provide an exact simulation algorithm that produces variables from truncated Gaussian distributions on (R₊)^p via a perfect sampling scheme, based on stochastic ordering and slice sampling, since accept-reject algorithms like those of Geweke (1991) or Robert (1994) are difficult to extend to higher dimensions.

A number of people have written graduate theses in which a significant component was on perfect sampling with Markov chains. In chronological order these are:

David Bruce Wilson. Exact Sampling with Markov Chains. Ph.D. thesis, MIT Mathematics Department, May 28, 1996.
Advisor: James G. Propp.

Tine Møller Sørensen. A study of Propp & Wilson's method for exact Markov chain Monte Carlo sampling, 1997. Master's thesis in computational statistics, University of Bath.
Advisor: Christopher Jennison.

Morten Fismen. Exact simulation using Markov chains. Technical Report 6/98, Institutt for Matematiske Fag, 1998. Diploma-thesis.
Advisor: Håvard Rue

Karin Nelander. Contributions to Percolation Theory and Exact Sampling. Ph.D. thesis, Deperartment of Mathematics, Göteborg, March 29, 1998.
Advisor: Olle Häggström

Jem Noelle Corcoran. Perfect Sampling in MCMC Algorithms. Ph.D. thesis, Department of Statistics at Colorado State University, May 1998.
Advisor: Richard L. Tweedie

Bas Straatman. Exact sampling and applications to a mite dispersal model. Master's thesis, Utrecht, August 10, 1998.

Elke Thönnes. Perfect and Imperfect Simulations in Stochastic Geometry. Ph.D. thesis, University of Warwick, October 1998.
Advisor: Wilfrid S. Kendall

Motoya Machida. Stochastic Monotonicity and Realizable Monotonicity. PhD thesis, The Johns Hopkins University, Department of Mathematical Sciences, 1999.
Advisor: James A. Fill

Mark Lawrence Huber. Perfect Sampling Using Bounding Chains. Ph.D. thesis, Cornell University, May 1999.
Advisor: David B. Shmoys

Michael Harvey. Monte Carlo Inference for Belief Networks Using Coupling From the Past. Master's thesis, department of computer science, University of Toronto, 1999.
Advisor: Radford M. Neal

Jens Lund. Statistical inference and perfect simulation for point processes observed with noise. PhD thesis, The Royal Veterinary and Agricultural University, Copenhagen, Department of Statistics, December 1999.
Advisor: Mats Rudemo

Alison Gibbs. Convergence of Markov Chain Monte Carlo Algorithms with Applications to Image Restoration. PhD thesis, University of Toronto, Department of Statistics, October 1999. (Postscript, PDF.)
Advisor: Jeffrey Rosenthal

Jesper Møller. Aspects of spatial statistics, stochastic geometry and Markov chain Monte Carlo methods. Thesis for doctoral degree in Natural Sciences, Aalborg University.

Giovanni Montana. Small sets and domination in perfect simulation. Ph.D. thesis, University of Warwick, April 2002.
Advisor: Wilfrid S. Kendall

There are a number of research talks that do not appear to have associated written articles that are publicly available. These are listed below.

Chris Jennison. Approximate exact sampling: towards the general application of Propp and Wilson's algorithm. Seminar at University of Bath, 1998.

Abstract: Propp and Wilson's sampling-from-the-past rule allows the possibility of exact sampling by Markov chain Monte Carlo (MCMC) methods. We describe the Propp and Wilson method and consider details of its practical usage.
We then consider a scheme for applying the basic idea of Propp and Wilson in general problems. The method becomes approximate once more but with arguable advantages over other MCMC samplers.

Abstract: I have studied a Markov chain which describes the dispersal of mites on cassava fields in West Africa. Instead of obtaining a sample of this model with approximately the stationary distribution by Monte Carlo simulation, it is possible to obtain a result which is exactly distributed according to the stationary distribution. One way to do this is coupling from the past. After a short introduction of this procedure I will explain the changes I have made to the original model in order to be able to use coupling from the past and show some simulations which give exact samples.

Abstract:

The Monte Carlo community recently has had a pleasant surprise. Based on their ingenious idea of running coupled Markov chains with negative time, Propp and Wilson (1996, Random Structures and Algorithms ) proposed a Markov chain Monte Carlo (MCMC) algorithm that will, with probability one, terminate itself in a finite number of steps and yet deliver draws that are exactly from the limiting (i.e., stationary) distribution. By applying the algorithm to a variety of problems, including sampling exactly from the Ising model at the critical temperature with a 4200 by 4200 toroidal grid, they demonstrated the practicality and efficiency of the algorithm. Their findings are perhaps particularly exciting for statisticians/probabilists/applied mathematicians, since this appears to be the first time that a major Monte Carlo method is developed solely by non-physicists, yet the method is applicable to non-trivial computational problems in physics and other scientific studies. Built upon their method of coupling from the past or backward coupling, a new class of MCMC algorithms has emerged. This class of algorithms has been labeled perfect simulation or exact simulation, because for this class of stochastic iterative algorithms the challenging issue of accessing convergence as well as errors in approximation completely vanishes.

In this talk I will first give a brief tutorial of the Propp-Wilson algorithm and Murdoch and Green's (1998, Scandinavian Journal of Statistics) extension to continuous-state Markov chains. I will then propose two methods, multi-stage backward coupling and parallel antithetic coupling, for improving the computational or equivalently statistical efficiency of the current perfect simulation schemes. The first method borrows ideas from survey sampling where it is a common knowledge that multi-stage sampling is typically more cost effective than single-stage sampling. The second method explores the use of antithetic variates with backward coupling, and it relies critically on the theory of negative association, which studies the preservation of negative correlation under monotone transformations. Limited empirical and theoretical evidence suggests the possibility of significant improvement (e.g., 30%-50% reduction in time/variance) with either method over the Propp-Wilson algorithm in certain applications.

While the theory and implementation of the proposed methods is not completely trivial, the talk should be accessible to both the pessimists (nothing is perfect) and the optimists (things can always be better).

Abstract:
Since the seminal work of Propp and Wilson on perfect sampling, two algorithms for perfect sampling are known, one based on coupling from the past (CFTP) by Propp and Wilson, and the other via rejection sampling by Fill. The idea of perfect sampling is, in essence, that given an ergodic Markov chain we can generate a perfect stationary observation within a finite number of steps. The CFTP algorithm has been studied and used in various ways along with applications in Markov Chain Monte Carlo (MCMC). However, the reports on similar investigations for Fill's algorithm are limited compared with the CFTP algorithm.
Recently Hobert, Robert, and Titterington studied the implementation of the CFTP algorithm for two- and three-component mixtures with known components and reported the performances of the CFTP algorithm for these cases. They showed that the MCMC for the two-component mixture is monotone with a natural linear ordering over the weights. By extending such coupling to the case of three-component mixture, they observed that the coupled chains are contained in a lozenge-shaped region, which simplifies the algorithm to detect coalescence. But their coupling method for $k$-component mixtures with $n$ samples requires ${{n+k-1}{k-1}}$ transitions at the initial step, no matter how much the size of transitions can be reduced later. Therefore, as they argued, it is difficult to extend their method further because of the combinatorial explosion.
The coalescence of all the coupled chains is the essential characteristic for the CFTP algorithm. On the other hand, Fill's algorithm for stochastically monotone case, in theory, does not require such grand coalescence. In fact, as shown in Fill's paper, the proof of his algorithm's validity relies only on the property of a bivariate coupling. In this talk, we exploit this property further and demonstrate how we can use it for mixture problems of more than three components.

Abstract: Many images found in microscopy, material science and biology can be described by means of a random set. Perhaps the best known example is the Boolean model (Matheron (1975)) formalising a configuration of independent, randomly placed particles. Notwithstanding the strong independence assumptions, because of the occlusion effect inherent in the fact that only the image of all particles is observable rather than individual ones, inference for Boolean models is far from trivial (Molchanov (1997)). In this talk, we will outline a likelihood approach for the intensity parameter of a Boolean model of discs (sometimes called the bombing model). An important ingredient of our technique is to augment the data by those particles that are occluded using coupling from the past (Propp and Wilson (1996)).
The talk is based on joint work with E W van Zwet (Utrecht)

Abstract: An MCMC sampling procedure known as coupling from the past (CFTP) is described for variable selection in the Bayesian linear model with orthogonal predictors, which includes wavelets, Fourier series and Chebyshev polynomials. CFTP allows one to draw perfect i.i.d. samples from the posterior model space in realistic CPU time. Examples are used to demonstrate this approach on a number of curve fitting problems.

Abstract: Lorsque l'on souhaite engendrer des objets selon une distribution P, on peut construire une chaine de Markov ergodique dont la distribution stationnaire est P. Tout le probleme est de savoir combien de temps il faut faire tourner ce processus pour approcher à epsilon pres la distribution stationnaire, i.e borner le temps de mélange de la chaine. La méthode "Couplage depuis le passé" [Kendall, Propp,Wilson, Jerrum,...] permet de s'abstenir de ces calculs souvent compliqués et d'obtenir un échantillon de l'ensemble des états, distibué exactement selon la distribution stationnaire.

Abstract: Propp and Wilson's (1996) coupling from the past (CFTP) algorithm generates a sample from the limiting distribution of a Markov chain. In this talk I argue that the underlying idea of CFTP is more widely applicable, and will demonstrate successful and unsuccessful attempts to apply it to problems ranging from approximation of integrals to simulation of stochastic differential equations.

Abstract: Initiated by the seminal work of Propp and Wilson (1996), a new class of MCMC algorithms has emerged. This class of algorithms has been labeled perfect simulation or exact simulation because, for this class of stochastic iterative algorithms, the challenging issue of accessing convergence as well as errors in approximation completely vanishes. In this paper we propose the methods of multi-stage backward coupling and of parallel antithetic coupling to expand the Propp and Wilson's framework of backward coupling. The first method borrows ideas from survey sampling where it is a common knowledge that multi-stage sampling is typically more cost effective than single-stage sampling. The second method explores the use of antithetic variates with backward coupling, and it relies critically on the theory of negative association, which studies the preservation of negative correlation under monotone transformations. Limited empirical and theoretical evidence suggests the possibility of significant improvement (e.g., 30%-50% reduction in time/variance) with either method over the Propp-Wilson algorithm in certain applications.

Abstract: The class of Markov chains having a specified stationary distribution is very large, so it is important to have criteria telling when one chain performs better than another. The Peskun ordering is a partial ordering on this class. We study the implications of the Peskun ordering both in finite and general state spaces. Unfortunately there are many Metropolis-Hastings samplers that are not comparable in the Peskun sense. We thus define a more useful ordering, the covariance ordering, that allows us to compare a wider class of sampling schemes. It is always possible to beat the Metropolis-Hastings algorithm in terms of the Peskun ordering. Two new algorithms will be introduced and studied for this purpose. The slice sampler outperforms the independence Metropolis-Hastings algorithm. The splitting rejection sampler outperforms the more general Metropolis-Hastings algorithm. Finally we propose a ``perfect'' version of the slice sampler. Perfect sampling allows exact simulation of random variables from the stationary measure of a Markov chain. By exploiting monotonicity properties of the slice sampler we show that a perfect version of the algorithm can be easily implemented.

Abstract: Since Propp and Wilson's seminal work published in 1996, the perfect sampling technique has extended its research into many ways, particularly in applications with Markov Chain Monte Carlo (MCMC). Given an ergodic Markov chain, the idea of perfect sampling is, in essence, to generate a sample from the exact stationary distribution in finites steps. Two methods for developing such a perfect samplingalgorithm are known, the one based on coupling from the past (CFTP) by Propp and Wilson (1996) and the other via rejection sampling by Fill (1998).

Fill's algorithm has been known for its advantage to be independent of the running time, but also for its intricacy in both theory and practice. The recent paper by Fill, Machida, Murdoch, and Rosenthal (1999) spelled out a general framework for his algorithm, and proposed various possible extension Hobert, Robert, and Tittering (1999) have studied CFTP algorithm for an MCMC evaluation as simple mixture problems. Their study was limited to two-and three-component mixtures, and suggested a difficulty in implementing CFTP algorithm when the mixture has more than three components. We demonstrate how a framework of Fill's algorithm can be applied for this particular mixture problem, and propose a perfect sampling algorithm using a cross-monotone chain. Our algorithm can be implemented with any number of components, but may not perform well as the number of components increases. The objective of this study is to further stimulate practical applications based on Fill's algorithm.

Abstract: Many branches of Probability Theory have benefited from coupling constructions, not least the theory of Markov chains. The coupling inequality for example allows us to bound the total variation distance of a Markov chain to its stationary distribution, in an entirely probabilistic way. This has led recently to computable bounds. As another example, Perfect Simulation exploits couplings to produce exact samples from distributions that are hard to simulate from. A central problem is the actual construction of the coupling, which tends to be problem specific and something of an art form. The "splitting technique" is one method which is very general and has been very successful for years. Among its drawbacks are the need to perform analytic estimates before the method can be applied. In this talk, we shall propose a "more automatic" way of coupling Markov chains, which does not require such estimates, and is applicable to a variety of chains.

Abstract: "Perfect simulation"-- Markov chain Monte Carlo with no statistical error. It sounds great, it even looks kind of easy. So why aren't you doing it? Probably because, as they say, "the devil is in the details." Perfect simulation methods are based on the idea of coupling sample paths of a Markov chain. In this talk we will explore the details of three specific examples, each having specific implementation difficulties. We will consider an unbounded storage model where paths must be coupled on a continuous state space, the standard Ising model of magnetism (both the ferromagnet and antiferomagnet) where paths are running around in a more complicated state space of "spin configurations", and the hard-core lattice gas model where sample paths will naturally repel one another despite the fact that our goal is to get them to meet.

Information on heuristic algorithms for assessing Markov chain convergence to the stationary distribution (among other things) can be found in these resources:

Alan D. Sokal. Monte Carlo methods in statistical mechanics: Foundations and new algorithms, 1989. Lecture notes from Cours de Troisième Cycle de la Physique en Suisse Romande. Updated in 1996 for the Cargèse Summer School on ``Functional Integration: Basics and Applications.'' (Click here to download.)

MCMC Preprint Service

Persi Diaconis and Laurent Saloff-Coste. What do we know about the Metropolis algorithm?, In Proceedings of the Twenty-Seventh Annual ACM Symposium on the Theory of Computing, pages 112-129, 1995.

Mark Jerrum and Alistair Sinclair. The Markov chain Monte Carlo method: an approach to approximate counting and integration, in ``Approximation Algorithms for NP-hard Problems,'' D.S.Hochbaum ed., PWS Publishing, Boston, 1996. (Click here to download.)

David Aldous and Persi Diaconis. Shuffling Cards and Stopping Times, American Mathematical Monthly, 93(5):333-348, 1986.

A more recent and more developed reference on stopping times:

Persi Diaconis and James A. Fill. Strong stationary times via a new form of duality. The Annals of Probability, 18:1483--1522, 1990.

Gérard Letac. A contraction principle for certain Markov chains and its applications. In Random Matrices and Their Applications, volume 50 of Contemporary Mathematics, pages 263--273, 1986.

Herman Thorisson. Backward limits, The Annals of Probability 16(2):914--924, 1988.

A. A. Borovkov and S. G. Foss. Stochastically recursive sequences and their generalizations. Siberian Advances in Mathematics, 2(1):16--81, 1992.

David J. Aldous and James A. Fill. Reversible Markov Chains and Random Walks on Graphs. Book in preparation, http://www.stat.berkeley.edu/~aldous/book.html.

When explaining CFTP to an audience, there are invariably many questions. Included below are some of these questions together with their answers. [Adapted from section 1.4 of Wilson (2000), first published by the AMS.]

Q: If we always end up in state 3 no matter where we start, then how is that a random sample?
A: For a given particular sequence of coin flips, every possible starting state ends up in state 3. But for a different (random) sequence of coin flips, every possible starting state may end up in a different final state at time 0.

Q: What if we just run the Markov chain forward until coalescence?
A: Consider the toy example of the previous section. Coalescence only occurs at the states 0 and n, so the result would be very far from being distributed according to π.

Q: What happens if we use fresh coins rather than re-using the same coins?
A: Consider the toy example of the previous section, and set n=2 (so the states are 0,1,2). Then one can check that the probability of outputting state 1 has a binary expansion of 0.0010010101001010101010101001..., which is neither rational nor very close to 1/3.

Q: Rather than doubling back in time, what if we double forward in time, and stop the Markov chain at the first power of 2 greater than or equal to the coalescence time?
A: As before, set n=2 in our toy example. One can check that the probability of outputting state 1 is 1/6 rather than 1/3.

Q: What if we instead ...
A: Enough already! There do exist other ways to generate perfectly random samples, but the only obvious change that can be made to the CFTP algorithm without breaking it is changing the sequence of starting times in the past from powers of 2 to some other sequences integers.

Q: If coupling forwards in time doesn't work, then why does going backwards in time work?
A: If you did not like the first explanation, then another way to look at it is that a virtual Markov chain has been running for all time, and so today the state is random. If we can (with probability 1) figure out today's state by looking at some of the recent randomizing operations, then we have a random state.

Q: If going backwards in time works, then why doesn't going forwards in time work?
A1: There is a way to obtain perfectly random samples by running forwards in time (Wilson 2000), but none of the obvious variations described above work.
A2: CFTP determines the state at a deterministic time, any one of which is distributed according to π. The variations suggested above determine the state at a random time, where that time is correlated with the moves of the Markov chain in a complicated way, and these correlations mess things up.

Q: Why did you step back by powers of 2, when any other sequence would have worked?
A: For efficiency reasons. Let $T^*$ be the best time in the past at which to start, i.e. the smallest integer for which starting at time $-T^*$ leads to coalescence. By stepping back by powers of 2, the total number of Markov chain steps simulated is never larger than $4 T^*$ (and closer to $2.8 T^*$ ``on average''); see Propp and Wilson (1996), section 5.2. If we had stepped back by one each time, then the number of simulated steps would have been ${T^*}{2} \approx (1/2) (T^*)^2$. If we had stepped back quadratically, then the number of simulated steps would have been about $(1/3) (T^*)^{3/2}$. For this reason some people prefer quadratic backoff when $T^*$ is fairly small.

Q: So you need the state space to be monotone?
A: That would certainly be very useful, but there are many counterexamples to the proposition that is necessary. See {coupling}.

Q: Can you do CFTP on Banach spaces?
A: I don't know. Depends on whether or not you can figure out the state at time 0.

Q: Where's the proof of efficiency?
A: In the monotone setting, loosely speaking, CFTP is efficient whenever the Markov chain mixes rapidly; see {monotone}. There also proofs of efficiency for certain non-monotone settings.

Q(?): But you still need to analyze the mixing time, since otherwise you won't know how long it will take.
A: Wrong. The principal advantage of using CFTP (or Fill's algorithm) is that you don't need these a priori mixing time bounds in order to run the algorithm, collect perfectly random samples, and carry on with the rest of the research project. The fact that these are perfectly random samples is icing on the cake. (But I still think that mixing time bounds are interesting.)

Q: But sampling spin glass configurations is NP-hard.
A: The spin-glass Markov chain that you're using is probably very slowly mixing in the worst case. CFTP will not be faster than the mixing time of the underlying Markov chain.

Q: Is CFTP like a ZPP or Las Vegas algorithm for random sampling?
A: ``Yes'' for Las Vegas, ``sometimes'' for ZPP. [A Las Vegas algorithm uses randomness to compute a deterministic function. The running time is a random variable, but with probability 1 it returns an answer, and when it does so, the answer is correct. A Monte Carlo algorithm in contrast does not guarantee a correct answer. A problem is in ZPP if it can be solved by polynomial expected time Las Vegas algorithm.]

Q: Could you make a hybrid algorithm, which starts out by doing CFTP, but then does something different if CFTP starts to take a long time?
A: Yes. This would be like experiment $C_T$.

Q: What's the probability that CFTP takes a long time?
A: The tail distribution of the running time decays geometrically. More can be said if the Markov chain is monotone, see {monotone}.

Q: What if I don't want to wait for $10^{70}$ years. Does this make CFTP biased? Is it really better than forwards coupling?
A1: The answer to the second question is yes. How long are you willing to wait? With forward coupling, that's how long you wait. With CFTP your average waiting time is probably much smaller.
A2: The answer to the first question depends on what you mean by ``biased''. No-one disputes that the systematic bias is zero. The so-called ``user-impatience bias'' (the effect of an impatient user interrupting a simulation and progress) is a second order effect that pertains to most random sampling algorithms that most people would not call biased.
A3: If you're genuinely concerned about the quality of your random samples, you should first spend time picking a good pseudo-random number generator.
A4: Anyone concerned about ``user-impatience bias'' should be equally concerned about ``user-patience bias'': if an experimenter run simulations until some deadline, and then lets the last one finish before quitting, then the resulting collection of samples is biased to contain more samples that take a long time to generate. But if the experimenter instead aborts the last simulation (unless there are no samples so far, in which case (s)he lets it finish), then the resulting collection of samples is unbiased. See Glynn and Heidelberger.

Q: Can you quantify the user-impatience bias?
A: If you generate N samples before your deadline, and then average some function of these samples, the bias is at most Pr[N=0]. If you do something sensible in the event that N=0, the bias will be even less. See Glynn and Heidelberger.

Postscript illustration of monotone coupling from the past (CFTP)

Postscript illustration of the Murdoch-Green rejection coupler

Postscript illustration of the Murdoch-Green partitioned multigamma coupler

Postscript illustration of the Green-Murdoch random walk Metropolis bisection coupling

Postscript illustration of Green-Murdoch random walk Metropolis bounded CFTP

Jason Woolever's random tiling applets (using monotone-CFTP)

Wilfrid Kendall's animated comparsion of forwards and backwards coupling

Georgii's perfect continuum Ising model pictures

Jeffrey Rosenthal's monotone-CFTP applet for the chain

2-state Potts 3-state Potts 4-state Potts 5-state Potts

The 2-state, 3-state, 4-state, and 5-state Potts models at their respective critical temperatures on the 2D grid, generated by monotone-CFTP on the Fortuin-Kasteleyn random-cluster model.

The 4-state Potts model is particularly interesting, click here to learn why and to see much larger perfectly random 4-state Potts configurations.

Childs, Patterson, and MacKay give a number of perfect Potts configurations with antiferromagnetic and ferromagnetic interactions, as well as a number of associated animations, and plots of thermodynamic quantities.

A random spanning tree of the grid, generated by loop-erased random walk. (A spanning tree of a graph is a connected, acyclic subgraph of the given graph.)

A random lozenge tiling of a hexagon, generated by monotone-CFTP. A lozenge is a 60-120 degree rhombus. The three different orientations of lozenges are shown in different colors.

(Representation of) random ``square ice'' with extremal boundary conditions, generated by monotone-CFTP. In the square ice model each vertex of the square grid points to two of its neighbors, and is pointed at by its two other neighbors. To get this representation, the outgoing arcs from the even-parity vertices were used to create contour lines. The spaces between these contours were alternately colored blue and white. Extremal boundary conditions, associated with alternating sign matrices, were used.

Random independent set of the grid (with periodic boundary conditions, and ``activity'' or ``fugacity'' 2), generated by monotone-CFTP. An independent set of a graph is a set of vertices such that no two vertices in the set are adjacent. The probability of an independent set is proportional to the fugacity (2 here) raised to the number of points in the set. Points of this random independent set at even-parity grid positions are shown in one color, points at odd-parity grid positions are shown in the other color.

Perfect simulations of the area-interaction point process (from Kendall's web page of abstracts):
(a) attractive case and (b) repulsive case

WRASS cartoon

Included here are the definitions of some terms used but not defined above.

area-interaction point process: Defined relative to the Poisson point process, the probability density of a configuration is given an extra weight that is exponentially small or large in the area of the union of circles (or other fixed shapes) centered about the points. When the extra weight is exponentially small (large) in the area, in a configuration with many points, the points will tend to be nearby (far away), giving the attractive (repulsive) area-interaction point process.

continuum random cluster model: Defined relative to a Poisson point process, clusters are formed by taking the union of circles (or other shapes) centered about the points. The probability density of a configuration gets an extra factor of q for each cluster that it contains. The discrete version of the continuum random cluster model is not the random cluster model, but rather is related to it in the same way that site percolation is related to bond percolation.

dimer model: A dimer configuration is a perfect matching of a graph, i.e. a pairing of the vertices of the graph so that each vertex is paired with exactly one other vertex, connected to it by an edge of the graph. Typically all configurations are equally likely, but sometimes each edge contributes a weight to those perfect matchings that contain it. (The term ``dimer'' comes from considering the vertices to be atoms. The pairing of vertices corresponds to the placement of bonds to make dimers.) Depicted here is a random dimer configuration of the hexagonal grid, generated by monotone-CFTP, and shown as a tiling. Each vertex/atom corresponds to a triangle, and each edge/dimer is shown as a rhombus.

hard core model: A hard-core configuration is an indepen- dent set of a graph, i.e.\ a set of vertices of the graph such that no two vertices are connected by an edge. The probability of an independent set gets an extra factor of λ, known as the ``activity'' or ``fugacity'', for each vertex that it contains. Shown here is a random independent set of the grid (with periodic boundary conditions), with λ=2, generated by monotone-CFTP.

ice model: An ice configuration is an Eulerian orientation of a graph, i.e. an assignment of directions to the edges of a graph so that at each vertex the number of edges directed towards it equals the number of edges directed away from it. Some edges may be fixed at the boundaries of the graph, but given those constraints, all configurations are equally likely. (The term ``ice'' comes from an analogy with ice, where the vertices correspond to water molecules, the edges to hydrogen bonds, and the edge orientations determine which water molecule's hydrogren atom is involved in the hydrogen bond.)

Potts model: Each vertex on a graph (typically a grid) is assigned one of q different colors. The probability of a configu- ration gets an extra weight for each edge whose two endpoints are the same color. (The weight is thought of as being related to an interaction energy and the temperature.) When the weights are at least one, the model is ``ferromagnetic'', if they are less than one, then the model is ``antiferromagnetic''. The case q=2 is the Ising model. When the weight factor is zero, one obtains proper q-colorings.

random-cluster model: Also known as the Fortuin--Kasteleyn random cluster model, and bond-correlated percolation, it can be defined relative to ordinary bond percolation (each edge occuring independently with probability p), where the probability of a configuration gets an extra weight of q for each connected component it contains. When q is a positive integer, this model is closely related to the q-state ferromagnetic Potts model. When q→0 and then p→0, the result is a random spanning tree. When q=1 one gets ordinary percolation.

spanning tree: A connected, acyclic subgraph of a given graph. If the graph is directed, then ``spanning tree'' refers to an ``arborescence'', in which a distinguished vertex is the ``root'' of the tree, and the edges of the tree are directed to- wards the root. A random spanning tree is such a tree (or arborescence) chosen uniformly at random, or if the graph is weighted, with probability proportional to the products of the weights of the edges contained in the tree.

Widom-Rowlinson model: A model in which there are typically two (but possibly more) types of particles, where particles of different types can't be nearby. In the discrete case, there is a graph, each vertex may contain zero or one particles, and no edge has two different types of particles on its endpoints. The probability of a legal configuration is proportional to some constant (the ``fugacity'' or ``activity'') raised to the power of the number of particles. In the continuous case, particles lie in the plane (or other manifold), and particles of different type must be some minimum distance apart. The probability density of a configuration is what one would get by randomly assigning particle types to the points of a Poisson process, and conditioning on the configuration being legal.

There seems to be enough perfect sampling code on the web to warrant making a section of links to it. Here is a partial listing, I will add more links as I track them down or they are called to my attention.

• Wilfrid Kendall's page on perfect simulation includes several programs
• XRC, X-windows program for generating Random Cluster states, as well as Ising and Potts states
• Program for generating samples from the Strauss point process
• Programs for generating samples from the autonormal and autogamma distributions
• Jesper Møller's ftp site includes some perfect simulation code
• Geoff Nicholls' image restoration software: JPG example and code
• Armin S. A. Rährl's java code for CFTP
• Paul Fearnhead's perfect simulation for genetic models software

The maintainer thanks Andrei Broder, James A. Fill, Wilfrid S. Kendall, Jesper Møller, and James G. Propp for their helpful comments, and David J. C. MacKay for help updating the HTML.