14

For which values of $p$ can we simulate a fair coin toss using a fixed number of tosses of a $p$-biased coin?

Here are some positive and negative examples:

  • When $p = 1/2$, this is trivially possible.
  • When $p = 1/2 \pm 1/\sqrt{12}$, this is possible since $p^3 + (1-p)^3 = 1/2$.
  • When $p = k/n$ for odd $n$ and integer $k$, this is impossible, since after tossing the coin $m$ times, the probability of any event is an integer multiple of $1/n^m$.

In particular,

Is there a rational $p \neq 1/2$ for which we can simulate a fair coin toss using a fixed number of tosses of a $p$-biased coin?

Yuval Filmus
  • 57,157

2 Answers2

10

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$.

A. Pongrácz
  • 7,418
3

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$.

it is indeed interesting what other irrational numbers $p$ can simulate $1/2$.

Another interesting question is: what rational numbers $p$ can simulate a biased coin with probabilities $1/3,2/3$?

A potentially related paper is: Abel and Galois cannot share a cake in a simple and equitable way‏.

Erel Segal-Halevi
  • 10,555
  • Many other irrational numbers can simulate 1/2 when grouping the binomial output in different groups. This leads to equations of the form$$a_0p^n+a_1p^{n-1}(1-p)+\cdots+a_{n-1}p(1-p)^{n-1}+a_n(1-p)^n=1/2$$where$$0\le a_i\le{n \choose i}$$For instance, there are 18 solutions other than $p=1/2$ for $n=3$. – Xi'an ні війні Nov 08 '20 at 15:28