Can you get a fair coin flip by rolling a fair, 5-sided die a finite number of times?

Question

Can you get a fair coin flip by rolling a fair, 5-sided die a finite number of times?

Answer 1

It's clear that there are multiple ways to interpret this question, and the answer depends upon the interpretation. I personally agree with @lulu, that if a finite threshold is picked prior to die rolls, it will be impossible to determine a 'Head' or 'Tail' outcome due to the odd number of possible arrangement of dice rolls.

If we are worried about finding a result within a finite number of trials which is unbounded, the below method will serve our purposes well. The reasoning for this being that while infinite $5$s in a row is theoretically possible, it has likelihood of zero. Further, the expectation of the number of dice rolls is also finite.

1. Roll the die
2. If the result is in $\{1,2\}$, call it 'Tails'
   If the result is in $\{3,4\}$, call it 'Heads'
3. If the result is $5$, reroll until you get something in $\{1,2,3,4\}$.

$$P\left(n\text{ '5's in a row}\right) = 5^{-n}$$ $$P\left(\text{Infinite '5's}\right) = \lim_{n\to\infty}5^{-n} = 0$$ The likelihood of the $k$th roll ending in a non-'$5$' is given by $$f(k) = \left(\frac{1}{5}\right)^{k-1}\cdot \frac45$$ and so the expected number of rolls before the sequence terminates is: $$E[K] = \sum_{k=1}^\infty k\cdot f(k) = \frac45\sum_{k=1}^{\infty} k\cdot\left(\frac{1}{5}\right)^{k-1} = \frac54$$

Answer 2

I think the subtlety here is that one can imagine all sorts of complicated criteria hidden inside the "finite" method. But, however complex the method is, in the end it has to come down to looking at sequences. To see this:

First, "finite" means that there is some (known) number $k$ such that the outcome, H or T, is guaranteed to be established in $k$ or fewer rolls.

Now, suppose the Devil assures us that he can do it, with some number of rolls $k$. That means he guarantees the simulation of the fair coin in $k$ or fewer rolls, though naturally he declines to explain his method. Take $5^k$ people and give them each a different sequence of $k$ die rolls. Now, let the Devil call for rolls. whenever the Devil calls for a new roll, each person just reveals the next element of their sequence. In the end, whatever the Devil was doing, we'll see who among the people had H and who had T. After that, I no longer care what the Devil's method was. I don't need him any more, since I have every possible outcome (within the declared limits). Thus, however complex your test was, in the end it has to come down to simply calling some sequences H and others T. Alas, however, there are $5^k$ sequences, an odd number, all of which are equally probable so no subset of them has probability exactly $\frac 12$

Of course you can come arbitrarily close with high probability. Indeed, this is true even for unfair coins. If you want to simulate a coin that comes up H with probability $p$, write $p$ out as a "deci"-mal in base $5$. Now start to roll your die, regarding the rolls as if they were entries in another base 5 decimal ("pentimal" sounds just awful). If the decimal you create by rolling is less than the decimal for $p$ then record an H. Otherwise, T. Of course you might match exactly (probability $\frac {1}{5^k}$ if you roll $k$ times). But as $k$ grows the probability of matching certainly does go to $0$ and the probability of getting H goes to $p$.