Why does the Metropolis algorithm allow changes even for ∆E > 0? In the Metropolis Monte Carlo algorithm, why can you accept changes even for $\Delta E > 0$ (provided that a random number is less than a given probability ratio, e.g. $\exp(-\beta \Delta E)$)?
 A: Standard Monte Carlo samples the canonical (NVT) ensemble. So it maintains constant temperature but the potential energy is free to fluctuate - both up and down.
This will only seem odd if you incorrectly imagine the equilibrium state of a system to correspond to that with the minimum energy. The equilibrium state is actually determined by the minimum free energy which balances potential energy with entropy. So although there will be a natural inclination to decrease the potential energy, there is also an inclination to increase entropy (which the $\Delta E>0$ case helps achieve).
As a demonstration, imagine starting with an ice structure and increasing the temperature to 1000 K. What will happen to the structure if you omit the $\Delta E > 0$ case? Absolutely nothing.
A: The underlying reason is purely mathematical (apart from the fact that the relative probability of a state is $\exp(-\beta E)$), so'll give a mathematical answer. 
The idea is that you want to sample the state space, meaning that you want to randomly generate states so that the generated states follow a probability distribution, in your case the Boltzmann distribution. One way is to directly generate samples, but that is often not a realistic option. An alternative is to randomly walk through the state space in small steps, where the steps are generated to follow a certain distribution in such a way that the long term sample will follow the required probability distribution. The Metropolis algorithm is one of the simplest such schemes, in which neighbouring states are randomly generated and accepted or rejected in such a way as to fulfill the previously mentioned condition.
The answer to your question is simply that if you would reject changes with $\Delta E > 0$, then you wouldn't be sampling according to that distribution. 
If you want I can elaborate on how you can see this.
A: It's because you don't want to just find an optimum, but to sample the entire distribution. The MH algorithm satisfies a property called "detailed balance", and for me this video is the most intuitive explanation I've seen.
