0

Provided a coinflip generator (a function that can be called to provide an output of either 1 or 0 with equal probability of $1/2$), is it possible to construct a function that would

  1. yield either a, b or c with equal probability of $1/3$, and

  2. have well-defined memory requirements, runtime and guaranteed termination? (This point rules out running the coinflip two times for 4 outcomes and assigning one of the outcomes to re-run, because that is no longer guaranteed to terminate.)

This thought experiment appeared simple at first, but having given it some thought, I'm not sure this is possible, but I can't prove either case.

Zubo
  • 173
  • 4
  • 1
    See also https://math.stackexchange.com/questions/1333/ and https://math.stackexchange.com/questions/3340212/. – joriki Apr 29 '20 at 22:53

1 Answers1

1

No, this is not possible. When you flip the coin $n$ times, you have $2^n$ equiprobable results. You want to divide them up equally among the $3$ outcomes, but $2^n$ is not divisible by $3$. Thus, no matter how often you throw the coin and no matter how you assign the outcomes, there will always be $1$ or $2$ outcomes left over. Thus, an algorithm that yields a probability of exactly $\frac13$ cannot be guaranteed to terminate; you can only minimize the expected number of coin flips you need to generate.

joriki
  • 238,052
  • I have also come up with this, but was not sure this rules it out completely - can this be considered proof? – Zubo Apr 29 '20 at 22:53
  • I was always curious about a slightly relaxed problem, that is, if I just require finite termination (arbitrary number of steps) for all inputs (not just ae.) is it possible to define an algorithm that satisfies 1. in the question? Seems tantalisingly doable. – copper.hat Apr 29 '20 at 23:01