adaptive-rejection-sampler

Adaptive rejection sampling (ARS) generates samples from log-concave distributions by constructing a piecewise linear envelope using tangent lines at evaluated points. The algorithm iteratively refines this envelope, drawing candidates from the upper hull and accepting or rejecting them based on acceptance tests, then updating the envelope with rejected points to improve efficiency over iterations.

Log-concavity means the logarithm of a probability density function is concave, ensuring tangent lines form valid upper and lower bounds. This property enables ARS to construct guaranteed envelopes for rejection sampling, making the algorithm both theoretically sound and computationally efficient for distributions like exponential and Gaussian.

Verify log-concavity by confirming the second derivative of the log density is non-positive across the domain, or test numerically with tolerance thresholds. ARS implementations should include verification routines and test against standard log-concave distributions like exponential and Gaussian to confirm envelope construction is correct.

Initialization requires selecting starting points where the tangent lines are evaluated to build the initial envelope. Effective strategies include spacing points uniformly across the support or using quantiles, ensuring the envelope adequately bounds the target density before sampling begins.

Optimize ARS by tuning iteration limits to balance envelope quality against computational cost and implementing timeout safeguards to prevent runaway sampling. Monitor acceptance rates and envelope tightness; if acceptance drops or iterations exceed thresholds, adjust initialization or point-selection strategies.

ARS applies to any log-concave distribution. Beyond exponential and Gaussian, it works with log-normal, Laplace, and other log-concave densities. Verify log-concavity for your target, test envelope bounds numerically with tolerances, and validate sampling output against known statistics before production use.