5
$\begingroup$

The Metropolis algorithm is an instance of the MCMC class of algorithms, with the purpose of sampling from a posterior distribution that may be intractable to manipulate analytically.

For the sake of keeping things simple, let's use the following example:

  • Suppose you want to find the posterior distribution over the bias $\theta$ of a coin, given a list of $n$ observations $X_i$.
  • We start with a uniform prior: $\theta \sim \mathsf{Uniform}(0,1)$, and consider the binomial likelihood: $X \mid \theta \sim \mathsf{Binomial}(n, \theta)$.
  • The posterior will be $p(\theta \mid X) = \dfrac{p(X\mid\theta) \cdot p(\theta)}{Z_p}$, where $Z_p=\int_0^1{p(X\mid\theta) \cdot p(\theta) d\theta}$

Let's assume that $Z_p$ is "intractable", so we will use the Metropolis algorithm to sample from the posterior.

First, we need a symmetric proposal distribution, that will give us a new potential sample to move to. First, is it true that this proposal distribution solely gives you a new sample, and is otherwise unrelated to the posterior?

Next, the acceptance probability of moving to a new sample $\theta^\star$ given the current sample $\theta_t$ is $$ \min\left(1, \ \dfrac{p(\theta^\star \mid X)}{p(\theta_t \mid X)}\right) = \min\left(1, \ \dfrac{p(X\mid\theta^\star)\cdot p(\theta^\star)}{p(X\mid\theta_t)\cdot p(\theta_t)}\right) $$ which can now be evaluated, since the likelihood and the prior are known, as chosen by the statistician. Essentially, this sample acceptance "trick" allows one to bypass the computation of the normalizing constant.

Is this summary of Metropolis algorithm correct?

$\endgroup$
3
  • 1
    $\begingroup$ Maybe a silly question, but if $\theta$ is the 'bias' of a presumably fair coin, shouldn't the prior be uniform from $-0.5, 0.5$? $\endgroup$
    – Alexis
    Nov 11, 2021 at 23:52
  • $\begingroup$ (Or does 'bias' just mean 'probability of heads'?) $\endgroup$
    – Alexis
    Nov 12, 2021 at 0:18
  • 1
    $\begingroup$ Here, "bias" is just the probability of heads, not an offset from 0.5. Sorry for the confusion. $\endgroup$ Nov 12, 2021 at 8:34

1 Answer 1

7
$\begingroup$

This is a correct description of the (symmetric) Metropolis-[Rosenbluth²]-Hastings algorithm, but the motivation is not:

(i) ignoring the normalising constant $Z_p$ is common to a lot of simulation techniques, like accept-reject methods. The normalising constant is useful when computing the cdf and using the inverse cdf technique, but otherwise, it rarely matters. The reasons for using MCMC methods are rather that the (e.g., posterior) distributions to be simulated are complex, high-dimension, non-standard distributions.

(ii) the posterior must be available analytically in the sense that $$p(\theta)p(x|\theta)$$ must be computable for the observed value $x$ and an arbitrary $\theta$, up to a constant (in $\theta$). Otherwise, the random variable $\theta$ must be completed by an auxiliary variable to augment $p(\theta|x)$ into a joint distribution $q(\theta,z|x)$ that can be computed or simulated (as in data augmentation).

$\endgroup$
4
  • 1
    $\begingroup$ Right, the motivation is one of the reasons I posted the question. I understand that the posterior may become very complex -- is this solely due to the choice of likelihood $\times$ prior? E.g. for certain problems, this pair of likelihood and prior leads to a complicated posterior, but separately, the likelihood and prior are "manageable", in the sense that their product can still be easily evaluated, so MCMC methods are applicable. Is this correct? $\endgroup$ Nov 11, 2021 at 11:47
  • 2
    $\begingroup$ Yes, having a fully computable product likelihood × prior does not mean simulating the distribution is directly feasible. $\endgroup$
    – Xi'an
    Nov 11, 2021 at 16:38
  • $\begingroup$ Thanks! Can you please point me towards some exercises / proofs where this is the case? $\endgroup$ Nov 11, 2021 at 17:07
  • 3
    $\begingroup$ All textbooks with a MCMC part (Albert, Gelman et al., McEalreath, Liu, &tc.) contain many examples, including ours. $\endgroup$
    – Xi'an
    Nov 11, 2021 at 17:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.