Metropolis Chain |

Nikolaos Metropolis

Nicholas Metropolis, a Greek American physicist, is well known for the “Metropolis chains”. It is a well known fact in Markov chain theory that for an irreducible matrix $P$ there is a unique stationary distribution $\pi$ satisfying $\pi P = \pi$ . A natural question which comes up is the following:

Given a probability distribution $\pi$ on a state space $\Omega$ , can we construct a transition matrix for which $\pi$ is its stationary distribution?

The method for sampling from a given probability distribution is called Markov Chain Monte Carlo (In my opinion, this fact by itself is elegant, but not too surprising. The most interesting question is how fast do you converge, but I will elaborate on this in a follow up post.). The main idea behind Markov Chain Monte Carlo is censorship. Let’s start for simplicity by considering a symmetric transition matrix $\Delta$ , that is $\Delta(x,y)=\Delta(y,x)$ . We will create a chain that will censor moves with some probability. Assume for example that we are in state $x$ . We will sample the next state $y$ using $\Delta(x,:)$ but we will accept the new state with probability $\alpha(x,y)$ . Therefore, we end up having the following transition matrix: $P(x,y)= \Delta(x,y) \alpha(x,y)$ if $x \neq y$ and $P(x,x) = 1 - \sum_{y \neq x} \Delta(x,y)\alpha(x,y)$ . The goal thus has become to pick a matrix $\alpha$ such that the matrix $P$ has stationary distribution the distribution we want to sample from. Now we will use the following proposition, which is the crucial argument we will use to pick the $\alpha$ matrix:

Proposition: Assume that we have a probability distribution $\pi$ on $\Omega$ which satisfies the detailed balance equations, i.e., $\pi(x) Q(x,y) = \pi(y) Q(y,x)$ for all pairs $x,y$ , where $Q$ is a transition matrix. Then, any $\pi$ which satisfies this set of equations is stationary for $Q$ .

Proof: Recall the definition of a stationary distribution for a transition matrix $Q$ , i.e., $\pi Q = \pi$ or equivalently $\pi(x) = \sum_y \pi(y) Q(y,x)$ . But from the detailed balance equation we can substitute the terms of the sum and obtain the following tautology: $\pi(x) = \sum_y \pi(y) Q(y,x) = \sum_y \pi(x) Q(x,y) = \pi(x) \sum_y Q(x,y) = \pi(x) \dot 1$ .

Now that we know the above, we can pick the $\alpha$ matrix so that we obtain the desired probability distribution. Specifically, it suffices to find an $\alpha$ matrix such that for every pair of states $x,y$ the detailed balance equations for the censored MC are satisfied. $\pi(x) \Delta(x,y) \alpha(x,y) = \pi(y) \Delta(y,x) \alpha(y,x)$ . Since we started out with a symmetric matrix, we obtain $\pi(x) \alpha(x,y) = \pi(y) \alpha(y,x)$ . Since the entries of the $\alpha$ matrix are probabilities, we have the constraints $\pi(x) \alpha(x,y) \leq \pi(x)$ and $\pi(y) \alpha(y,x) \leq \pi(y)$ . A choice which wastes as much as little moves and satisfies the above equations and constraints is to pick $\alpha(x,y) = \min{( \frac{\pi(y)}{\pi(x)},1})$ . This results in the transition matrix $P$ that we wanted from the beginning. Clearly, $P(x,y) = \Delta(x,y) \min{( \frac{\pi(y)}{\pi(x)},1})$ if $x \neq y$ and $P(x,x) = 1 - \sum_{y \neq x} P(x,y)$ .

Remarks:

1) An important fact concerning the Metropolis Chain algorithm is that we can easily simulate the chain since the “amount of censorship” we introduce depends on the ratios of $\frac{\pi(y)}{\pi(x)}$ .

2) Exactly the same argument applies to the case that $\Delta$ is not symmetric. In that case $\alpha(x,y) = \min{ ( \frac{ \pi(y) \Delta(y,x) }{\pi(x) \Delta(x,y) } , 1)}$ .

3) Despite the fact that the above analysis today is considered standard, it is still a remarkable result. Think about it…

4) A lot of hard work goes into proving that the chain mixes rapidly. More about this aspect in future posts.

5) Many data mining and machine learning papers which I have seen use Metropolis chains, e.g., to perform simulated annealing, but neither prove that their heuristic is there because the problem is NP-hard, nor they prove that their chain mixes rapidly. This is in my opinion something to be avoided.

Metropolis Chain

Leave a Reply Cancel reply

Follow webpage via email

Metropolis Chain

Share this:

Like this:

Leave a Reply Cancel reply

Follow webpage via email