Metropolis-Hastings(MH) 알고리즘은 복잡한 확률 분포에서 샘플을 추출하는 가장 단순한 MCMC 알고리즘이다. 이것은 target 분포에서 직접 샘플링 하기가 어려울 때, 샘플링하고자 하는 분포를 근사하는 Markov Chain을 구성하고 이 체인을 통해 분포의 샘플을 생성한다.
MH는 각 단계에서 현재 상태 $\bold{x}$에서 새로운 상태 $\bold{x}'$로 $q(\bold{x}'|\bold{x})$의 확률로 움직이는 것을 제안한다. 여기서 $q$는 proposal 분포(또는 kernel이라고도 함)라 하고 일반적으로 가우시안 같은 간단한 분포를 사용한다.
$\bold{x}'$로 이동을 제안 받으면 각 상태에서 소모된 시간의 장기 비율이 목표 분포 $p^*(\bold{x})$에 비례 하도록 보장하는 어떤 공식에 따라 이 제안을 수락할지 거절할지 결정한다. 제안이 수락되면 새로운 상태는 $\bold{x}'$이고 그렇지 않으면 현재 상태 $\bold{x}$에서 샘플링을 반복한다.
제안이 대칭 $q(\bold{x}'|\bold{x}) = q(\bold{x}|\bold{x}')$인 경우, 수락 확률은 다음 공식에 의해 주어진다.
$$ A = \min\left(1, {p^(\bold{x}') \over p^(\bold{x})} \right) $$
$\bold{x}'$이 $\bold{x}$보다 더 가능성이 높으면 ${p^(\bold{x}') \over p^(\bold{x})} > 1$이므로 분명히 거기로 이동한다. 그러나 $\bold{x}'$가 가능성이 낮더라도 상대적인 확률에 의존하여 어쨌든 그곳으로 이동할 수 있다. 따라서 가능성이 더 높은 상태로만 탐욕적으로 이동하는 대신 가끔 가능성이 낮은 상태로 ‘내리막(downhill)’ 이동을 허용한다.
제안이 비대칭 $q(\bold{x}'|\bold{x}) \ne q(\bold{x}|\bold{x}')$인 경우, 수락 확률은 다음과 같이 주어진다. 이것을 Hastings correction이라 한다.
$$ \begin{aligned} A &= \min(1,\alpha) \\ \alpha &= {p^(\bold{x}')q(\bold{x}|\bold{x}') \over p^(\bold{x})q(\bold{x}'|\bold{x})}={p^(\bold{x}')/q(\bold{x}'|\bold{x}) \over p^(\bold{x}) / q(\bold{x}|\bold{x}')} \end{aligned} $$
MH가 유용한 이유는 타겟 분포의 정규화 상수를 모르더라도 샘플링이 가능하기 때문이다. 예컨대 타겟 분포를 unnormalized $\tilde{p}(\bold{x})$와 정규화 상수 $Z$를 이용하여 $p^*(\bold{x}) = {1\over Z}\tilde{p}(\bold{x})$라 하면 위의 식을 다음처럼 작성할 수 있다.
$$ \alpha = {(\tilde{p}(\bold{x}') /Z)q(\bold{x}|\bold{x}') \over (\tilde{p}(\bold{x})/Z) q(\bold{x}'|\bold{x})} $$
여기서 분모와 분자의 정규화 상수 $Z$는 상쇄되므로 $Z$를 모르더라도 $p^*$에서 샘플링 할 수 있다.
제안 분포 $q$가 타겟의 지지(support)를 커버하면 유효하거나 인정된다. 형식적으로 이것을 다음처럼 작성할 수 있다.
$$ \text{supp}(p^*) \sube \cup_x \text{supp}(q(\cdot|x)) $$