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?