Five-state barrier example for simulated annealing

Consider the chosen finite minimization problemOnly adjacent integers are neighbors. At each interior state propose left or right with probability $1/2$ each; at an endpoint propose its sole neighbor with probability $1/2$ and itself with probability $1/2$. This proposal distribution is symmetric, including at the endpoints. The local minimum at $1$ is relative to these allowed moves; $4$ is the unique global minimum.

At $1$, improving-only local search rejects both neighbors because $E(0)=2$ and $E(2)=4$ exceed $E(1)=1$. For simulated annealing, choose $T_{\ast }=1/\ln 2$, using the natural logarithm. Conditional on proposing $2$ from $1$, the acceptance probability isThe one-step transition probability is instead $P_{T_{\ast }}(1,2)=(1/2)(1/8)=1/16$. Both subsequent rightward proposals are downhill, so the conditional probability of the precise next three states being $2,3,4$, given $X_0=1$ and fixed $T_{\ast }$, isThis is one possible escape route, not the probability of eventually reaching $4$. Rejections, excursions toward $0$, and repeated attempts give many other sample paths. The calculation establishes possibility, without claiming a general performance advantage from a selected sample path.

For comparison, halving $T_{\ast }$ makes the uphill acceptance probability $1/64$; doubling it makes that probability $1/(2\sqrt{2})$. Cooling makes it harder to leave this local minimum, even though the stationary distribution increasingly favors the global minimum. That tension is the central scheduling problem.