# Deterministic algorithms inspired by MCMC?

There's a heuristic, which I find appealing, that says that for every stochastic algorithm, there should be at least one deterministic algorithm that performs better, provided the universe isn't adversarial. I first heard this principle articulated by Eliezer Yudkowsky here.

Markov Chain Monte Carlo algorithms, which are some of the post powerful and general algorithms for approximating probability distributions are, seem like a counterexample to this principle. Has there been much investigation into algorithms which take their inspiration from MCMC algorithms (I'm mostly thinking of Metropolis Hastings and Hamiltonian Monte Carlo), but which are totally deterministic? If not, why not?

-
Well, for your sentence "for every stochastic algorithm, there should be at least one deterministic algorithm that performs better", there is a counterpart written by David Mumford link. – user10525 May 25 '12 at 23:33
Haha, I'll take a look. – John Salvatier May 25 '12 at 23:35
Do "better" in what sense? Achieve a goal with less computation? Less storage? Come closer to the goal (a better near-optimum, more accuracy, etc)? Provide more insight? Are these senses to be taken universally or perhaps just asymptotically or almost surely? – whuber Jun 23 '12 at 15:35