Adaptive Rejection Sampling
For many distributions, finding a proposal distribution that includes the given distribution without a lot of wasted space is difficult. An extension of rejection sampling that can be used to overcome this difficulty and efficiently sample from a large number of distributions (provided that they are log-concave, which is in fact the case for most of the common distributions) is known as adaptive rejection sampling. The basic idea is to model the proposal distribution using a set of piecewise exponential distributions (i.e. segments of one or more exponential distributions, attached end to end). This can be easier visualized in log space (i.e. by looking at the logarithm of the distribution). The logarithm of an exponential distribution is a straight line, and hence this method essentially involves enclosing the logarithm of the density in a series of line segments. This is the source of the log-concave restriction: if a distribution is log-concave, then its logarithm is concave (shaped like an upside-down U), meaning that a line segment tangent to the curve will always pass over the curve. The method essentially involves successively determining an envelope of straight-line segments that approximates the logarithm better and better while still remaining above the curve, starting with a fixed number of segments (possibly just a single tangent line). Any time we choose a point that is rejected, we tighten the envelope with another line segment that is tangent to the curve at the point with the same x-coordinate as the chosen point.
Read more about this topic: Rejection Sampling
Famous quotes containing the words adaptive and/or rejection:
“The shift from the perception of the child as innocent to the perception of the child as competent has greatly increased the demands on contemporary children for maturity, for participating in competitive sports, for early academic achievement, and for protecting themselves against adults who might do them harm. While children might be able to cope with any one of those demands taken singly, taken together they often exceed children’s adaptive capacity.”
—David Elkind (20th century)
“As between these two, the need that in its haste to be abolished cannot pause to be stated and the need that is the absolute predicament of particular human identity, one does not presume to suggest a relation of worth. Yet the distinction is perhaps not idle, for it is from the failure to make it that proceeds the common rejection as “obscure” of most that is significant in modern music, painting and literature.”
—Samuel Beckett (1906–1989)