>with better asymptotic probabilistic bounds than simulated annealing This seems unlikely to me. The Metropolis algorithm is just simulated annealing with a c

>with better asymptotic probabilistic bounds than simulated annealing This seems unlikely to me. The Metropolis algorithm is just simulated annealing with a constant temperature. Which means that simulated annealing includes Metropolis MCMC as a special case. Also, while simulated annealing is guaranteed to find the global optimum given infinite time (almost sure convergence), I'm not aware of any such guarantees for Metropolis.