Last Saturday, while getting reacquainted with my home desk, I was delighted to spot a new arXival by Luc Devroye! Entitled the acceptance-complement method revisited, it discusses a variant of accept-reject method, where the target density f(·) is squeezed between two functions
0≤r(x)≤f(x)≤r(x)+q(x)
and can be simulated as the mixture
r(x)+(f(x)-r(x)),
assuming both r(·) and q(·) are proportional to densities that can easily be simulated. (With the additional constraint of q(·) having at most mass 1.) The nicest part is that the algorithm is always one-pass, as
- generate Y~ q(y), U ~U(0,1)
- if Uq(Y)<f(Y)-r(Y), set X=Y
- else generate X~r(x)
with step 2 having two outcomes: either generate a realisation of [the density proportional to] f(·)-r(·) or generate an event of probability α when α is the mass [normalising constant] of r(·). This explains step 3 since the rejection of Y implies simulation from the second component of f(·). Brilliant! And Devroye derives a universal accept-complement algorithm for generic log-concave densities (that differs from Gilks & Wild, 1992.).
