So, the randomized algorithm isn’t really better than the unrandomized one because getting a bad result from the unrandomized one is only going to happen when your environment maliciously hands you a problem whose features match up just wrong with the non-random choices you make, so all you need to do is to make those choices in a way that’s tremendously unlikely to match up just wrong with anything the environment hands you because it doesn’t have the same sorts of pattern in it that the environment might inflict on you.
Except that the definition of “random”, in practice, is something very like “generally lacking the sorts of patterns that the environment might inflict on you”. When people implement “randomized” algorithms, they don’t generally do it by introducing some quantum noise source into their system (unless there’s a real adversary, as in cryptography), they do it with a pseudorandom number generator, which precisely is a deterministic thing designed to produce output that lacks the kinds of patterns we find in the environment.
So it doesn’t seem to me that you’ve offered much argument here against “randomizing” algorithms as generally practised; that is, having them make choices in a way that we confidently expect not to match up pessimally with what the environment throws at us.
Or, less verbosely:
Indeed randomness can improve the worst-case scenario, if the worst-case environment is allowed to exploit “deterministic” moves but not “random” ones. What “random” means, in practice, is: the sort of thing that typical environments are not able to exploit. This is not cheating.
What “random” means, in practice, is: the sort of thing that typical environments are not able to exploit.
No, it means “the sort of thing which is uncorrelated with the environment”. What you want is for your responses to be correlated with the environment in a way that benefits you.
So, the randomized algorithm isn’t really better than the unrandomized one because getting a bad result from the unrandomized one is only going to happen when your environment maliciously hands you a problem whose features match up just wrong with the non-random choices you make, so all you need to do is to make those choices in a way that’s tremendously unlikely to match up just wrong with anything the environment hands you because it doesn’t have the same sorts of pattern in it that the environment might inflict on you.
Except that the definition of “random”, in practice, is something very like “generally lacking the sorts of patterns that the environment might inflict on you”. When people implement “randomized” algorithms, they don’t generally do it by introducing some quantum noise source into their system (unless there’s a real adversary, as in cryptography), they do it with a pseudorandom number generator, which precisely is a deterministic thing designed to produce output that lacks the kinds of patterns we find in the environment.
So it doesn’t seem to me that you’ve offered much argument here against “randomizing” algorithms as generally practised; that is, having them make choices in a way that we confidently expect not to match up pessimally with what the environment throws at us.
Or, less verbosely:
Indeed randomness can improve the worst-case scenario, if the worst-case environment is allowed to exploit “deterministic” moves but not “random” ones. What “random” means, in practice, is: the sort of thing that typical environments are not able to exploit. This is not cheating.
No, it means “the sort of thing which is uncorrelated with the environment”. What you want is for your responses to be correlated with the environment in a way that benefits you.