@ Will: You happen to have named a particular deterministic algorithm; that doesn’t say much about every deterministic algorithm. Moreover, none of you folks seem to notice much that pseudo-random algorithms are actually deterministic too...
Finally, you say: “Only when the input is random will [the deterministic algorithm] on average take O(1) queries. The random one will take O(1) on average on every type of input.”
I can’t tell you how frustrating it is to see you just continue to toss in the “on average” phrase, as though it doesn’t matter, when in fact it’s the critical part.
To be blunt: you have no proof that all deterministic algorithms require n/4+1 steps on average. You only have a proof that deterministic algorithms require n/4+1 steps in the worst case, full stop. Not, “in the worse case, on average”.
DonGeddis is missing the point. Randomness does buy power. The simplest example is sampling in statistics: to estimate the fraction of read-headed people in the world to within 5% precision and with confidence 99%, it is enough to draw a certain number of random samples and compute the fraction of read-headed people in the sample. The number of samples required is independent of the population size. No deterministic algorithm can do this, not even if you try to simulate samples by using good PRNGs, because there are ``orderings″ of the world’s population that would fool your algorithm. But if you use random bits that are independent of the data, you cannot be fooled. (By the way, whether ‘true randomness’ is really possible in the real world is a totally different issue.)
Note that, for decision problems, randomness is not believed to give you a more-than-polynomial speedup (this is the P vs BPP question). But neither sampling nor the promise problem Scott mentioned are decision problems (defined on all inputs).
Regarding your claim that you cannot compare ‘worst-case time’ for deterministic algorithms with ‘worst-case expected time’ for randomized ones: this is totally pointless and shows a total lack of understanding of randomization. No one claims that you can have a randomized algorithm with success probability one that outperforms the deterministic algorithm. So either we use the expected running time or the randomized algorithm, or we allow a small error probability.
We can choose either one and use the same definition of the problem for both deterministic and randomized. Take Scott example and suppose we want algorithms that succeed with probability 2⁄3 at least, on every input. The goal is the same in both cases, so they are comparable. In the case of deterministic algorithms, this implies always getting the correct answer. DonGeddis seems not to realize this, and contrary to what he says, any deterministic algorithm, no matter how clever, needs to look at n/4+1 elements in the worst case. (By the way, maybe DonGeddis problem is that he doesn’t see the proof of this fact, but it easily provable with standard techniques.) However, a randomized algorithm that makes a worst-case constant number of queries will succeed with probability 2⁄3. If we want higher succeed probability, we can just repeat a constant number of times. Note that I’m not talking about the expected complexity but about worst-case complexity, if the former bothers you; this comes at the expense of a small error probability.
As for Blum’s paper, it shows that the best bounds we can prove for randomized algorithms in that particular problem outperform the bounds we can prove for deterministic algorithms. Sure, that does not imply the former are better, but it’s the best bound we can prove. To prove that the randomized algorithm in this case has a better constant, one needs to find a lower bound for the deterministic algorithm.
The number of samples required is independent of the population size. No deterministic algorithm can do this, not even if you try to simulate samples by using good PRNGs, because there are ``orderings″ of the world’s population that would fool your algorithm.
Wait a minute. There are also orderings of the world population that will randomly fool the random algorithm. (That’s where the 99% comes from.) Or, more precisely, there are samplings generated by your random algorithm that get fooled by the actual ordering of the world population.
If you write a deterministic algorithm that samples the exact number of samples as the random one does, but instead of sampling randomly you sample deterministically, spreading the samples in a way you believe to be appropriately uniform, then, assuming the human population isn’t conspiring to trick you, you should get exactly the same 99% confidence and 5% precision.
(Of course, if you screw up spreading the samples, it means you did worse than random, so there’s something wrong with your model of the world. And if the entire world conspires to mess up your estimate of red hair frequency, and succeeds to do so without you noticing and altering you sampling, you’ve got bigger problems.)
For example, once n is found (the number of tests needed), you list all humans in order of some suitable tuple of properties (e.g., full name name, date and time of birth, population of home city/town/etc, or maybe), and then pick n people equally distanced in this list. You’re still going to find the answer, with the same precision and confidence, unless the world population conspired to distribute itself over the world exactly the right way to mess up your selection. There are all sorts of other selection procedures that are deterministic (they depend only on the population), but are ridiculously unlikely to have any correlation with hair color.
Other example: order all cities/towns/etc by GDP; group them in groups of ~N/n; pick from each group the youngest person; I don’t think n is high enough, but if it happens that a group contains a single city with more than N/n population pick the two, three, etc youngest persons. If you’re concerned that people all over the world recently started planning their babies just to mess with you, then pick the median-by-age person.
@ Will: You happen to have named a particular deterministic algorithm; that doesn’t say much about every deterministic algorithm. Moreover, none of you folks seem to notice much that pseudo-random algorithms are actually deterministic too...
Finally, you say: “Only when the input is random will [the deterministic algorithm] on average take O(1) queries. The random one will take O(1) on average on every type of input.”
I can’t tell you how frustrating it is to see you just continue to toss in the “on average” phrase, as though it doesn’t matter, when in fact it’s the critical part.
To be blunt: you have no proof that all deterministic algorithms require n/4+1 steps on average. You only have a proof that deterministic algorithms require n/4+1 steps in the worst case, full stop. Not, “in the worse case, on average”.
DonGeddis is missing the point. Randomness does buy power. The simplest example is sampling in statistics: to estimate the fraction of read-headed people in the world to within 5% precision and with confidence 99%, it is enough to draw a certain number of random samples and compute the fraction of read-headed people in the sample. The number of samples required is independent of the population size. No deterministic algorithm can do this, not even if you try to simulate samples by using good PRNGs, because there are ``orderings″ of the world’s population that would fool your algorithm. But if you use random bits that are independent of the data, you cannot be fooled. (By the way, whether ‘true randomness’ is really possible in the real world is a totally different issue.)
Note that, for decision problems, randomness is not believed to give you a more-than-polynomial speedup (this is the P vs BPP question). But neither sampling nor the promise problem Scott mentioned are decision problems (defined on all inputs).
Regarding your claim that you cannot compare ‘worst-case time’ for deterministic algorithms with ‘worst-case expected time’ for randomized ones: this is totally pointless and shows a total lack of understanding of randomization. No one claims that you can have a randomized algorithm with success probability one that outperforms the deterministic algorithm. So either we use the expected running time or the randomized algorithm, or we allow a small error probability.
We can choose either one and use the same definition of the problem for both deterministic and randomized. Take Scott example and suppose we want algorithms that succeed with probability 2⁄3 at least, on every input. The goal is the same in both cases, so they are comparable. In the case of deterministic algorithms, this implies always getting the correct answer. DonGeddis seems not to realize this, and contrary to what he says, any deterministic algorithm, no matter how clever, needs to look at n/4+1 elements in the worst case. (By the way, maybe DonGeddis problem is that he doesn’t see the proof of this fact, but it easily provable with standard techniques.) However, a randomized algorithm that makes a worst-case constant number of queries will succeed with probability 2⁄3. If we want higher succeed probability, we can just repeat a constant number of times. Note that I’m not talking about the expected complexity but about worst-case complexity, if the former bothers you; this comes at the expense of a small error probability.
As for Blum’s paper, it shows that the best bounds we can prove for randomized algorithms in that particular problem outperform the bounds we can prove for deterministic algorithms. Sure, that does not imply the former are better, but it’s the best bound we can prove. To prove that the randomized algorithm in this case has a better constant, one needs to find a lower bound for the deterministic algorithm.
Wait a minute. There are also orderings of the world population that will randomly fool the random algorithm. (That’s where the 99% comes from.) Or, more precisely, there are samplings generated by your random algorithm that get fooled by the actual ordering of the world population.
If you write a deterministic algorithm that samples the exact number of samples as the random one does, but instead of sampling randomly you sample deterministically, spreading the samples in a way you believe to be appropriately uniform, then, assuming the human population isn’t conspiring to trick you, you should get exactly the same 99% confidence and 5% precision.
(Of course, if you screw up spreading the samples, it means you did worse than random, so there’s something wrong with your model of the world. And if the entire world conspires to mess up your estimate of red hair frequency, and succeeds to do so without you noticing and altering you sampling, you’ve got bigger problems.)
For example, once n is found (the number of tests needed), you list all humans in order of some suitable tuple of properties (e.g., full name name, date and time of birth, population of home city/town/etc, or maybe), and then pick n people equally distanced in this list. You’re still going to find the answer, with the same precision and confidence, unless the world population conspired to distribute itself over the world exactly the right way to mess up your selection. There are all sorts of other selection procedures that are deterministic (they depend only on the population), but are ridiculously unlikely to have any correlation with hair color.
Other example: order all cities/towns/etc by GDP; group them in groups of ~N/n; pick from each group the youngest person; I don’t think n is high enough, but if it happens that a group contains a single city with more than N/n population pick the two, three, etc youngest persons. If you’re concerned that people all over the world recently started planning their babies just to mess with you, then pick the median-by-age person.