Қолдану-жобалау сандық статистика әдісі

Computational statistics technique
In numerical analysis and computational statistics, rejection sampling is a basic technique used to generate observations from a distribution. It is also commonly called the acceptance rejection method or "accept reject algorithm" and is a type of exact simulation method. The method works for any distribution in with a density. Rejection sampling is based on the observation that to sample a random variable in one dimension, one can perform a uniformly random sampling of the two dimensional Cartesian graph, and keep the samples in the region under the graph of its density function. Note that this property can be extended to N dimension functions.

Rejection sampling requires knowing the target distribution (specifically, ability to evaluate target PDF at any point). Rejection sampling can lead to a lot of unwanted samples being taken if the function being sampled is highly concentrated in a certain region, for example a function that has a spike at some location. For many distributions, this problem can be solved using an adaptive extension (see adaptive rejection sampling), or with an appropriate change of variables with the method of the ratio of uniforms. In addition, as the dimensions of the problem get larger, the ratio of the embedded volume to the "corners" of the embedding volume tends towards zero, thus a lot of rejections can take place before a useful sample is generated, thus making the algorithm inefficient and impractical. See curse of dimensionality. In high dimensions, it is necessary to use a different approach, typically a Markov chain Monte Carlo method such as Metropolis sampling or Gibbs sampling. (However, Gibbs sampling, which breaks down a multi dimensional sampling problem into a series of low dimensional samples, may use rejection sampling as one of its steps.)