Eliezer: Am a bit confused on what you mean. Do you claim that there cannot be randomized algorithms that can solve problems in less expected computing time than any deterministic algorithm would take for that problem?
As I understand it (and computational complexity people please please please correct me if I'm way off on this) there's significant theoretical reason to suspect that probabalistic algorithms are strictly more powerful. That is, can be expected to solve some problems faster than the best possible deterministic algorithms.
Proof that this is not the case:
For any probabilistic algorithm A and problem P, there exists some sequence of random actions, among the many of which A is capable, that solves the problem the problem the fastest. (It doesn't take the same amount of time each time, so there has to be some shortest possible time it can take.) Then, there is a deterministic algorithm A' that always takes that series of actions on that problem.
But... I mean, when you combine the running time with the effort it takes to find the better, deterministic solution, it might not be ...
I'll be moving to Redwood City, CA in a week, so forgive me if I don't get a regular post out every day between now and then. As a substitute offering, some items from my (offline) quotesfile: