If you would like to learn CFTP and/or Fill's algorithm, there are several expositions to choose from. Many articles which develop new coupling techniques for use in CFTP or Fill's algorithm also contain brief explanations of these techniques.

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.

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.

Morten Fismen. Exact simulation using Markov chains. Technical Report 6/98,

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.

Karin Nelander. A Markov chain Monte Carlo study of the beach model. Markov Processes and Related Fields 6(3):345--369, 2000.

Abstract: We study the beach model introduced by 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.

Abstract: The greatest drawback of Monte Carlo Markov chain methods is lack of knowledge of the mixing time of the chain. The use of bounding chains solves this difficulty for some chains by giving theoretical and experimental upper bounds on the mixing time. Moreover, when used with methodologies such as coupling from the past, bounding chains allow the user to take samples drawn exactly from the stationary distribution without knowledge of the mixing time. Here we present a bounding chain for the Swendsen-Wang process. The Swendsen-Wang bounding chain allow us to efficiently obtain exact samples from the ferromagnetic Q-state Potts model for certain classes of graphs. Also, by analyzing this bounding chain, we will show that Swendsen-Wang is rapidly mixing over a slightly larger range of parameters than was known previously.

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.

Updated to
C. C. Holmes and B. K. Mallick. Perfect simulation for Bayesian curve and surface fitting, 1999. Preprint.

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.

Armin S. A. Rährl.

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.

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 efficient 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 efficiency.

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 show how to perform perfect simulation of a functional of a Dirichlet process, when the values of the functional are bounded. We also give a procedure for ``approximate'' simulation in the case of unbounded functional values.

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 efficient 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.

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.

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.