Sample-based non-uniform random variate generation

By Luc Devroye. 1986

A sample of n lid random variables with a given unknown density is given. We discuss several issues related to the problem or generating a new sample of lid random variables with almost the same density. In particular, we look at sample independence, consistency, sample indistinguishability, moment matching and generator efficiency. We also introduce the notion of a replacement number, the minimum number of observations in a given sample that have to be replaced to obtain a sample with a given density.

Subfields: Probabilistic & Bayesian Methods

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Probabilistic & Bayesian Methods

Citations in the corpus

Auto-Encoding Variational Bayes (2013, neutral): “In this case, let (cid:15) ∼ U ( 0 , I ) , and let g φ ( (cid:15) , x ) be the inverse CDF of q φ ( z | x When all three approaches fail, good approximations to the inverse CDF exist requiring computations with time complexity comparable to the PDF (see e.g. [Dev86] for some methods).”
Density estimation using Real NVP (2016, methodology): “Exact samples from the resulting distribution can be generated by using the inverse transform sampling rule [16].”
Tutorial on Variational Autoencoders (2016, methodology): “ distribution for a single dimension, and repeat with the conditional distribution of each additional dimension. See the “inversion method” and the “conditional distribution method” in Devroye et al. [15] 6 mize the model using stochastic gradient ascent. It is actually conceptually straightforward ”
Looking for the Devil in the Details: Learning Trilinear Attention Sampling Network for Fine-Grained Image Recognition (2019, methodology): “Inspired by the inverse-transform [6], we implement the sampling by calculating the inverse function of the distribution function.”
Large-Scale Heterogeneous Feature Embedding (2019, methodology): “Then the time complexity of sampling a neighbor from si would become O(N) (Devroye 1986), which is expensive.”
Random Number Generation (2008, methodology): “Several special cases and refinements are described in Devroye (1986), Gentle (2003), Leydold (2000), and other references given there.”
Optimizing Ad Allocation in Social Advertising (2015, methodology): “05, via the inverse transform sampling technique [32] on the samples randomly taken from uniform distribution U(0, 1).”
PROBABILISTIC FORECASTING OF THE MASSES AND RADII OF OTHER WORLDS (2016, background): “By directly walking in the prior probability space with a Gaussian function as our proposal distribution, inverse sampling is more efficient than walking in real space plus likelihood penalization (see Devroye 1986 for further details on the inverse sampling method).”