Q:

Optimize the Game - Make Fair Game with Biased Coins

The traditional question states that given an unfair coin, with 0.7 probability of heads, how would you make a fair game? The answer is only consider two outcomes. If two trials yields $HT$ then the player wins, else if $TH$ the player loses.
Now the interesting part is the follow-up question. If now my head probability is 0.99, how should one go about optimizing making a fair game out of this coin? "Optimizing" means to come up with a fair game with minimal amount of coin tosses.
The original approach is inefficient, because most of the outcome would be $HH$, with probability $0.99^2$). The probability of $HT$ or $TH$ would be relatively small.

A:

The probability of flipping 69 consecutive heads is $(.99)^{69}=0.4998+$.  I'm prepared to be surprised, but I suspect that means that you can't arrange an experiment in fewer than 69 flips that would have a 50% chance of success.

A:

Each coin flip provides $-P \log_2 P = 0.0143546$ bits of information (uncertainty), and you seek $1$ bit of uncertainty.  Thus you need at least $1/.0143546 \approx 69$ such tosses.  This is perfectly efficient and the laws of information ensure you cannot do better than that.

