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 worth it. It’s only worth it if you can generalize the solution to other problems. So I guess randomized algorithms are better when the time you spend thinking about how to do it better pays for itself in time saved, summed across all the problems you apply that thinking to.
EDIT: Oops that last sentence is basically the opposite of what I was trying to say
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 worth it. It’s only worth it if you can generalize the solution to other problems. So I guess randomized algorithms are better when the time you spend thinking about how to do it better pays for itself in time saved, summed across all the problems you apply that thinking to.
EDIT: Oops that last sentence is basically the opposite of what I was trying to say