English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

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 flnite 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 difierent 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 modiflcation) to antimonotone" chains. When the chain is reversible, naive implementation of the algorithm uses fewer transitions but more space than Propp{Wilson. When flne-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 is polynomial in n, the algorithm runs in time of the same order (bound) as Propp{Wilson [expectation O(logn)] and uses only logarithmically more space [expectation O(n logn), vs. O(n) for Propp{Wilson]. AMS 1991 subject classiflcations. Primary 60J10; secondary 68U20, 60G40, 62D05. Key words and phrases. Markov chain Monte Carlo, perfect simulation, rejection sampling,

An interruptible algorithm for perfect sampling via Markov chains