Perfect Reversal of Rejection Sampling Methods for First-Passage-Time and Similar Probability Distributions

Abstract

We present a perfectly reversible method for bi-directional generation of samples from computationally complex probability distributions. While the previously best-known procedures consume memory proportional to the length of execution between changes of execution direction, here we present a scheme to completely eliminate the memory overhead. Our solution affords two important features, namely determinism and repeatability, across arbitrarily spaced changes of direction (and arbitrary number of samples) along the sample stream. We illustrate the perfect reversal method with first passage time distributions that appear in physical system models, and present its implementation and verification in FORTRAN.