= Fixed-temperature law of simulated annealing
{title2=$\pi_T(x)=Z_T^{-1}e^{-E(x)/T}$}
On a finite <state space> $F$ with finite <objective function> values, the fixed-$T$ target is a <Boltzmann distribution>:
$$
\pi_T(x)=\frac{e^{-E(x)/T}}{Z_T},\qquad Z_T=\sum_{z\in F}e^{-E(z)/T}.
$$
The <partition function> $Z_T$ normalizes the weights but cancels from the <Metropolis–Hastings acceptance probability>. A short <detailed balance> proof explains the target. With symmetric $q$ and $x\ne y$,
$$
\pi_T(x)P_T(x,y)
=\frac{q(x,y)}{Z_T}\min\{e^{-E(x)/T},e^{-E(y)/T}\}
=\pi_T(y)P_T(y,x).
$$
Summing over $x$ gives $\pi_TP_T=\pi_T$, so this is a <stationary distribution>. On a finite <state space>, a <connected graph> of positive symmetric proposals makes the accepted <Markov chain> an <irreducible Markov chain>. Convergence from any starting state additionally requires an <aperiodic Markov chain>; one positive self-transition suffices under irreducibility. Replacing $q$ by $(I+q)/2$ ensures this. For asymmetric $q$, require connectivity through bidirectional proposals: one-way proposals are rejected.<Markov Chains and Mixing Times, second edition by David A. Levin and others>[§3.2, printed pp. 39–41: reversibility; §4.3, Theorem 4.9, printed p. 52: convergence for finite irreducible aperiodic chains]{ref}
In the <five-state barrier example for simulated annealing>, $T_*=1/\ln2$ gives exact <Boltzmann weights> $2^{-E(x)}$. Multiplying by $16$ gives
$$
\pi_{T_*}=\frac1{33}(4,8,1,4,16),\qquad Z_{T_*}=\frac{33}{16}.
$$
For the uphill edge, <detailed balance> is visible numerically:
$$
\pi_{T_*}(1)P_{T_*}(1,2)=\frac8{33}\frac1{16}
=\frac1{66}=\frac1{33}\frac12
=\pi_{T_*}(2)P_{T_*}(2,1).
$$
Thus the <global minimum> has the largest individual stationary <probability>, $16/33$, but is far from certain at this positive $T_*$. At $T_*/2$ the exact <stationary distribution> is $(16,64,1,16,256)/353$.
\Image[/simulated-annealing-equilibrium-and-acceptance.png]
{title=Lower temperature concentrates equilibrium weights while suppressing uphill acceptance}
{description=Exact <Boltzmann distributions> for the chosen five-state <objective function>, and the uphill acceptance <probability> $e^{-3/T}$ conditional on the proposal $1\to2$. The one-step <transition probability> is half that acceptance <probability>. The bars describe equilibrium at each fixed temperature, not the evolving <probability distribution> during cooling.}
For any finite $F$, let $M$ be the <set> of <global minima> and $E_{\min}$ the smallest <objective function> value. Cancelling $e^{-E_{\min}/T}$ from numerator and denominator shows that each nonminimal state's weight tends to zero as $T\downarrow0$, while every state in $M$ has equal weight. Therefore $\pi_T$ tends to the <uniform distribution> on $M$. This is a statement about a family of equilibrium <probability distributions>; it does not prove that a cooling <Markov chain> follows that family.
Back to article page
