Any deterministic strategy to solve this problem clearly requires looking at 2n/3 + 1 of the bits. On the other hand, a randomized sampling strategy only has to look at O(1) bits to succeed with high probability.
I’m not a mathematician, but something about this tripped me up. It doesn’t seem fair to compare the cost of succeeding with probability 1 (the 2n/3+1 deterministic strategy) to the cost of succeeding with probability (1 - epsilon). It shouldn’t be surprising that perfect accuracy is more expensive than less-than-perfect accuracy.
Beyond that I’m having trouble following what they’re actually disagreeing about, but it doesn’t sound like they disagree about the mathematical properties of anything. I’m smelling a dissolvable question here.
“Randomization cannot improve matters when dealing with average (random?) inputs.
“Randomization can sometimes efficiently improve matters when dealing with a hostile, but not omnicient, input-producer.” (colloquial worst case, e.g. encryption)
“Randomization can improve matters when dealing with an omnicient hostile input-producer.” (true worst case, like Omega putting a million dollars in whichever box it predicts you will not choose)
Assuming I’m following the argument correctly, I don’t think Eliezer or Scott would disagree with any of the above three.
If you ever find yourself mathematically proving that you can do better by randomizing
From the linked post. “Doing better” is ambiguous and could be interpreted as any of the above three. Are they really disagreeing about mathematical properties, or about which environments are worth worrying about?
It doesn’t seem fair to compare the cost of succeeding with probability 1 (the 2n/3+1 deterministic strategy) to the cost of succeeding with probability (1 - epsilon). It shouldn’t be surprising that perfect accuracy is more expensive than less-than-perfect accuracy.
If you have an intelligent adversary, and you leave a single opening which maxent would choose epsilon% of the time, the adversary will choose it 100% of the time. Randomization allows you to leave lots of openings, each with small probability, so they can only choose the right one epsilon% of the time.
The comparison is not quite fair—sometimes it makes sense to think of the adversary having access to your RNG, in which case you need to leave no openings—but there are cases where this is useful. (This shows up as mixed strategies in game theory, for example.)
[Edit] As an illustration, let’s work through the case with n=3. To simplify, suppose that you identify all the bits you want to probe, and then you get the results.
If you probe all 3 bits, then you get the right answer with certainty always, and the adversary can do nothing.
If you probe 2 bits, then you either see 11 or 10 or 00. In the first case, you can be certain there are two ones; in the last case, you can be certain there is only one one. In the middle case, you don’t know which is true. If your algorithm is deterministic, you preselect which bits you’ll probe—say, the first and second bit—and so the worst case is that you get 10, and if you’re playing against an opponent, they can always choose that move. If your algorithm is random, then the opponent isn’t sure which bits you’ll probe, and so a third of the time you’ll get a 11 or a 00. The adversary can reduce the algorithm’s effectiveness from 2⁄3 to 1⁄2.
If you probe 1 bit, then you either see 1 or 0. In the first case, under maxent, there’s a 2/3rds chance there are two ones; in the second case, there’s a 2/3rds chance there is one one. If you employ that deterministic algorithm and always pick the first bit against an adversary, you will be wrong every time! The adversary can reduce the effectiveness from 2⁄3 to 0.
If you probe 0 bits, then you see nothing, and are right 1⁄2 the time.
What the randomness is doing at each step is counteracting the adversary. You can also see that the deterministic algorithm separates into two cases: ‘no better than doing nothing’ and ’100% correct’, which is typical.
[Edit2]What about the case where you sample a bit, then decide whether or not to keep sampling? The work is already done- just read the above in reverse. If 2/3rds probability is good enough, then the randomized algorithm can stop after one bit, but the deterministic algorithm needs all three. If you want certainty, the randomized algorithm uses, on average, only 2.67 sampled bits, because a third of the time they can stop after two.
I’m not a mathematician, but something about this tripped me up. It doesn’t seem fair to compare the cost of succeeding with probability 1 (the 2n/3+1 deterministic strategy) to the cost of succeeding with probability (1 - epsilon). It shouldn’t be surprising that perfect accuracy is more expensive than less-than-perfect accuracy.
Beyond that I’m having trouble following what they’re actually disagreeing about, but it doesn’t sound like they disagree about the mathematical properties of anything. I’m smelling a dissolvable question here.
“Randomization cannot improve matters when dealing with average (random?) inputs.
“Randomization can sometimes efficiently improve matters when dealing with a hostile, but not omnicient, input-producer.” (colloquial worst case, e.g. encryption)
“Randomization can improve matters when dealing with an omnicient hostile input-producer.” (true worst case, like Omega putting a million dollars in whichever box it predicts you will not choose)
Assuming I’m following the argument correctly, I don’t think Eliezer or Scott would disagree with any of the above three.
From the linked post. “Doing better” is ambiguous and could be interpreted as any of the above three. Are they really disagreeing about mathematical properties, or about which environments are worth worrying about?
If you have an intelligent adversary, and you leave a single opening which maxent would choose epsilon% of the time, the adversary will choose it 100% of the time. Randomization allows you to leave lots of openings, each with small probability, so they can only choose the right one epsilon% of the time.
The comparison is not quite fair—sometimes it makes sense to think of the adversary having access to your RNG, in which case you need to leave no openings—but there are cases where this is useful. (This shows up as mixed strategies in game theory, for example.)
[Edit] As an illustration, let’s work through the case with n=3. To simplify, suppose that you identify all the bits you want to probe, and then you get the results.
If you probe all 3 bits, then you get the right answer with certainty always, and the adversary can do nothing.
If you probe 2 bits, then you either see 11 or 10 or 00. In the first case, you can be certain there are two ones; in the last case, you can be certain there is only one one. In the middle case, you don’t know which is true. If your algorithm is deterministic, you preselect which bits you’ll probe—say, the first and second bit—and so the worst case is that you get 10, and if you’re playing against an opponent, they can always choose that move. If your algorithm is random, then the opponent isn’t sure which bits you’ll probe, and so a third of the time you’ll get a 11 or a 00. The adversary can reduce the algorithm’s effectiveness from 2⁄3 to 1⁄2.
If you probe 1 bit, then you either see 1 or 0. In the first case, under maxent, there’s a 2/3rds chance there are two ones; in the second case, there’s a 2/3rds chance there is one one. If you employ that deterministic algorithm and always pick the first bit against an adversary, you will be wrong every time! The adversary can reduce the effectiveness from 2⁄3 to 0.
If you probe 0 bits, then you see nothing, and are right 1⁄2 the time.
What the randomness is doing at each step is counteracting the adversary. You can also see that the deterministic algorithm separates into two cases: ‘no better than doing nothing’ and ’100% correct’, which is typical.
[Edit2]What about the case where you sample a bit, then decide whether or not to keep sampling? The work is already done- just read the above in reverse. If 2/3rds probability is good enough, then the randomized algorithm can stop after one bit, but the deterministic algorithm needs all three. If you want certainty, the randomized algorithm uses, on average, only 2.67 sampled bits, because a third of the time they can stop after two.