Efficient random generation from truncated Laplace distribution

Question

We have several ways of drawing random samples from Laplace distribution. Is there any efficient way of sampling from left truncated Laplace distribution? Inverse transform sampling is an obvious solution, but maybe there is something better?

Answer 1

A straightforward method that is reasonably efficient if the left truncation point is below the median is to just generate a Laplace random variate, then reject it if it falls to the left of the truncation point and generate another, repeating until one is generated that falls above the truncation point. If the Laplace random variate generation algorithm requires $n$ uniform variate generations on average for one Laplace variate generation, the truncated Laplace algorithm requires $n/(1-F(\alpha))$ uniform variate generations on average, where $\alpha$ is the truncation point, and therefore never requires more (on average) than twice the uniform variate generations as the original algorithm regardless of the truncation point - and if the truncation point is well into the lower tail, e.g., at the 10th percentile of the distribution, is almost as efficient as the original algorithm.

If the left truncation point is above the median, then you have an exponential distribution for the sampling distribution with lower bound equal to the truncation point, so plenty of efficient algorithms there.

Another approach, useful if your Laplace random variate generation algorithm uses inverse transform sampling, is to shift and rescale the initial $\text{U}(0,1)$ variate to fall into the range $U(\alpha,1)$, where $\alpha$ is the percentile of the Laplace distribution where the left truncation occurs, then just use the inverse transform as usual, without regard for truncation. The resulting algorithm requires one addition and multiplication more than the original, so is essentially just as efficient as the inverse transform method for the un-truncated distribution.

Answer 2

If you need extreme efficiency and don't mind increased code complexity, you could adapt this ziggurat-like rejection sampling technique to the standard laplace distribution directly and use shifts and scaling to produce distributions with arbitrary parameters.