Why accept a worse state?
Hill-climbing accepts improving neighbors and may stop at a local optimum. If a better region lies beyond a temporary loss, a strictly improving walk cannot reach it. Simulated annealing permits such a loss with a controlled probability. A temperature is an algorithm parameter, not a physical temperature required by the problem: high temperature makes small losses easier to accept, while low temperature makes them rarer.
Definition 23.1.1
(Metropolis acceptance rule)
Let be a finite set of candidate states and let be a real-valued cost to minimize. At temperature , first propose according to probabilities . For now suppose and each row sums to one. Accept the proposed move with probability
If it is rejected, stay at . A lower or equal cost is always accepted; an increase is accepted with probability .
The proposal can itself return the current state. At each iteration the actual next-state probabilities include both self-proposals and rejected moves. Each acceptance uses a fresh uniform random draw; the proposal and acceptance mechanisms are specified as conditional probabilities given the current state. The magnitude of a cost difference matters relative to : changing all cost units by a positive factor without changing changes the algorithm.
A fixed temperature and its invariant distribution
Definition 23.1.2
(Fixed-temperature distribution and invariance)
For fixed , define
These positive numbers sum to one. Let for distinct ; put the remaining probability on the diagonal. An invariant distribution satisfies : starting with this distribution leaves the distribution unchanged after one step. It does not mean that each individual run stays at its starting state.
Theorem 23.1.3
(Detailed balance for symmetric proposals)
For a finite state space, real costs, , and symmetric proposal probabilities, is invariant for the stated transition rule. If the graph with edges between distinct states is connected, this invariant distribution is unique. Convergence from every starting state additionally requires aperiodicity; a positive self-loop at every state is sufficient.
Proof
(Detailed balance edge by edge)
For distinct , symmetry gives
The identity also holds trivially on the diagonal. Sum over : the inflow to equals . Thus is invariant. Connectivity and positive acceptance make the finite chain irreducible. The finite irreducible Markov-chain theorem gives uniqueness; with aperiodicity it also gives convergence from any initial distribution. A self-loop at each state implies aperiodicity. Invariance itself did not require connectivity or aperiodicity.
Proof X-ray
Where symmetry is used
Symmetry makes the proposal factor the same in both directions. The minimum then pairs the smaller of the two unnormalized weights with that common factor. Omitting a proposal asymmetry correction can destroy this balance.
If proposals are asymmetric, a standard alternative for a pair with both directions positive is the Metropolis–Hastings acceptance probability . Pairs proposed in only one direction have zero acceptance for this reversible construction. This distinction matters on a graph of unequal degrees: choosing uniformly among neighbors usually does not produce symmetric .
Counterexample mode
Uniform neighbor proposals are not symmetric
A tempting shortcut is to propose a uniformly chosen neighbor and apply the plain rule as if that proposal were symmetric. Take the path —— with all costs equal to , so that is uniform, at each state, for every . Every proposal is then accepted: moves to with probability , moves to or with probability each, and moves to with probability . Starting from the uniform distribution, the inflow to is only , so is not invariant for this rule; the distribution is. Multiplying the acceptance probability by repairs it: the acceptance probability becomes for and and for and , and the uniform distribution then satisfies detailed balance.
Worked search and equilibrium
Worked example 23.1.4
(A search trace that crosses a cost increase)
Take , costs , , , and propose uniformly from the other two states. At , is accepted with probability , whereas is always accepted. For instance, if the proposal is from and the independent uniform draw is , accept because . If the next proposal is , accept it; this particular trace crosses a temporary cost increase to reach the lower-cost state. The proposal rule also permits a direct move, so crossing is not necessary in this example. A draw of at the first step instead rejects the proposal and leaves the state at .
Worked example 23.1.5
(Stationary probabilities at temperature one)
At this temperature , so the stationary probabilities are
These are long-run marginal probabilities under the fixed kernel, not the probability that a two-step trace has reached . With the indicated proposal, a rejected uphill move gives a self-loop; the chain is connected, so it converges to these probabilities. Keeping the best state seen separately can return even if the current state later leaves it. That bookkeeping does not alter the transition kernel.
Worked example 23.1.6
(A hot and a cold temperature on the same states)
Keep the three states with costs , , and the uniform proposals. At the weights are , and , with sum , so . The search is nearly indifferent to cost: the uphill step of size is accepted with probability .
At the weights are , and , so and . The uphill step is accepted with probability . Leaving requires an increase of or , accepted with probabilities and , so a chain at stays there for about steps at a time. High temperature ignores cost; low temperature makes the chain almost motionless, which is why a schedule must pass between the two.
Cooling is a different process
A schedule chooses positive temperatures and applies the corresponding transition at each step. The kernels then change with time. The fixed-temperature invariant-distribution theorem cannot be applied as though the chain had already equilibrated at each temperature. At any fixed , even an optimum can be left, so returning the final state and returning the best visited state are different procedures.
Proposition 23.1.7
(The low-temperature equilibrium limit)
Let be finite and nonempty, and let be its set of global cost minimizers. As , converges to the uniform distribution on .
Proof
(Dividing out the minimum cost)
Subtract the minimum cost from every energy. This common factor cancels from numerator and denominator. For the resulting weight is ; for it is . There are finitely many states, so the denominator tends to , giving probability at each minimizer and zero elsewhere.
Counterexample mode
A cold schedule can freeze too soon
Consider a three-state path —— with costs , symmetric proposals , and remaining row mass on the diagonal. Starting at , choose at step . The chance of leaving at step given that it has not yet left is . Since and every , the infinite product is positive. Thus there is positive probability of staying at forever and never visiting the global minimizer . Low temperatures alone do not establish convergence to an optimum.
The positive-product conclusion follows, for example, because and the upper bound has finite sum. Slow-cooling theorems need additional conditions on the proposal graph and schedule; no generic finite-time success guarantee follows from the acceptance rule. Conversely, a finite budget can work well in practice, but its success must be measured for the specified cost, neighborhood, schedule and starting distribution.
Common mistakes
Common mistake
(Changing the cost scale without changing the temperature)
Multiplying every cost by keeps the ranking of the states but replaces an uphill step of size by one of size . At its acceptance probability drops from to . A temperature has meaning only relative to the units of .
Common mistake
(Returning the last state as if it were the best state)
At any fixed the chain can leave a global minimizer, so the last state visited may be worse than an earlier one. Recording the best state seen is separate bookkeeping and does not change the transition kernel.
Practice
Quick check
(At , what is the probability of accepting a proposed cost increase of ? What happens for a decrease of ?)
Use separately for an increase and for a decrease.
Solution · Answer
An increase of is accepted with probability . A decrease is accepted with probability .
Quick check
(Two states have costs and and symmetric proposal probabilities. Find their fixed-temperature stationary probability ratio and the limiting probabilities as .)
Write the ratio ; the normalizing constant cancels.
Solution · Answer
The ratio of the cost- probability to the cost- probability is . As , these probabilities tend to and , respectively. This is a limit of equilibrium distributions, not automatically of a finite cooling run.
Quick check
(A proposal graph is a path ——, and each state proposes a uniformly chosen neighbor. Is the proposal symmetric? Identify a pair showing the answer and give the correction ratio for .)
Compare with ; the correction ratio is .
Solution · Answer
No: but . For the Metropolis–Hastings rule the proposal ratio for is . The energy factor must still be included in the acceptance probability.
Quick check
(Using the three-state worked example at , calculate the probability of the exact accepted path in two steps. Why does it differ from ?)
Multiply two proposal probabilities by two acceptance probabilities.
Solution · Answer
Each proposal has probability ; the first acceptance has probability and the second has probability . The path probability is therefore . It describes one specified two-step trajectory from ; instead describes the invariant marginal under indefinite fixed-temperature transitions.