Don - the "sleight of hand", as you put it is that (as I think has been said before) we're examining worst-case. We explicitly are allowing the string of 1s and 0s to be picked by an adversarial superintelligence who knows our strategy. Scott's algorithm only needs to sample 4 bits on average to answer the question even when the universe it out to get him - the deterministic version will need to sample exactly n/4+1.
Basically, Eliezer seems to be claiming that BPP = P (or possibly something stronger), which most people think is probably true, but...
I'm sure most people here are aware of Axelrod's classic "experiment" with an Iterated Prisoner's Dilemma tournament in which experts from around the world were invited to submit any strategy they liked, with the strategy which scored the highest over several rounds with each of the other strategies winning, and in which Tit for Tat came out top (Tit for Two Tats winning a later rerun. Axelrod's original experiment was fixed-horizon, and every single "nice" strategy (never defect first) that was entered finished above every single "...
I get the feeling a lot of proponents of cryonics are a bit like those who criticize prediction markets, but refuse to bet on them. If you really believe that signing up for cryonics is so important, why aren't you being frozen now? Surely there are large numbers of branches in which your brain gets irretrievably destroyed tomorrow - if the reward for being frozen is so big, why wait?
"Suppose we agree that shoplifting is morally objectionable behavior. Is it true that the only solution to shoplifting is violence or the threat of violence? I don't think so"
Well then you disagree with most of the rest of the world - at least in the UK, we tend to forcibly place shoplifters in prisons - if that's not violence, I don't know what is.
Don, if n is big enough then sure, I'm more than willing to play your game (assuming I get something out of it if I win).
My randomised algorithm will get the right answer within 4 tries in expectation. If I'm allowed to sample a thousand bits then the probability that it won't have found the answer by then is .75^1000 which I think is something like 10^-120. And this applies even if you're allowed to choose the string after looking at my algorithm.
If you play the game this way with your deterministic algorithm you will always need to sample n/4 + 1 bits ... (read more)