Simulating a fair coin toss using a biased coin in fixed number of tosses

Solution 1:

No, you cannot do it with any rational different from $1/2$, and it is nontrivial. Beautiful problem! Also, this is pure elementary number theory, nothing to do with probability theory, of course.

Some notations to simplify the calculation (you already covered the case when the denominator is odd, so now it is even): probability of heads: $\frac{a}{2n}$, probability of tails: $\frac{b}{2n}$, $a+b=2n$, WLOG $\gcd(a,n)=1$ and $a$ is odd. In particular, $\gcd(a,b)=1$. Number of tosses: $k$.

So we have numbers of the form $a^k, a^{k-1}b, \ldots, ab^{k-1}, b^k$, and we need to find a subsum whose value is $2^{k-1}n^k$. The trick is that we only have one of $a^k$ and $b^k$, we have more of the rest.

Observation: We need to use $b^k$, otherwise we are not good $\pmod a$.

So we need to find a sum using expressions of the form $a^k, a^{k-1}b, \ldots, ab^{k-1}$ (we might repeat these several times in the sum) which adds up to $2^{k-1}n^k-b^k$.

All these remaining terms are divisible by $a$, so we have $2^{k-1}n^k\equiv b^k \equiv (2n-a)^k \pmod a$, so $2^{k-1}n^k\equiv 2^kn^k \pmod a$, or equivalently, $2^{k-1}n^k\equiv 0 \pmod a$. But $a$ is coprime to both $2$ and $n$, a contradiction. EXCEPT: if $a=1$.

Repeat the argument with reversing the roles of $a$ and $b$, and we obtain $b=1$. So $p=1/(1+1)=1/2$.

Solution 2:

I was just about to ask the same question! Here is what I found:

As proved by A. Pongrácz, all rational numbers except $1/2$ cannot simulate $1/2$. Let $p=a/(a+b)$, where $a$ and $b$ are relatively prime. After $n$ tosses, there are $1/2^n$ possible outcomes. The probability of each outcome is a rational number with denominator $(a+b)^n$. The numerators are all multiples of $b$, except one numerator which is $a^n$. Therefore, in any partition of the outcomes into two subsets, one subset (the one containing the $a^n$) will have a sum that is not a multiple of $b$, while the other sum will have a sum that is a multiple of $b$. Hence the two sums cannot be equal.
On the other hand, $p$ can simulate $1/2$ whenever $p = (1/2)^{1/n}$, for some integer $n\geq 1$. Proof. Just toss the coin $n$ times. The probability that it lands $n$ times on Heads is exactly $1/2$.