Question about Metropolis Hastings algorithm

[pamparana]

Hello everyone,

I am having a bit of trouble understanding the metropolis hastings algorithm which can be used to generate random samples from a distribution that can be difficult to sample directly from:

As I understand it we sample from a proposal distribution (say a normal distribution).

Now, to construct the Markov chain, I sample from this proposal distribution and accept or reject the sample based on the the equation shown http://upload.wikimedia.org/math/3/4/e/34e36a79ed058565327282b6cff8f214.png"

Now, in this equation the first ratio p(x(t))/p(x'). Where is this coming from? It seems that these are the terms from the distribution that we want to directly sample from!? or are they not?

I understand that somehow this will set the Markov chain in a way that the transition probabilities will reflect the desired distribution but I am not sure what this term is how can it be easily calculated.

I would be very grateful for any help you can give me.

Many thanks,

Luca

 

[mmwave]

Hello Luca,

I can understand your confusion about the metropolis hastings algorithm. Let me try to break it down for you.

First, let's start with the goal of the algorithm - to generate random samples from a distribution that is difficult to sample from directly. This is often the case with complex distributions in statistics, where it may not be possible to find an analytical solution for sampling.

To do this, we use a proposal distribution, which is a distribution that is easy to sample from. This is where the normal distribution comes in - it is a commonly used proposal distribution because it is easy to sample from and can approximate many other distributions.

Now, let's look at the equation you mentioned: http://upload.wikimedia.org/math/3/4/e/34e36a79ed058565327282b6cff8f214.png" . The first ratio, p(x(t))/p(x'), is the ratio of the probability of the current state (x(t)) to the probability of the proposed state (x'). This is where the desired distribution comes in - p(x(t)) and p(x') are the terms from the distribution we want to sample from.

The second ratio, q(x(t)/x'), is the ratio of the probability of proposing the current state (x(t)) from the proposed state (x'). This is where the proposal distribution comes in - q(x(t)/x') is the probability of sampling x(t) from the proposal distribution given that the proposed state is x'.

Now, the goal of the algorithm is to set up the Markov chain in a way that the transition probabilities reflect the desired distribution. This is done by accepting or rejecting the proposed state based on the ratio of these two probabilities. If the ratio is greater than 1, the proposed state is always accepted. If the ratio is less than 1, the proposed state is accepted with a probability equal to the ratio.

In summary, the first ratio in the equation represents the desired distribution, while the second ratio represents the proposal distribution. By balancing these two ratios, the algorithm is able to generate random samples from the desired distribution.

I hope this helps clarify the metropolis hastings algorithm for you. If you have any further questions, please don't hesitate to ask.