Ok, but there some random algorithms which cannot be improved by derandomizing, precisely because the random algorithm does just as well as any deterministic algorithm: for example, if there is some event that has an exact 50% chance of happening, all algorithms, random or not, do equally well at guessing whether it will happen or not.
In other words, such a case doesn’t satisfy the condition that the algorithm can be “improved by randomizing.”
I take it that such an algorithm couldn’t be improved in accuracy, but I expect any randomized algorithm would be more cycle-intensive than a constant rule of “guess that event X will happen”—which will perform just as well.
Ok, but there some random algorithms which cannot be improved by derandomizing, precisely because the random algorithm does just as well as any deterministic algorithm: for example, if there is some event that has an exact 50% chance of happening, all algorithms, random or not, do equally well at guessing whether it will happen or not.
In other words, such a case doesn’t satisfy the condition that the algorithm can be “improved by randomizing.”
I take it that such an algorithm couldn’t be improved in accuracy, but I expect any randomized algorithm would be more cycle-intensive than a constant rule of “guess that event X will happen”—which will perform just as well.