How does the Metropolis Algorithm work? (for idiots)

Question

I have the mathematical skills of a house brick and I am desperately trying to learn this algorithm from a computer science perspective.

Below is my knowledge of the algorithm. Can someone please tell me where I am going wrong without using maths lingo!?

What does the Metropolis Algorithm Do?

Let's say I have a 3x3 grid labelled 1 - 9. I can transition horizontally and vertically only. I want the chance of transitioning from node a to node b to be the same as transitioning from node b to node a given n steps where n is a big old integer. The Metropolis algorithm will tell me what the transition percentages should be between each node.

How do I do it?

There's a magic rule that says that the chance of going from a to b is the same as the chance of being in a divided by the chance of being in b. This can described as:

P(a->b) = min[1, π(b)/π(a)]

Where:

• P means "the probability of"
• -> means "transitioning to"
• min means "minimum of"
• π means "being in node(blah)"

I want the chance of being in any node when starting from any node to be the same. I have 9 nodes. Therefore the probability of being in any node should be 1/9.

Plugging this into the algorithm...

P(a->b) = min[1, (1/9)/(1/9)]

That means P(a->b) = 1. That is impossible as there is the chance of staying still + transitioning to nodes c, d, etc to consider. The Probability of anything cannot exceed 1 as nothing is more likely than certainty.

Help?! :(

Answer 1

This answer is aimed at non-mathematicians and is intentionally put in Layman's terms...

The Metropolis Algorithm

The Metropolis algorithm will move across a Markov-chain using known values about the probability of being in a certain kind of state. It CAN be used to simulate (and therefore demonstrate) an even distribution across a fixed or infinite number of nodes. It has 3 distinct steps:

1. The Proposal
2. The Acceptance/Rejection
3. The Transition

This is based on a formula that calculates Acceptance/Rejection which is:

$P(a->b) = min[1, π(b)/π(a)]$

Translated into English, this means:

The probability of transitioning from Node a to Node b is the same as the smaller of either certainty or the chance of being in node b divided by the chance of being in node a.

We need the "the smaller of either..." bit as a probability cannot exceed 1 or Maths will explode.

The Scenario

Imagine you are magically deposited in the middle of a desert island. You want to move around and explore but also need to drink from the springs that you are surrounded by. You have a map of the island in your pocket. The world here moves in discrete time - i.e. chunks of 1 hour. No other unit of time is possible and this unit is atomic.

Example 1

For now, assume that the springs have no animals in them and there are no barriers to drinking from them. The springs on your map are arranged in a 3 x 3 grid and you are currently standing next to spring 5 - the middle spring/cell.

3 x 3 Grid

Step 1 - The Proposal:

You pick a spring at random - let's say spring 5. You choose another spring at random - say spring 2. Our proposal in Maths language looks like this:

• $π(i)$ = The chance of being in node $i$ where $i$ in this case refers to an index of a spring.

In our case, $π(2)$

Therefore our proposal is:

$P(spring5->spring2)$

Or put simply

$P(5->2)$

Step 2 - The Acceptance/Rejection

We can use the Metropolis acceptance/rejection formula to calculate your success of moving between the two springs. We need to know what $P$ means:

$P(5->2)$ <- "I want to navigate from spring 5 to spring 2. What is the probability of me getting there successfully?"

Therefore:

$P(a->b) = min[1, π(b)/π(a)]$

Or to put it another way:

$P(2->5) = min[1, π(2)/π(5)]$

Now all we need to know is what $min$ means.

• $min$ = The minimum of 2 arguments. In the case take the smallest answer from $1$ or $π(b)/π(a)$.

We know what the $π(i)$ for every spring is. It's $1/9$. We have 9 springs. They are not distinct and there aren't any barriers. We could be in any 1 of them if we wandered around aimlessly for a gazillion hours. As we know $π(i)$, we can fill in the rest of the equation.

$P(2->5) = min[1, (1/9)/(1/9)]$

This resolves to:

$P(2->5) = min[1, 1/1] = min[1, 1] = 1$

This means that it is CERTAIN that if we choose a spring, we will get there unimpeded. This means ACCEPT.

Step 3 - The Transition:

We just have to update $π$.

$π(2)$

Success!

Example 2

Exactly the same as before but we are near to the ocean (in an "edge" node) and we want to know the chance of going into the sea by mistake (outside of the grid). Let's call the sea $x$.

Step 1 - The Proposal:

$P(2->x)$

Step 2 - The Acceptance/Rejection:

Everyone knows that the sea doesn't contain fresh water. You would never, ever make this mistake. Therefore the probability of making this transition is 0.

$P(2->x) = min[1, 0/(1/9)] = min[1, 0] = 0$

This means REJECT.

Step 3 - The Transition:

The transition proposal failed. There was no transition. You did not move into the sea and drown. Good for you! You stayed put.

$π(2)$

Example 3

The springs are no longer in a 9x9 grid but an infinite grid. There is no advantage to the springs being in a grid or using a finite grid. The maths for this works exactly the same if the grid is infinite. Instead of a having 9 springs, we can say that $1/9th$ springs are of type $a$, another $1/9th$ of our springs are of type b, etc. Here are the 3 steps.

Step 1 - The Proposal:

$P(a->b)$

Step 2 - The Acceptance/Rejection:

$P(a->b) = min[1, (1/9)∞/(1/9)∞] = min[1, 1] = 1$

Step 3 - The Transition:

$π(b)$

Example 4

Let's go back to the 9 springs arranged in a grid. 4 of the springs now have Orange Juice and 5 of the springs have Vodka. We label the ones that have Orange juice as $y$ and the ones with vodka as $z$. We are currently at a Vodka and now, utterly inebriated, we want some orange juice. We don't care which spring it is - as long as it has orange juice. Being totally drunk as we are, we don't even know which spring we're in. Thankfully, that doesn't matter. So, we just have to pick a direction at random. What we want to know is the answer to the following question:

"Given that I am in a spring of vodka, what is the chance of successfully going to a spring of orange juice if I walk to a random spring?"

Step 1 - The Proposal:

$P(z->y)$

Step 2 - The Acceptance/Rejection:

$P(z->y) = min[1, (4/9)/(5/9)] = min[1, 0.8] = 0.8$

Step 3 - The Transition:

This part isn't so Black and White any more. We have an 80% chance of transition ACCEPTANCE.

• $P(π(y))$ = 80%
• $P(π(z))$ = 20%

This implies there are 2 things that could happen:

• We could successfully move from a Vodka spring to an Orange spring with 80% probability
• We could fail to transition (pass out, walk into a tree, etc) with 20% probability. This means we do NOT transition and remain in $π(z)$.

So to answer the question "What is the chance of going from a Vodka Spring to an Orange Spring":

$5/9 * 4/5 = 44$%

ChanceOfChoosingAOrangeSpring * ChanceOfSuccessfulTransition = ChanceOfTransitioningToOrangeSpring

How we actually compute this is irrelevant (dice roll, random number, etc). Also, note that if we go from Orange to Vodka, we are not drunk and therefore the transition probability is 1 (Certain).