So I recently rediscovered simulated annealing through a path that others seem to be well aware of. I was aware of Metropolis-Hastings as a sampling algorithm that creates a Markov-Chain whose stationary distribution is the distribution produced by normalizing some function. It's a small leap to realize that you can use this to optimize lots of things and you can even keep rejections that happen to be the minimum you've found so far. But further more you could also reshape the cost function so that it rewards the optimum with much higher probability than anything else (say by exponentiation or squaring the function or something). This has the effect of lowering the entropy of the normalized distribution. If we reshape the target distribution too much though our mixing times could be quite bad. We can solve this by gradually reshaping the target distribution to a low entropy distribution however. Further more higher entropy target distributions should (I think? A proof would be appreciated) have lower mixing times so if our actual target function has low entropy and long mixing times we can fix that. After one researches this line of thinking it quickly becomes clear that this is simulated annealing from a different angle than its generally presented.

The notion of entropy used in physics is deeply connected (or so I'm told) to the notion of entropy used in information theory (which is why Shannon named it as such). The physical notion of entropy is deeply connected to temperature. I've never taken thermodynamics so I don't really understand the bridge between information theoretical entropy, and temperature (which has physical entropy in the middle as the bridge).

Can this link be explained? Given a probability distribution can we define the "temperature" of the distribution? Is there an information theoretical way to define temperature? Perhaps only a subset of distributions have a temperature but we can generate probability distributions that correspond to a given temperature? I'm trying to understand the notion of temperature used in simulated annealing without learning about thermodynamics.

To give a better example of what I'm trying to ask I'll ask by analogy. Understanding what a quantum circuit is doesn't require understanding much of anything about quantum physics for a computer scientist. What's the equivalent understanding of temperature for a computer scientist that knows a bit about information theory?

  • $\begingroup$ Side note: I've found several upper bounds on mixing time that are seemingly proportional to log(1/2^H(pi)) where H is min-entropy and pi is the stationary distribution. I say seemingly because they all have an additional complicated term that depends on pi and/or the markov chain matrix (like the spectral gap of the matrix, or the Cheeger constant). But if proportionality holds then the claim that lower entropy stationary distributions will be mixed to faster is true at least for min-entropy $\endgroup$
    – Jake
    Oct 29, 2019 at 21:03

1 Answer 1


Along the lines of entropy, what you are trying to get to when using Metropolis or Simulated Annealing is a low entropy state. You want to find order within the disorder. Now, Metropolis and Simulated Annealing are slightly different things. Metropolis' goal is not to find the absolute minimum entropy, it is to recreate a distribution, which may be single mode. What simulated annealing does is focus the Metropolis to find the absolute minimum.

So in annealing you start at a high temperature, which means basically that anything is possible. Think of quantum tunneling. The most improbable thing can happen when temperatures are very high. So when we begin the optimization, we allow for a whole lot of jumps that you would not see otherwise. As you cool you focus on just what makes sense so that jumps are made only when they are better.

At a high temperature you will accept propositions at a higher rate to test the space and eventually you stop accepting these wacky ideas to focus on the best solutions only. In the end you should have a good idea of the optimal solution.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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