pith. sign in

arxiv: 1907.06748 · v1 · pith:E4MXDBTOnew · submitted 2019-07-15 · 💻 cs.DS · math.PR· stat.CO

Designing Perfect Simulation Algorithms using Local Correctness

Mark Huber This is my paper

Pith reviewed 2026-05-24 20:59 UTC · model grok-4.3

classification 💻 cs.DS math.PRstat.CO
keywords perfect simulationrecursive algorithmslocal correctnessexact samplingBernoulli factoryacceptance-rejectioncoupling from the past
0
0 comments X

The pith

A recursive sampling algorithm produces exact draws from a target distribution exactly when it terminates with probability 1 and passes a local-correctness check.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows that many seemingly different perfect-simulation methods all succeed for the same two reasons. An algorithm must halt almost surely, and it must remain correct when every recursive call is replaced by an oracle that already draws from the target distribution. Verifying these conditions is usually direct and avoids circular reasoning about the global output law. The same test immediately certifies acceptance-rejection, coupling from the past, partial rejection sampling, and several Bernoulli factories. The author also uses the test to construct a new linear Bernoulli factory that runs 41 percent faster than the prior version.

Core claim

The Fundamental Theorem of Perfect Simulation asserts that the output of any recursive probabilistic algorithm is distributed exactly according to a target law if and only if the algorithm terminates with probability 1 and is locally correct, where local correctness is established by substituting oracles for the recursive calls and proving that the resulting non-recursive procedure is correct.

What carries the argument

The Fundamental Theorem of Perfect Simulation, which reduces global exactness of a recursive sampler to termination and a local oracle-substitution check.

If this is right

  • Acceptance-rejection, coupling from the past, read-once CFTP, partial rejection sampling, and several Bernoulli factories are all correct because each satisfies the two conditions.
  • A new Bernoulli factory for linear functions can be proved correct by the same local check and runs 41 percent faster than the earlier construction.
  • Designers of perfect simulators can focus effort on establishing termination and local correctness rather than analyzing the full output distribution directly.
  • Any future recursive procedure shown to meet the two conditions is automatically guaranteed to be exact.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same local-check strategy might simplify correctness arguments for approximate sampling schemes that are later derandomized or made exact.
  • High-dimensional or continuous-state samplers whose global analysis is intractable could become tractable once reduced to a local oracle test.
  • The theorem suggests a systematic way to compose existing perfect simulators into larger ones while preserving exactness.

Load-bearing premise

The local-correctness property can be verified by oracle substitution without any circular dependence on the correctness of the original recursive procedure.

What would settle it

A concrete recursive algorithm that halts with probability 1, whose oracle-substituted version is provably correct, yet whose output distribution differs from the claimed target would refute the theorem.

read the original abstract

Consider a randomized algorithm that draws samples exactly from a distribution using recursion. Such an algorithm is called a perfect simulation, and here a variety of methods for building this type of algorithm are shown to derive from the same result: the Fundamental Theorem of Perfect Simulation (FTPS). The FTPS gives two necessary and sufficient conditions for the output of a recursive probabilistic algorithm to come exactly from the desired distribution. First, the algorithm must terminate with probability 1. Second, the algorithm must be locally correct, which means that if the recursive calls in the original algorithm are replaced by oracles that draw from the desired distribution, then this new algorithm can be proven to be correct. While it is usually straightforward to verify these conditions, they are surprisingly powerful, giving the correctness of Acceptance/Rejection, Coupling from the Past, the Randomness Recycler, Read-once CFTP, Partial Rejection Sampling, Partially Recursive Acceptance Rejection, and various Bernoulli Factories. We illustrate the use of this algorithm by building a new Bernoulli Factory for linear functions that is 41\% faster than the previous method.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 1 minor

Summary. The paper introduces the Fundamental Theorem of Perfect Simulation (FTPS), which states that a recursive probabilistic algorithm outputs exact samples from a target distribution if and only if it terminates almost surely and satisfies local correctness (i.e., the non-recursive algorithm obtained by replacing recursive calls with oracles that draw from the target distribution is correct). The theorem is used to recover the correctness of Acceptance/Rejection, Coupling from the Past, the Randomness Recycler, Read-once CFTP, Partial Rejection Sampling, Partially Recursive Acceptance Rejection, and various Bernoulli factories, and is applied to construct a new Bernoulli factory for linear functions claimed to be 41% faster than prior methods.

