Density approximation and exact simulation of random variables that are solutions of fixed-point equations
Authors:
- 1 March 2002
- journal article
- general applied-probability
- Published by Cambridge University Press (CUP) in Advances in Applied Probability
- Vol. 34 (02) , 441-468
Abstract
An algorithm is developed for exact simulation from distributions that are defined as fixed points of maps between spaces of probability measures. The fixed points of the class of maps under consideration include examples of limit distributions of random variables studied in the probabilistic analysis of algorithms. Approximating sequences for the densities of the fixed points with explicit error bounds are constructed. The sampling algorithm relies on a modified rejection method.Keywords
This publication has 28 references indexed in Scilit:
- Approximating the limiting Quicksort distributionRandom Structures & Algorithms, 2001
- Stability of perpetuitiesThe Annals of Probability, 2000
- Perpetuities with thin tailsAdvances in Applied Probability, 1996
- Asymptotic distribution theory for Hoare's selection algorithmAdvances in Applied Probability, 1996
- Probability metrics and recursive algorithmsAdvances in Applied Probability, 1995
- Strict Stationarity of Generalized Autoregressive ProcessesThe Annals of Probability, 1992
- Limiting Distributions for Path Lengths in Recursive TreesProbability in the Engineering and Informational Sciences, 1991
- QuicksortThe Computer Journal, 1962
- Algorithm 64: QuicksortCommunications of the ACM, 1961
- On stochastic processes connected with certain physical recording apparatusesActa Mathematica Hungarica, 1955