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

Question

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.

Answer 1

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.

Answer 2

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.