Fast inverse transform sampling in one and two dimensions

2013/07/04 by Sheehan Olver, Alex Townsend, Olver, Sheehan +1 · 1 citation
Computer Science · Engineering · #65C10 #Anomaly Detection Techniques and Applications #Chaos-based Image/Signal Encryption #FOS: Mathematics #Numerical Analysis (math.NA) #Probability (math.PR) #Sparse and Compressive Sensing Techniques #Statistics Theory (math.ST)

paper · pdf · doi:10.48550/arxiv.1307.1223

openalex publication_date 2013/07/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We develop a computationally efficient and robust algorithm for generating pseudo-random samples from a broad class of smooth probability distributions in one and two dimensions. The algorithm is based on inverse transform sampling with a polynomial approximation scheme using Chebyshev polynomials, Chebyshev grids, and low rank function approximation. Numerical experiments demonstrate that our algorithm outperforms existing approaches.

Citations

• A method for numerical integration on an automatic computer
• A note on the summation of Chebyshev series

Cited by

• FlexiWalker: Extensible GPU Framework for Efficient Dynamic Random Walks with Runtime Adaptation

Related

• Generating Generalized Inverse Gaussian Random Variates by Fast Inversion
• A Sparse Fast Chebyshev Transform for High-Dimensional Approximation
• Continuous Random Variate Generation by Fast Numerical Inversion
• Random Variate Generation by Numerical Inversion When Only the Density Is Known
• Random Variate Generation by Numerical Inversion When Only the Density Is Known