James Propp <jamespropp(a)gmail.com> wrote:
> 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?
Certainly. I assume that the square roots of the primes, in
binary, to the right of the radix point, are normal ("random") and
uncorrelated. If so, consider some subset of the first k primes. B
hashes (exclusive-ors) the digit sequences (to the right of the radix
point) of the square roots of those primes together to generate the
bit sequence. If k is 20, there will be about a million possible
algorithms, so A can probably find the correct one (asuming A only
tries algorithms in this set). But if k is much more than 20, A
doesn't stand a chance.
> 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.
How large can n be? If k is more than a thousand, converting all mass
in the universe into computers and running them all in parallel until
the heat death of the universe wouldn't suffice to find B's algorithm.
Of course there will be a chance just slightly less than 1/2 that two
completely uncorrelated finite bit strings (e.g. A's and B's, if A is
clueless) will match slightly more than half the time, but in the long
run the proportion of matches will bounce between slightly more than
1/2 and slightly less than 1/2.
Regardless of B's algorithm, so long as it produces the same number
of 0s and 1s on average, I think it very unlikely that the asymptotic
proportion of matches could be anything but 1/2 or 1.
> 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).
If I understand you correctly, B comes up with an algorithm to
generate an unending sequence of bits, and A tries to guess the
algorithm so as to generate the same sequence (the same other than
some finite number of mismatched bits at the beginning before A
guesses the correct algorithm, I mean). As such, I don't understand
the point in the oracle. If B simply asks the oracle for a complete
list of every algorithm A will try, that would make B's already easy
task even easier.
