Density approximation and exact simulation of random variables that are solutions of fixed-point equations (Q3149977)

When \({\mathcal L}(X)\) is the distribution of a random variable \(X\) that satisfies a distributional fixed-point equation of the form \(X \sim \sum_{r=1}^K A_rX^{(r)}+b\) where the symbol \(\sim\) denotes equality in distribution, \(X^{(1)}, \dots, X^{(K)}\), \((A_1, \dots, A_K, b)\) are independent with \({\mathcal L} (X^{(r)})= {\mathcal L}(X)\) for all \(r\) and given random variables \(A_1, \dots, A_k, b\), and \(K \geq 1\) is a fixed integer, \({\mathcal L}(X)\) or \(X\) is called a fixed point of the above equation. This paper is concerned with density approximation and exact simulation from a class of fixed points with \(K \geq 2\). First, the authors specify the type of fixed-point equation under consideration and give examples of limit laws of quicksort cost measures and internal path length of random search trees. They show that the fixed point has \(C^\infty\) density and that the density and all its derivatives are bounded, and then derive a dominating, integrable curve needed for the rejection method. A general rate of convergence for \(\mu_n \rightarrow X\) is derived, which depends on the accuracy of the approximation of the discretizations \(A_r^{(n)}\) and \(b^{(n)}\). The modified rejection algorithm for approximating the density is given with some considerations on computational complexity.