Appendix to ``Approximating perpetuities

DOI10.1007/S11009-012-9299-2zbMATH Open1368.60023arXiv1203.0679OpenAlexW2111102599MaRDI QIDQ370895FDOQ370895

Authors: Margarete Knape, Ralph Neininger 

Publication date: 20 September 2013

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

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.

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

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

zbMATH Keywords

quickselectperfect simulationcoupling from the pastkey exchangesmultigamma couplerperpetuity

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• The double CFTP method
• Quickselect and the Dickman Function
• A mixture representation of \(\pi\) with applications in Markov chain Monte Carlo and perfect sampling.
• Approximating perpetuities
• Exact Sampling from a Continuous State Space
• Simulating perpetuities
• Simulating the Dickman distribution
• Perfect simulation of Vervaat perpetuities

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)