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.
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.