0
$\begingroup$

I've been trying to understand the original paper in which the Metropolis algorithm was proposed, specifically the proof of convergence given in section II.

The final step in the proof gives the inequality $$(\nu_r/\nu_s) > [\exp(-E_r/kT)/\exp(-E_s/kT)],\tag{6}$$ The paper says that the above inequality plus ergodicity implies convergence, but I don't see how this follows. I can see that $\exp(-E_r/kT)/\exp(-E_s/kT) = \exp(-\Delta E/kt)$, which is the threshold used when deciding to accept the new state. But in the algorithm, we choose $\xi_3$ uniformly between 0 and 1, and accept iff $\xi_3 < \exp(-\Delta E/kt)$. I don't see how $\xi_3$ is related to $\nu_r/\nu_s$, or even why we care about the quantity $\nu_r/\nu_s$.

Another question I have is that in more modern presentations of the Metropolis algorithm, the proof of convergence basically goes like this: (1) show that the acceptance probabilities imply that the transition probabilities satisfy detailed balance, (2) show that detailed balance implies a stationary distribution. However, in the proof in this paper, there is no mention of detailed balance or anything resembling it. What's going on?

$\endgroup$
2
$\begingroup$

Suppose $\nu_r$ is the invariant measure. The claims made (preceding (5) and (6)) are that if $E_r > E_s$, then

  • the flow from $r$ to $s$ is $\nu_r P_{rs}$
  • the flow from $s$ to $r$ is $\nu_s P_{sr} \cdot \exp \left( - \left[ E_r - E_s \right] / kT \right)$

In (5) and (6), the reasoning is that if these two terms are not equal, then the system is not at equilibrium.

If one takes $\nu_r = \exp \left( - E_r / kT \right)$, then the system is at equilibrium, and thus is an invariant measure for the Markov chain constructed.

Note that `equilibrium' here is used synonymously with 'in detailed balance'.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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