If instead the simulator can read the real probability on an infinite tape… obviously it can’t read the whole tape before producing an output. So it has to read, then output, then read, then output. It seems intuitive that with this strategy, it can place an absolute limit on the advantage that any attacker can achieve, but I don’t have a proof of that yet.
In this model, a simulator can exactly match the desired probability in O(1) expected time per sample. (The distribution of possible running times extends to arbitrarily large values, but the L1-norm of the distribution is finite. If this were a decision problem rather than a sampling problem, I’d call it ZPP.)
Algorithm:
Start with an empty string S.
Flip a coin and append it to S.
If S is exactly equal to the corresponding-length prefix of your probability tape P, then goto 2.
In this model, a simulator can exactly match the desired probability in O(1) expected time per sample. (The distribution of possible running times extends to arbitrarily large values, but the L1-norm of the distribution is finite. If this were a decision problem rather than a sampling problem, I’d call it ZPP.)
Algorithm:
Start with an empty string S.
Flip a coin and append it to S.
If S is exactly equal to the corresponding-length prefix of your probability tape P, then goto 2.
Compare (S < P)
D’oh! Of course—thanks!