Abstract: We propose and analyze an algorithm to approximate distribution functions and densities of perpetuities. Our algorithm refines an earlier approach based on iterating discretized versions of the fixed point equation that defines the perpetuity. We significantly reduce the complexity of the earlier algorithm. Also one particular perpetuity arising in the analysis of the selection algorithm Quickselect is studied in more detail. Our approach works well for distribution functions. For densities we have weaker error bounds although computer experiments indicate that densities can also be approximated well.
Recommendations
Cites work
- scientific article; zbMATH DE number 3835125 (Why is no real title available?)
- scientific article; zbMATH DE number 1026574 (Why is no real title available?)
- scientific article; zbMATH DE number 1552325 (Why is no real title available?)
- A note on the approximation of perpetuities
- Analysis of quickselect : an algorithm for order statistics
- Density approximation and exact simulation of random variables that are solutions of fixed-point equations
- Limiting distributions of two random sequences
- Logarithmic combinatorial structures: A probabilistic approach
- On a stochastic difference equation and a representation of non–negative infinitely divisible random variables
- On distributional properties of perpetuities
- On the Asymptotic Distribution of Large Prime Factors
- Perfect simulation from the quicksort limit distribution
- Perpetuities with thin tails
- Quickselect and the Dickman Function
- Quicksort asymptotics
- Rates of convergence for products of random stochastic \(2\times 2\) matrices
- Simulating perpetuities
- Stability of perpetuities
- The limit behavior of an interval splitting scheme
Cited in
(10)- Perpetuities with thin tails revisited
- Selfdecomposability perpetuity laws and stopping times
- A note on the approximation of perpetuities
- Simulating perpetuities
- Central limit theorem for kernel estimator of invariant density in bifurcating Markov chains models
- Appendix to ``Approximating perpetuities
- Analysis of swaps in radix selection
- Perfect simulation of Vervaat perpetuities
- Approximations for the distribution of perpetuities with small discount rates
- Distributional analysis of swaps in quick select
This page was built for publication: Approximating perpetuities
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q398787)
