An idea I shared on "Can you behave randomly? (1998)" ( https://news.ycombinator.com/item?id=11753194 ) seems relevant here. The keypresses I entered were not predictable by the Oracle. I generated the keypresses by first picking an arbitrary integer in [0,59]. I then (using simple mental arithmetic) used that integer to seed a PRNG by George Marsaglia [1] to generate a stream of pseudo-random decimal digits. For eac…
Can't you invoke a simpler random generator? Let's say primes % 4 ?
See results at http://imgur.com/iaHBNNr ("Your nth attempt" is primes % 4, "Coin nth attempt" is the Marsaglia PRNG). Note that primes % 4 has too many runs, its prob(H given H) is too low, and its prob(H given T) is too high.