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. :)