Significance. If the FTPS holds with the claimed necessity and sufficiency, it supplies a first-principles unifying criterion for perfect simulation that separates termination from distributional correctness and permits independent verification of the latter via oracles. This framework directly accounts for the correctness of multiple established algorithms without ad-hoc arguments and enables new constructions, which is a substantive contribution to the design of exact sampling methods in theoretical computer science.

major comments (1)
  1. [Abstract] The abstract asserts that the two conditions are necessary and sufficient and that local correctness is 'usually straightforward' to verify, yet supplies no formal statement of the theorem (no numbered conditions, no measure-theoretic setup, no explicit definition of the probability space or the oracle replacement). Without this, it is impossible to confirm that the sufficiency direction closes without circular appeal to properties of the target measure itself.
minor comments (1)
  1. [Abstract] The 41% speedup claim for the new Bernoulli factory should be accompanied by the precise definition of the linear function, the previous baseline algorithm, and the exact runtime metric used.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We appreciate the referee's detailed feedback on our manuscript. Below we address the major comment point by point.

read point-by-point responses

  1. Referee: [Abstract] The abstract asserts that the two conditions are necessary and sufficient and that local correctness is 'usually straightforward' to verify, yet supplies no formal statement of the theorem (no numbered conditions, no measure-theoretic setup, no explicit definition of the probability space or the oracle replacement). Without this, it is impossible to confirm that the sufficiency direction closes without circular appeal to properties of the target measure itself.

    Authors: The abstract is intended as a concise summary for a broad audience and therefore does not include the full formal statement. The complete statement of the Fundamental Theorem of Perfect Simulation, including the measure-theoretic setup on the space of execution traces, the definition of local correctness via oracle replacement, and the numbered conditions, appears as Theorem 1 in Section 2 of the manuscript. The proof of sufficiency shows that if the algorithm terminates almost surely and the local version is correct, then the output distribution must coincide with the target by solving the fixed-point equation induced by the recursion; this argument does not appeal circularly to the target measure because local correctness is established independently by direct verification on the non-recursive procedure. We are happy to add a parenthetical reference to Theorem 1 in the abstract if the editor deems it appropriate. revision: partial

Circularity Check

0 steps flagged

FTPS theorem is self-contained with independent verification conditions

full rationale

The paper states the FTPS as two necessary and sufficient conditions (almost-sure termination plus local correctness via oracle replacement for recursive calls) whose verification is described as usually straightforward and independent of the global target. No equations, proofs, or applications in the provided text reduce the claimed sufficiency to a self-definition, a fitted parameter renamed as prediction, or a load-bearing self-citation chain. The unification of existing methods (AR, CFTP, etc.) is presented as a consequence of the theorem rather than the theorem being defined in terms of those methods. This is the normal case of a non-circular first-principles result.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

Based solely on the abstract, the result rests on standard axioms of probability (termination almost surely, correctness under oracle substitution) with no free parameters, invented entities, or ad-hoc assumptions visible.

axioms (2)
  • domain assumption A recursive algorithm terminates with probability 1.
    Stated as first necessary condition in the FTPS description.
  • domain assumption Local correctness holds when recursive calls are replaced by oracles from the target distribution.
    Stated as second necessary and sufficient condition.

pith-pipeline@v0.9.0 · 5707 in / 1371 out tokens · 19752 ms · 2026-05-24T20:59:41.615892+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

