I’ll be thinking about this problem for the next hour or so unless something comes up, so I’ll be writing my thoughts down here if I think they are important.
A couple of preliminary observations:
The magician must be playing a mixed strategy. This is easy to see since otherwise a copy of the magician playing against him could know when he stops and could know his prediction and deliberately falsify it no matter what.
It’s not enough for the prediction after the stopping to be random, the stopping time itself must also be random. This is because if I knew when the magician would stop then from that moment on I would just randomize my bit string to be either all 1s or all 0s, and the magician couldn’t win with a probability above 50% no matter what.
The naive intuition that “it’s impossible because the magician can’t gain information about the future of an arbitrary bit string” is wrong, because the magician doesn’t actually need to gain information in a technical sense to be able to make this prediction. Obviously if the bit strings are sampled randomly from the Cantor set then the magician could just guess that 50% of the next 1 million digits would be 0 and he would win even though he has no information about the string at all.
I don’t have a solution, but I’ve done some analysis to try to make a strategy of the following form work: pick the number of steps at which you halt from a distribution ∼1/k1+ε and then guess that the mean of the next k terms will be equal to the mean of the last k terms. I tried to get a cancellation in some L2 error sum but unfortunately it went nowhere.
I think this strategy doesn’t work and I’m not even sure if it’s a good idea to not have k depend on the sequence the magician has seen so far, but I couldn’t see a simple argument for why it would be impossible so I tried to make it work anyway.
The magician needs to separately pick “how long a horizon to look over” and “when to stop.” Otherwise I can just have a string with exponentially increasing runs of 0s and 1s, and you’ll usually be pretty wrong if you use the first k to predict the next k.
I’ll be thinking about this problem for the next hour or so unless something comes up, so I’ll be writing my thoughts down here if I think they are important.
A couple of preliminary observations:
The magician must be playing a mixed strategy. This is easy to see since otherwise a copy of the magician playing against him could know when he stops and could know his prediction and deliberately falsify it no matter what.
It’s not enough for the prediction after the stopping to be random, the stopping time itself must also be random. This is because if I knew when the magician would stop then from that moment on I would just randomize my bit string to be either all 1s or all 0s, and the magician couldn’t win with a probability above 50% no matter what.
The naive intuition that “it’s impossible because the magician can’t gain information about the future of an arbitrary bit string” is wrong, because the magician doesn’t actually need to gain information in a technical sense to be able to make this prediction. Obviously if the bit strings are sampled randomly from the Cantor set then the magician could just guess that 50% of the next 1 million digits would be 0 and he would win even though he has no information about the string at all.
I don’t have a solution, but I’ve done some analysis to try to make a strategy of the following form work: pick the number of steps at which you halt from a distribution ∼1/k1+ε and then guess that the mean of the next k terms will be equal to the mean of the last k terms. I tried to get a cancellation in some L2 error sum but unfortunately it went nowhere.
I think this strategy doesn’t work and I’m not even sure if it’s a good idea to not have k depend on the sequence the magician has seen so far, but I couldn’t see a simple argument for why it would be impossible so I tried to make it work anyway.
This seems like it nearly works, but
The magician needs to separately pick “how long a horizon to look over” and “when to stop.” Otherwise I can just have a string with exponentially increasing runs of 0s and 1s, and you’ll usually be pretty wrong if you use the first k to predict the next k.