Appendix to ``Approximating perpetuities

DOI10.1007/S11009-012-9299-2MaRDI QIDQ370895zbMATH OpenOpenAlexFDO

Authors Margarete Knape, Ralph Neininger

Publication date 20 September 2013

Published in Methodology and Computing in Applied Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1203.0679

zbMATH Keywords

quickselectperfect simulationcoupling from the pastkey exchangesmultigamma couplerperpetuity

Mathematics Subject Classification ID

Random number generation in numerical analysis (65C10) Distribution theory (60E99)

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.

Recommendations

• A note on the approximation of perpetuities
• Approximating perpetuities
• Perfect simulation of Vervaat perpetuities
• Perfect simulation from the quicksort limit distribution
• Fast perfect simulation of Vervaat perpetuities

Cites work

• scientific article; zbMATH DE number 3954145 (Why is no real title available?)
• A mixture representation of \(\pi\) with applications in Markov chain Monte Carlo and perfect sampling.
• Approximating perpetuities
• Exact Sampling from a Continuous State Space
• Perfect simulation of Vervaat perpetuities
• Quickselect and the Dickman Function
• Simulating perpetuities
• Simulating the Dickman distribution
• The double CFTP method

Cited in

(5)

• Fast perfect simulation of Vervaat perpetuities
• A note on the approximation of perpetuities
• Density approximation and exact simulation of random variables that are solutions of fixed-point equations
• Approximating perpetuities
• Perfect simulation of Vervaat perpetuities

This page was built for publication: Appendix to ``Approximating perpetuities

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q370895)