Parallel tempering

Remarks

Both kinds of moves leave the product measure $\pi_{\beta_1} \otimes \dots \otimes \pi_{\beta_M}$ invariant. For the swap, the ratio of the product weights after and before is as follows. $$\frac{\pi_{\beta_i}(x_{i+1}) \pi_{\beta_{i+1}}(x_i)}{\pi_{\beta_i}(x_i) \pi_{\beta_{i+1}}(x_{i+1})} = e^{(\beta_i - \beta_{i+1})(H(x_i) - H(x_{i+1}))},$$ so the rule of clause 2 is the Metropolis rule for a symmetric proposal, and it satisfies detailed balance. Hence the marginal of $x_M$ is $\pi_{\beta_M}$, and averages of $x_M$ estimate thermal averages at the lowest temperature. Example: let the hotter copy $x_i$ have the lower energy. Then $\beta_i - \beta_{i+1} < 0$ and $H(x_i) - H(x_{i+1}) < 0$, so the exponent is positive and the swap is always accepted. In this way low-energy states move towards the cold end. Non-example: accepting every swap would break the invariance, because a high-energy state from the hot copy would be pushed into the cold copy too often. The temperatures must be close enough that the energy distributions of neighbouring copies overlap; otherwise almost all swaps are rejected.