24 extracted references · 24 canonical work pages · 1 internal anchor

  1. [1]

    Asmussen, P

    S. Asmussen, P. W. Glynn, and H. Thorisson. Stationarity detection in the initial transient problem. ACM Trans. Modeling and Computer Simulation, 2(2):130–157, 1992

    work page 1992

  2. [2]

    Beskos, O

    A. Beskos, O. Papspiliopoulous, and G. O. Roberts. Retro spective exact simulation of diffusion sample paths with applications . Bernoulli, 12(6):1077–1098, 2006

    work page 2006

  3. [3]

    H. Cohn, R. Pemantle, and J. Propp. Generating a random si nk-free orientation in quadratic time. Electron. J. Combin. , 9(1), 2002

    work page 2002

  4. [4]

    M. Dyer, A. Frieze, and R. Kannan. A random polynomial-ti me al- gorithm for approximating the volume of convex bodies. J. Assoc. Comput. Mach. , 38(1):1–17, 1991

    work page 1991

  5. [5]

    Ferrari, R

    P.A. Ferrari, R. Fern´ andez, and N. L. Garcia. Perfect si mulation for interacting point processes, loss networks and ising model s. Stochastic Process. Appl., 102(1):63–68, 2002

    work page 2002

  6. [6]

    J. A. Fill and M. L. Huber. The Randomness Recycler: A new a pproach to perfect sampling. In Proc. 41st Sympos. on Foundations of Comp. Sci., pages 503–511, 2000

    work page 2000

  7. [7]

    H. Guo, M. Jerrum, and J. Liu. Uniform sampling through th e Lovasz local lemma. In STOC, 2017

    work page 2017

  8. [8]

    M. Huber. Perfect sampling using bounding chains. Annals of Applied Probability, 14(2):734–753, 2004

    work page 2004

  9. [9]

    M. Huber. Exact sampling from perfect matchings of dense regular bipartite graphs. Algorithmica, 44:183–193, 2006

    work page 2006

  10. [10]

    M. Huber. Fast perfect sampling from linear extensions . Discrete Math- ematics, 306:420–428, 2006. 16

    work page 2006

  11. [11]

    M. Huber. Perfect simulation with exponential tails. Random Structures Algorithms, 33(1):29–43, 2008

    work page 2008

  12. [12]

    M. Huber. Nearly optimal Bernoulli factories for linea r functions. Com- bin. Probab. Comput. , 25(4):577–591, 2016. arXiv:1308.1562

    work page internal anchor Pith review Pith/arXiv arXiv 2016

  13. [13]

    M. L. Huber. Perfect Simulation. Number 148 in Chapman & Hall/CRC Monographs on Statistics & Applied Probability. CRC Press, 2015

    work page 2015

  14. [14]

    Jerrum and A

    M. Jerrum and A. Sinclair. Approximating the permanent . J. Comput., 18:1149–1178, 1989

    work page 1989

  15. [15]

    Jerrum and A

    M. Jerrum and A. Sinclair. Polynomial-time approximat ion algorithms for the Ising model. SIAM J. Comput. , 22:1087–1116, 1993

    work page 1993

  16. [16]

    R. M. Karp and M. Luby. Monte-Carlo algorithms for enume rating and reliability problems. In Proc. FOCS, pages 56–64, 1983

    work page 1983

  17. [17]

    Nacu and Y

    S. Nacu and Y. Peres. Fast simulation of new coins from ol d. Ann. Appl. Probab., 15(1A):93–115, 2005

    work page 2005

  18. [18]

    J. G. Propp and D. B. Wilson. Exact sampling with coupled Markov chains and applications to statistical mechanics. Random Structures Algorithms, 9(1–2):223–252, 1996

    work page 1996

  19. [19]

    J. G. Propp and D. B. Wilson. How to get a perfectly random sample from a generic Markov chain and generate a random spanning tr ee of a directed graph. J. Algorithms , 217:170–217, 1998

    work page 1998

  20. [20]

    J. S. Provan and M. O. Ball. The complexity of counting cu ts and of computing the probability that a graph is connected. SIAM J. Comput. , 12:777–788, 1983

    work page 1983

  21. [21]

    S. Resnick. Adventures in Stochastic Processes . Birkh¨ auser, 1992

    work page 1992

  22. [22]

    von Neumann

    J. von Neumann. Various techniques used in connection w ith random digits. In Monte Carlo Method , Applied Mathematics Series 12, Wash- ington, D.C., 1951. National Bureau of Standards

    work page 1951

  23. [23]

    Wild and W

    P. Wild and W. R. Gilks. Algorithm as 287: Adaptive rejec tion sam- pling from log-concave density functions. J.R. Stat. Soc. Ser. C. Appl. Stat., 42(4):701–709, 1993

    work page 1993

  24. [24]

    D. B. Wilson. How to couple from the past using a read-onc e source of randomness. Random Structures Algorithms , 16(1):85–113, 2000. 17

    work page 2000