I don’t see why this will work. If there’s a tie for success-rate-furthest-from-0.5, moving one of them toward .5 might move the other farther away. Jim Propp On Thu, Oct 3, 2019 at 1:24 PM Brent Meeker via math-fun < math-fun@mailman.xmission.com> wrote:
Having produced a finite sequence of bits, to choose the next bit Player B runs all n algorithms and chooses the next bit value that will move the algorithm whose success rate is furthest from 0.5 toward 0.5.
Brent
On 10/3/2019 4:43 AM, James Propp wrote:
Define a bit-guessing algorithm to be any algorithm that, given a finite string of bits as input, predict what the next bit will be; define the bit-guessing game as an adversarial game in which Player A chooses a bit-guessing algorithm, Player B chooses an infinite sequence of bits, and the score is the asymptotic density (maybe I should say upper density or lower density?) of the set of n’s for which A’s algorithm correctly predicts B’s nth bit.
Question: If Player B is given complete knowledge of the innards of a million bit-guessing algorithms, can B construct an infinite sequence of bits whose score lies between .49 and .51 for *all* of those algorithms? Of course by “a million” I mean “n”, and by .49 and .51 I mean one-half plus epsilon and one-half minus epsilon, with suitable quantifiers.
I want a (nonrandom) construction, not an existence proof.
We’ll allow B to consult an oracle that will answer questions about those million bit-guessing algorithms (e.g., the oracle will reveal the truth-status of the Riemann Hypothesis if that’s germane).
This is probably an old problem, but I’m not sure how to search for it.
Jim Propp _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun