Appendix to "Approximating perpetuities"

Abstract

An algorithm for perfect simulation from the unique solution of the distributional fixed point equation $Y{=}_{d}UY+U(1-U)$ is constructed, where $Y$ and $U$ are independent and $U$ is uniformly distributed on $[0,1]$. This distribution comes up as a limit distribution in the probabilistic analysis of the Quickselect algorithm. Our simulation algorithm is based on coupling from the past with a multigamma coupler. It has four lines of code.

References in corpus (1)

• A mixture representation of πwith applications in Markov chain Monte Carlo and perfect sampling