# Efficient random generation from truncated Laplace distribution

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?

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.

• I was considering the same approaches, I guess I was over-thinking this by looking for something more fancy. Thanks for detailed answer!
– Tim
Jul 17 '18 at 21:57
• Given that the CDF is available, inverting the CDF into$$F^{-1}(p) = \mu - b\,\text{sgn}(p-1/2)\,\ln(1 - 2|p-1/2|)$$ with the nice trick of simulating $U(\alpha,1)$ is hard to beat. Jul 18 '18 at 4:50

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.

• True, but it doesn't answer the question, which was not "how do I generate exponential random variates efficiently?" or even "how do I generate Laplace variates efficiently?" Jul 17 '18 at 17:51
• You're right. I realized that you don't need to simulate exponential variates first but that the algorithm can be adapted to the laplace directly as a location-scale family. Jul 17 '18 at 19:13
• I personally like ziggurat generators, as my simulations are usually for simulation-based optimization and involve lots of random number generation, hundreds of times more than what a single run of the simulator might require, and 80+% of the runtime can be random number generation if you're just using off-the-shelf stuff. +1 for the suggestion! Jul 17 '18 at 19:23