Основное правило марковской цепи: предложи шаг, прими его с вероятностью, заданной отношением апостериорных распределений.Алгоритм Метрополиса-Гастингса — это метод Монте-Карло на основе марковских цепей (MCMC) для выборки из распределения вероятностей, когда прямая выборка невозможна. Он является рабочей лошадкой байесовских вычислений, позволяя генерировать последовательность выборок, которые асимптотически следуют целевому апостериорному распределению, даже если нормировочная константа неизвестна. Это делает его незаменимым для оценки параметров и сравнения моделей в сложных многомерных задачах.
Алгоритм был предложен Николасом Метрополисом в 1953 году для частного случая и обобщён У. Китом Гастингсом в 1970 году. Он получил широкое распространение в физике и статистике в 1980-х и 1990-х годах с ростом вычислительных мощностей.
Начиная с начальной точки, алгоритм предлагает новую точку в соответствии с распределением-предложением. Затем он вычисляет отношение апостериорных плотностей в предлагаемой и текущей точках. Если отношение больше 1, предложение принимается; в противном случае оно принимается с вероятностью, равной этому отношению. Это правило принятия гарантирует, что цепь проводит больше времени в областях высокой вероятности, и за много шагов распределение посещённых точек сходится к целевому распределению. Распределение-предложение можно настраивать для баланса между исследованием и эффективностью.
Он используется в физике частиц для подгонки сложных моделей к данным, в космологии для исследования пространства параметров Вселенной, а также в финансах для оценки рисков и ценообразования опционов.
Алгоритм был первоначально разработан для вычисления уравнения состояния газа из твёрдых сфер, и его создатели использовали один из первых электронных компьютеров — MANIAC — в Лос-Аламосе.
