6
$\begingroup$

It is a classic problem to simulate a fair coin with a biased one.

According to Fair Coin (wiki),

John von Neumann gave the following procedure:

  1. Toss the coin twice.
  2. If the results match, start over, forgetting both results.
  3. If the results differ, use the first result, forgetting the second.

In the worst case, the procedure may not terminate.

Problem: Is it possible to design an algorithm which guarantees termination in the worst case? What is the technique to solve such an impossibility problem?

$\endgroup$
  • 2
    $\begingroup$ No, it’s not possible, even when you know the bias of the coin to be, say, 1/3. $\endgroup$ – Yuval Filmus Sep 1 '18 at 15:23
10
$\begingroup$

No, it's not possible. Suppose the bias of the coin is $1/3$, and suppose you could guarantee termination. Then there would be some $n$ such that this always terminates after $n$ coin flips. Let $S$ denote the set of flip-sequences that causes your algorithm to output 0 (so that $\overline{S}$ is the set of flip-sequences that causes your algorithm to output 1). The probability of your algorithm outputting 0 is equal to the probability of getting a flip-sequence in $S$, which is a sum of the form

$$\sum_{x \in S} {a_x \over 3^n}$$

where each $a_x$ is an integer. Thus the probability of outputting 0 has the form $b/3^n$ where $b$ is an integer. We want this to be $1/2$, for your algorithm to produce an unbiased bit of output. However since $3^n$ is odd, there is no integer $b$ such that $b/3^n = 1/2$. Therefore, no such algorithm can exist.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.