Does there exist a finite fair gamble game with one dishonest coin?

I am thinking, maybe a well known problem, of

whether there exists a fair gamble game for two persons by tossing one dishonest coin that will always stop(one winner is selected) at no more than $N$ steps for some finite $N$.

My intuition is No.

-
It will depend on what is fixed. If you fix $N$ and have the liberty to choose the coin, then yes you can, as my answer shows. However if you have the coin at your disposition and must find $N$, it might not be possible, as shown by Ross. – Jean-Sébastien Apr 17 '13 at 15:55
@Jean-Sébastien Thanks you two. Pity that there is no way to accept two answers at the same time. – Ma Ming Apr 17 '13 at 21:52
No problem, you accept whatever answers you want, and can upvote as many as you wish. Happy to have been helpful – Jean-Sébastien Apr 17 '13 at 22:20

You are correct that this is not always possible. It depends upon $p$. For $N$ flips there are $2^N$ sequences, each with a certain probability that you can figure out if you know the probability the coin shows heads using the binomial distribution. To make a fair game, you need to be able to express $\frac 12$ as the sum of some set of these probabilities. In particular, if $p$ is transcendental, you know it is impossible because if it were possible you would have a polynomial equation with $p$ as a root.

-

For $N=2$, take $p=\frac{\sqrt{2}}{2}$ and consider a coin that comes up heads with probability $p$ and tails with probability $1-p$. The rules are as followed:

• Player $A$ wins if two throws of the coins come up as $HH$.
• Player $B$ wins otherwise.

The probability that $A$ wins is $p^2=2/4=1/2$, which makes it a fair game.

For any fixed $N$, you can find a "fair" $p$ by solving $$\frac{1}{2}=p^N,$$ which gives $e^{-\frac{\ln(2)}{N}}$. Note that for this to work you have to be able to choose $p$, as Ross shows, it can be impossible for fixed $p$ to find a $N$ that will work.

-
I guess the question didn't specify an arbitrarily dishonest coin, but could you provide a solution for that instance? – Jonathan Rich Apr 17 '13 at 15:49
@jonathan Rich The answer provided by Ross shows that for certain $p$ it can be impossible to do. I take any $N$ and show that you can find a $p$. – Jean-Sébastien Apr 17 '13 at 15:53
@JonathanRich: Not that is guaranteed to terminate for the reason I give. The standard approach is to let one player win on HT and the other win on TH and retoss if you get HH or TT. That is not guaranteed to terminate in a given number of throws. If you know $p$ you can reduce the number of wasted throws, but cannot get it to zero. – Ross Millikan Apr 17 '13 at 15:56