  The adaptive rejection sampling (ARS) algorithm is a universal random
generator for drawing samples efficiently from a univariate log-concave target
probability density function (pdf). ARS generates independent samples from the
target via rejection sampling with high acceptance rates. Indeed, ARS yields a
sequence of proposal functions that converge toward the target pdf, so that the
probability of accepting a sample approaches one. However, sampling from the
proposal pdf becomes more computational demanding each time it is updated. In
this work, we propose a novel ARS scheme, called Cheap Adaptive Rejection
Sampling (CARS), where the computational effort for drawing from the proposal
remains constant, decided in advance by the user. For generating a large number
of desired samples, CARS is faster than ARS.
