Partially Recursive Acceptance Rejection

MaRDI QIDQ6281545zbMATH OpenFDO

Authors Mark Huber

Publication date 30 December 2016

Mathematics Subject Classification ID

Monte Carlo methods (65C05) Analysis of algorithms (68W40)

Abstract: Generating random variates from high-dimensional distributions is often done approximately using Markov chain Monte Carlo. In certain cases, perfect simulation algorithms exist that allow one to draw exactly from the stationary distribution, but most require $O(nln(n))$ time, where $n$ measures the size of the input. In this work a new protocol for creating perfect simulation algorithms that runs in $O(n)$ time for a wider range of parameters on several models (such as Strauss, Ising, and random cluster) than was known previously. This work represents an extension of the popping algorithms due to Wilson.

This page was built for publication: Partially Recursive Acceptance Rejection

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6281545)