Editing Rejection sampling (section)

==Description==
To visualize the motivation behind rejection sampling, imagine graphing the [[probability density function]] (PDF) of a random variable onto a large rectangular board and throwing darts at it. Assume that the darts are uniformly distributed around the board. Now remove all of the darts that are outside the area under the curve.  The remaining darts will be distributed uniformly within the area under the curve, and the <math>x</math>‑positions of these darts will be distributed according to the random variable's density. This is because there is the most room for the darts to land where the curve is highest and thus the probability density is greatest.

The visualization just described is equivalent to a particular form of rejection sampling where the "proposal distribution" is uniform. Hence its graph is a rectangle.  The general form of rejection sampling assumes that the board is not necessarily rectangular but is shaped according to the density of some proposal distribution (not necessarily normalized to <math>1</math>) that we know how to sample from (for example, using [[inversion sampling]]). Its shape must be at least as high at every point as the distribution we want to sample from, so that the former completely encloses the latter. Otherwise, there would be parts of the curved area we want to sample from that could never be reached.

Rejection sampling works as follows:

#Sample a point on the <math>x</math>‑axis from the proposal distribution.
#Draw a vertical line at this <math>x</math>‑position, up to the y-value of the probability density function of the proposal distribution.
#Sample uniformly along this line. If the sampled value is greater than the value of the desired distribution at this vertical line, reject the <math>x</math>‑value and return to step 1; else the <math>x</math>‑value is a sample from the desired distribution.

This algorithm can be used to sample from the area under any curve, regardless of whether the function integrates to 1.  In fact, scaling a function by a constant has no effect on the sampled {{nobr|<math>x</math>‑positions}}.  Thus, the algorithm can be used to sample from a distribution whose [[normalizing constant]] is unknown, which is common in [[computational statistics]].