Введение
Метод вычислительной статистики
В численном анализе и вычислительной статистике метод отбраковки (или метод принятия-отбраковки, "алгоритм принятия-отбраковки") является базовым методом, используемым для генерации случайных выборок из распределения. Это тип точного метода моделирования. Метод применим к любому распределению с функцией плотности. Метод отбраковки основан на том, что для выборки случайной величины в одномерном пространстве можно выполнить равномерную случайную выборку на двумерной декартовой плоскости и сохранять только те выборки, которые попадают под график функции плотности. Следует отметить, что это свойство можно обобщить на функции от N переменных.
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.
Недостатки
Для отбора проб с отклонением требуется знание целевого распределения (в частности, возможность вычислять значение функции плотности вероятности в любой точке). Отбор проб с отклонением может приводить к генерации большого количества нежелательных образцов, если функция, из которой производится выборка, сильно сконцентрирована в определенной области, например, если у функции есть резкий пик в некоторой точке. Для многих распределений эту проблему можно решить, используя адаптивное расширение (см. адаптивный отбор проб с отклонением) или подходящее изменение переменных с помощью метода отношения равномерных распределений. Кроме того, с увеличением размерности задачи отношение объема вложенной области к "углам" этой области стремится к нулю, что приводит к большому количеству отклонений до получения полезного образца, делая алгоритм неэффективным и непрактичным. См. проклятие размерности. В задачах высокой размерности необходимо использовать другой подход, как правило, метод Монте-Карло на цепях Маркова, такой как метод Метрополиса или метод Гиббса. (Однако, при выборке Гиббса, которая разбивает многомерную задачу выборки на последовательность низкоразмерных выборок, отбор проб с отклонением может использоваться на одном из этапов.)