# Expected number of steps before a global optimum is found with Simulated Annealing

I'm reading a technical report on Simulated Annealing: On the Convergence Time of Simulated Annealing, by Sanguthevar Rajasekaran. You may find it following this link.

Given $G=(V, E)$ is the graph whose vertices are possible solutions to the given problem, and $E$ is the set of edges between the neighbours, the goal is to prove convergence of SA. For that purpose, the author assumed that $G$ is strongly connected and denoted the diameter of $G$, its degree and maximal energy difference between vertices by $D$, $d$ and $\Delta$, respectively.

There is a lemma on the 6th page:

If $X$ is any state in $V$, then the expected number of steps before a global optimal state is visited starting from $X$ is $\le (\frac 1 d \times e^{-\Delta / T})^{-D}$.

The probability to visit a neighbour $S_j$ after $S_i$ is:

$$\frac 1 d \times e^{\frac{-\Delta E}{T}}$$ where $\frac 1 d$ is the probability of selecting $S_j$ of all $d$ neighbours of $S_i$, and $e^{\frac{-\Delta E}{T}}$ is the probability to actually move to it. $T$ is held constant in the model.

In the proof of the lemma, the author determines the probability to visit a global optimum $g$ from any state $X$ as $\ge [\frac 1 d \times e^{-\frac \Delta T}]^D$ and finishes the proof:

This implies that the expected number of steps before $g$ is visited is $\le [d e^{\frac \Delta T}]^D$.

Would anyone care to explain how do we get the estimate for the number of steps? I'm stuck with it, but am really, really intrigued to figure this out. :)

• In addition to the answer by Jannis Teunissen, the easiest way to find answers would have been to contact the author of the paper :-) – Wolfgang Bangerth Dec 28 '15 at 19:30

## 1 Answer

Suppose the probability to reach the optimum from any state is $p$, in other words at each step the probability of reaching the optimum has a Bernoulli distribution with parameter $p$. The number of steps required then has a Geometric distribution, with mean $1/p$. If you add back the inequality signs you get the result you stated.