Извлечение из простого распределения и сохранение точек, попадающих под целевое.Метод отбора с отклонением — это простой метод Монте-Карло для генерации выборок из целевого распределения вероятностей, когда прямое сэмплирование затруднено. Он работает путём сэмплирования из более простого предложенного распределения, которое покрывает целевое распределение, а затем принятия или отклонения каждой выборки на основе случайного теста. Принятые выборки точно следуют целевому распределению. Это основополагающий алгоритм в вычислительной физике и статистике, часто используемый как строительный блок для более сложных методов, таких как марковские цепи Монте-Карло.
Метод был описан Джоном фон Нейманом в 1951 году в статье о различных техниках генерации случайных чисел, хотя похожие идеи появлялись и ранее в статистической литературе.
Задано целевое распределение p(x) и предложенное распределение q(x) такое, что p(x) ≤ M·q(x) для некоторой константы M. Вы извлекаете кандидата x из q(x) и равномерное случайное число u в [0,1]. Принимаете x, если u < p(x)/(M·q(x)), в противном случае отклоняете и пробуете снова. Принятые выборки распределены согласно p(x). Эффективность зависит от отношения площадей под p и M·q; если M слишком велико, многие выборки отклоняются, что приводит к потере вычислительных ресурсов. Метод работает лучше всего, когда q является хорошим приближением к p.
Используется в физике элементарных частиц для генерации случайных событий согласно сложным дифференциальным сечениям, а также в байесовской статистике для сэмплирования из апостериорных распределений, когда нормировочная константа неизвестна.
Метод отбора с отклонением также известен как «метод приём-отказ» и является ключевым ингредиентом знаменитого алгоритма Метрополиса-Хастингса, который обобщает его для решения задач высокой размерности.
