Librería Portfolio

Exact sampling, specifically coupling from the past (CFTP), allows users to sample exactly from the stationary distribution of a Markov chain. During its nearly 20 years of existence, exact sampling has evolved into perfect simulation, which enables high-dimensional simulation from interacting distributions.

Perfect Simulation illustrates the application of perfect simulation ideas and algorithms to a wide range of problems. The book is one of the first to bring together research on simulation from statistics, physics, finance, computer science, and other areas into a unified framework. You will discover the mechanisms behind creating perfect simulation algorithms for solving an array of problems.

The author describes numerous protocol methodologies for designing algorithms for specific problems. He first examines the commonly used acceptance/rejection (AR) protocol for creating perfect simulation algorithms. He then covers other major protocols, including CFTP; the Fill, Machida, Murdoch, and Rosenthal (FMMR) method; the randomness recycler; retrospective sampling; and partially recursive AR, along with multiple variants of these protocols. The book also shows how perfect simulation methods have been successfully applied to a variety of problems, such as Markov random fields, permutations, stochastic differential equations, spatial point processes, Bayesian posteriors, combinatorial objects, and Markov processes.



Introduction

Two examples

What is a perfect simulation algorithm?

The Fundamental Theorem of perfect simulation

A little bit of measure theory

Notation

A few applications

Markov chains and approximate simulation

Designing Markov chains

Uniform random variables

Computational complexity

Acceptance/Rejection

The method

Dealing with densities

Union of sets

Randomized approximation for #P complete problems

Gamma Bernoulli approximation scheme

Approximate densities for perfect simulation

Simulation using Markov and Chernoff inequalities

Where AR fails

Coupling from the Past

What is a coupling?

From the past

Monotonic CFTP

Slice samplers

Drawbacks to CFTP

Bounding Chains

What is a bounding chain?

The hard-core gas model

Swendsen-Wang bounding chain

Linear extensions of a partial order

Self-organizing lists

Using simple coupling with bounding chains

Advanced Techniques Using Coalescence

Read-once coupling from the past

Fill, Machida, Murdoch, and Rosenthal's method

Variable chains

Dealing with infinite graphs

Clan of ancestors

Deciding the length of time to run

Coalescence on Continuous and Unbounded State Spaces

Splitting chains

Multigamma coupling

Multishift coupling

Auto models

Metropolis-Hastings for continuous state spaces

Discrete auxiliary variables

Dominated coupling from the past

Using continuous state spaces for permutations

Spatial Point Processes

Acceptance/rejection

Thinning

Jump processes

Dominated coupling from the past for point processes

Shift moves

Cluster processes

Continuous-time Markov chains

The Randomness Recycler

Strong stationary stopping time

Example: RR for the Ising model

The general randomness recycler

Edge-based RR

Dimension building

Application: sink-free orientations of a graph

Advanced Acceptance/Rejection

Sequential acceptance/rejection

Application: approximating permanents

Partially recursive acceptance/rejection

Rooted spanning trees by popping

Stochastic Differential Equations

Brownian motion and the Brownian bridge

An exponential Bernoulli factory

Retrospective exact simulation

Applications and Limitations of Perfect Simulation

Doubly intractable distributions

Approximating integrals and sums

Omnithermal approximation

Running time of TPA

The paired product estimator

Concentration of the running time

Relationship between sampling and approximation

Limits on perfect simulation

The future of perfect simulation