REJECTION_SAMPLE
Acceptance/rejection sampling


REJECTION_SAMPLE is a MATLAB library which demonstrates acceptance/rejection sampling.

We suppose that for A <= X <= B, we are given a probability density function PDF(X), and wish to randomly sample X. If it is not feasible to compute the cumulative density function CDF(X) and invert it to X(CDF), then acceptance/rejection sampling can provide an alternate way of carrying out the sampling.

Briefly, a comparison curve Z(X) must be determined, such that PDF(X) <= Z(X) for all A <= X <= B, and with the property that data can be uniformly sampled under the Z curve.

If that is the case, then we uniformly sample an X value under the Z curve. Then we pick an R value uniformly between 0 and Z(X). We accept X if R <= PDF(X); otherwise, we reject this X and prepare to generate and test another value.

Licensing:

The computer code and data files described and made available on this web page are distributed under the GNU LGPL license.

Languages:

REJECTION_SAMPLE is available in a Matlab version.

Related Data and Programs:

HISTOGRAM_DATA_2D_SAMPLE, a MATLAB program which demonstrates how to construct a Probability Density Function (PDF) from a frequency table over a 2D domain, and then to use that PDF to create new samples.

HISTOGRAM_PDF_SAMPLE, a MATLAB library which demonstrates how sampling can be done by starting with the formula for a PDF, creating a histogram, constructing a histogram for the CDF, and then sampling.

HISTOGRAM_PDF_2D_SAMPLE, a MATLAB library which demonstrates how uniform sampling of a 2D region with respect to some known Probability Density Function (PDF) can be approximated by decomposing the region into rectangles, approximating the PDF by a piecewise constant function, constructing a histogram for the CDF, and then sampling.

PDFLIB, a MATLAB library which evaluates Probability Density Functions (PDF's) and produces random samples from them, including beta, binomial, chi, exponential, gamma, inverse chi, inverse gamma, multinomial, normal, scaled inverse chi, and uniform.

PROB, a MATLAB library which evaluates, samples, inverts, and characterizes a number of Probability Density Functions (PDF's) and Cumulative Density Functions (CDF's), including anglit, arcsin, benford, birthday, bernoulli, beta_binomial, beta, binomial, bradford, burr, cardiod, cauchy, chi, chi squared, circular, cosine, deranged, dipole, dirichlet mixture, discrete, empirical, english sentence and word length, error, exponential, extreme values, f, fisk, folded normal, frechet, gamma, generalized logistic, geometric, gompertz, gumbel, half normal, hypergeometric, inverse gaussian, laplace, levy, logistic, log normal, log series, log uniform, lorentz, maxwell, multinomial, nakagami, negative binomial, normal, pareto, planck, poisson, power, quasigeometric, rayleigh, reciprocal, runs, sech, semicircular, student t, triangle, uniform, von mises, weibull, zipf.

RANLIB, a MATLAB library which produces random samples from Probability Density Functions (PDF's), including Beta, Chi-square Exponential, F, Gamma, Multivariate normal, Noncentral chi-square, Noncentral F, Univariate normal, random permutations, Real uniform, Binomial, Negative Binomial, Multinomial, Poisson and Integer uniform, by Barry Brown and James Lovato.

WALKER_SAMPLE, a MATLAB library which efficiently samples a discrete probability vector using Walker sampling.

Source Code:

Examples and Tests:

You can go up one level to the MATLAB source codes.


Last revised on 09 August 2016.