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