The acceptance-rejection method for low-discrepancy sequences
From MaRDI portal
Abstract: Generation of pseudorandom numbers from different probability distributions has been studied extensively in the Monte Carlo simulation literature. Two standard generation techniques are the acceptance-rejection and inverse transformation methods. An alternative approach to Monte Carlo simulation is the quasi-Monte Carlo method, which uses low-discrepancy sequences, instead of pseudorandom numbers, in simulation. Low-discrepancy sequences from different distributions can be obtained by the inverse transformation method, just like for pseudorandom numbers. In this paper, we will present an acceptance-rejection algorithm for low-discrepancy sequences. We will prove a convergence result, and present error bounds. We will then use this acceptance-rejection algorithm to develop quasi-Monte Carlo versions of some well known algorithms to generate beta and gamma distributions, and investigate the efficiency of these algorithms numerically. We will also consider the simulation of the variance gamma model, a model used in computational finance, where the generation of these probability distributions are needed. Our results show that the acceptance-rejection technique can result in significant improvements in computing time over the inverse transformation method in the context of low-discrepancy sequences.
Recommendations
- Generation of non-uniform low-discrepancy sequences in quasi-Monte Carlo integration
- Generating low-discrepancy sequences from the normal distribution: Box-Muller or inverse transform?
- On the use of low discrepancy sequences in Monte Carlo methods
- Quasi-Random Sequences and Their Discrepancies
- Low-discrepancy simulation
Cites work
- scientific article; zbMATH DE number 3954145 (Why is no real title available?)
- scientific article; zbMATH DE number 3962966 (Why is no real title available?)
- scientific article; zbMATH DE number 53679 (Why is no real title available?)
- Algorithm AS 147: A Simple Series for the Incomplete Gamma Integral
- Algorithm AS 245: A Robust and Reliable Algorithm for the Logarithm of the Gamma Function
- Beiträge zur Diskrepanz bezüglich gewichteter Mittel. (Contributions to the discrepancy with respect to weighted means)
- Discrepancy bounds for deterministic acceptance-rejection samplers
- Error bounds for quasi-Monte Carlo integration with uniform point sets
- Error reduction techniques in quasi-Monte Carlo integration.
- Generalized von Neumann-Kakutani transformation and random-start scrambled Halton sequences
- Generating low-discrepancy sequences from the normal distribution: Box-Muller or inverse transform?
- Improving the rejection sampling method in quasi-Monte Carlo methods
- Mersenne twister
- Multidimensional variation for quasi-Monte Carlo
- Randomized Halton sequences
- Smoothness and dimension reduction in quasi-Monte Carlo methods
- The Variance Gamma Process and Option Pricing
- Uniform point sets and the collision test
- Variance-gamma and Monte Carlo
- When are quasi-Monte Carlo algorithms efficient for high dimensional integrals?
Cited in
(8)- A quasi-Monte Carlo implementation of the ziggurat method
- Discrepancy estimates for acceptance-rejection samplers using stratified inputs
- Discrepancy bounds for deterministic acceptance-rejection samplers
- Unisolvence of random Kansa collocation by thin-plate splines for the Poisson equation
- scientific article; zbMATH DE number 5006055 (Why is no real title available?)
- A goodness-of-fit test for copulas based on the collision test
- Generating low-discrepancy sequences from the normal distribution: Box-Muller or inverse transform?
- A discrepancy bound for deterministic acceptance-rejection samplers beyond \(N^{-1/2}\) in dimension 1
This page was built for publication: The acceptance-rejection method for low-discrepancy sequences
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q293509)
