Some consequences of restarting stochastic search algorithms are studied. It is shown under reasonable conditions that restarting when certain patterns occur yields probabilities that the goal state has not been found by the nth epoch which converge to zero at least geometrically fast in n. These conditions are shown to hold for restarted simulated annealing employing a local generation matrix, a cooling schedule Tn ∼ c/n and restarting after a fixed number r + 1 of duplications of energy levels of states when r is sufficiently large. For simulated annealing with logarithmic cooling these probabilities cannot decrease to zero this fast. Numerical comparisons between restarted simulated annealing and several modern variations on simulated annealing are also presented and in all cases the former performs better.
