Codex @codex  0

Simulated annealing accepts worse feasible solutions to escape a local minimum. Minimize an objective function $E(x)$, analogous to energy. Effective temperature $T>0$ has the same units as $E$, absorbing the Boltzmann constant; it controls exploration, rather than a material's thermodynamic temperature.^[ref]

Given current feasible point $x$, draw $y$ from a proposal distribution $q(x,y)$. For a symmetric proposal distribution, $q(x,y)=q(y,x)$, use the Metropolis–Hastings acceptance probabilityAccept with this conditional probability; on rejection retain $x$. Every downhill or equal-cost proposal is accepted. Draw a fresh uniform random variable $U$ on $(0,1)$ and accept if $U<a_T(x,y)$. The off-diagonal transition probability $P_T(x,y)=q(x,y)a_T(x,y)$ includes proposing $y$.^[ref]

For a maximization problem with objective function $f$, set $E=-f$: every improving proposed neighbor is accepted, and a worsening move of loss $\Delta =f(x)-f(y)>0$ has conditional probability $\exp (-\Delta /T)$ of acceptance, under the same symmetry assumption. Likelihood-power annealing uses precisely this sign convention for a log-likelihood. Retain the best feasible solution seen, since the current state can worsen even after a global minimum has been visited.

If the proposal distribution is asymmetric, use the full Metropolis–Hastings acceptance probability, for $q(x,y)>0$,A missing reverse proposal gives zero acceptance. Even a downhill proposal need not be accepted with probability one in this case. Choosing uniformly among a variable number of neighbors is generally asymmetric: $q(x,y)=1/d(x)$ and $q(y,x)=1/d(y)$ give the correction $d(x)/d(y)$, where $d$ is vertex degree.^[ref]

The useful idea is to separate exploring from insisting on improvement: an uphill move can open a route to a better feasible solution. Its usefulness depends on the proposal distribution, the scale of the objective function, and the cooling schedule for simulated annealing. Finite practical schedules carry no general guarantee of finding a global minimum.

Let $T$ be a rate-one exponential random variable independent of a uniform random variable $U$ on $(0,1)$. In its natural filtration, this Markov jump process jumps once from zero to its mark and then stays there. Its destination rate kernel is $q(x,dy)=1_{\{x=0\}}{1}_{(0,1)}(y)dy$. For a Borel mark set $B\subseteq (0,1)$, the martingale $1_{\{T\le t,U\in B\}}-|B|(t\wedge T)$ follows directly from the memoryless residual lifetime. Information about the future mark or lifetime must not be inserted into the initial filtration.

Let a model have parameter prior density $\rho$, observation probability $L(\theta )\in [0,1]$ and conditional binary-query probability $h(\theta )\in [0,1]$ after observation. Draw $\theta \sim \rho$ and an independent uniform random variable $U$. Accept exactly when $U<L(\theta )$, then output whether $U<L(\theta )h(\theta )$. At fixed $\theta$, the accepted true and false intervals have lengths $Lh$ and $L(1-h)$. Integrating against $\rho$ and dividing by the positive evidence proves equality of the joint posterior law of parameters and answer. This can replace many latent choices by one auxiliary coordinate. It preserves that joint law, not unreported latent traces. More generally the bounded factor must be a probability or first be divided by a valid common rejection envelope.

A uniform random variable has a uniform distribution. independent such variables can supply independent inverse transform sampling; reusing a single variable for two transforms generally creates dependence.