12

This puzzle was told to me by a Stanford PhD student in a graduate course on randomized algorithms. It's really clever/beautiful, and I think makes for a great challenge.

You are given a fair coin, and your goal is to simulate a biased coin with an arbitrary(!) bias. On average, your method must terminate in 2 coin flips. You can have any probability p, p=1/pi, p=1/17, p=.25, etc.

To make this a bit more formal, I'll give some pseudo-code.

# flip() -> returns true with probably 1/2
# flip() is the only source of randomness allowed.
def biased_flip(p):
   """
   Returns true with probability p.
   """
   ... # TODO: implement me!

if we call biased_flip() a million times, we will


expect flip() to have been called on average 2 million times


Any individual call could flip more than twice, but expectation is 2 per call.


for i in range(10e6):
   biased_flip(random.uniform())

I promise it's possible.

Hint 1:

The solution begins with turning the probability p into a binary decimal string. For example, 1/4=0.01.

Hint 2:

k coin flips can be turned into a binary decimal, which will partition the interval [0, 1] into 2^k subintervals. Each of these subintervals are equally likely. As k approaches infinity, are able to sample essentially uniformly from [0, 1].

Hint 3:

Keep flipping the coin, and with each flip, build up a binary string. 1 if the flips is H, 0 if T. The flips HHTT -> 0.1100. If your binary string is below the expansion of p so far, will it ever go above? If it's above, will it ever go below?

Hint 4:

1 + 1/2 + 1/4 + 1/8 + 1/16 converges to 2.

Evargalo
  • 6,270
  • 1
  • 19
  • 39
weissguy
  • 195
  • 7

2 Answers2

10

Well, it's very simple.
Let's write $p$ as a (possibly infinite) binary fraction: $p=0.p_1p_2p_3\dots$, where $p_i$ is either 0 or 1. Next, start tossing the coin, generating number $q=0.q_1q_2\dots q_k$ (where $q_i$ is the result of the $i$-th toss, 1=heads and 0=tails, or vice versa), until that value of $k$ where it becomes clear if $q<p$ or $q>p$ (equality can be treated in the either case). (For example, if $p_1=0$ and $q_1=1$, it's clear then $q\geqslant p$, since $0.1_2=0.011111\dots_2$, so we stop at $k=1$).
Now, there is a question. How frequently will we stop after $k$ tosses? Well, we need exactly $k$ flips if and only if $p_i=q_i \forall i=1,2,\dots,k-1$ , but $p_k\neq q_k$. Probability of that is $\frac{1}{2^k}$, since $q_i$ are independent (and have a Bernoulli distribution with parameter $\frac12$). So, the average number of tosses is $$\sum\limits_{n=1}^\infty n\times\frac{1}{2^n}=2$$ (The latter is proven by the fact that $\sum\limits_{n=1}^\infty \frac{x^n}{2^n}=\frac{2}{2-x} (-2\leqslant x < 2)$, thus by differentiating $\sum\limits_{n=1}^\infty \frac{nx^{n-1}}{2^n}=\frac{2}{(2-x)^2}$. Plugging $x=1$ (which is well within the radius of convergence) gives the result.)

trolley813
  • 11,282
  • 2
  • 25
  • 57
1

(Note: Please forgive my lack of math formatting ability.)

 bool biased_flip(decimal p)
 {
    decimal stepSize = .5;
    decimal accumulation = 0;
    while (accumulation < p && accumulation + stepSize * 2 > p)
    {
        if(flip())
        {
            accumulation += stepSize;
        }
        stepSize /= 2;
    }
    return accumulation >= p;
}

Because it's a computer puzzle, I wrote a (pseudo) program! How does it work?

Since we're relating coin flips to probability p, 0<p<1, I

related individual flips of the coin to positive integral powers of 1/2 (stepSize)

because

the sum of all such values converges to 1

and

any positive value less than 1 can be represented by a subset of this sum

So the nth flip of the fair coin represents

The nth power of 1/2

Each true result of flip()

Adds the corresponding power of 1/2 to a running total (accumulation) for the current biased_flip().

Each false result of flip()

Does not add the corresponding power of 1/2, but skips it.

The result of the biased flip is decided when

Either accumulation meets/exceeds p (true), or accumulation can no longer meet/exceed p (false).

Essentially, we're using fair coin flips to

generate a random number, which is then compared with p

but the method terminates when enough information is gathered to

determine whether p or the new random number is greater.

Finally, how do we know the average number of fair coin flips per biased flip is 2?

Every flip of the fair coin terminates the biased flip 50% of the time

That is, exactly one of the following is true at each flip:

A true flip() will result in accumulation meeting/exceeding p, so the biased_flip() returns true. (when accumulation + stepSize >= p)

or

A false flip() will leave the value of accumulation too low to reach p with any number of subsequent true flip()s, so the biased_flip() returns false. (when accumulation + stepSize < p)

Thus we are guaranteed to flip the fair coin at least once for each biased flip, and each additional fair flip occurs

with half the probability of the previous flip, on average.

The average number of fair flips per biased flip is therefore

1 + all positive integral powers of 1/2

= 2

ADoofus
  • 96
  • 1
  • 5