Suppose you have a fair n-sided die $D_n$ - or rather suppose you don't have a $D_n$ but want to simulate one by repeatedly (but finitely many times) throwing a single (possibly biased) coin $C_p$ that has a probability of $p\in (0,1)$ of landing on heads.
Two questions arise:
- Is it always possible to find a $p$ such that a $C_p$ can simulate a $D_n$?
- What is the minimum number of throws needed to simulate a $D_n$ with a suitable $C_p$?
For $n=2^k$ a power of $2$, this is easy: Just select $p=1/2$ and throw the (fair) coin $k$ times. All $n$ outcomes have equal probability $1/n$, so by labeling them $1, \ldots, n$, a $D_n$ can be simulated. Also, obviously, a $D_{2^k}$ cannot be simulated with less than $k$ throws, so the above way is in fact minimal.
For $n$ not a power of $2$, the first question is dealt with (and solved) in the November 2014 riddle of Michael Brand's site Using Your Head is Permitted. The second question, however, is far more tricky. The solution to the riddle shows that the minimum number of throws is bounded by the smallest number $k$ such that $$n \cdot \sum_{i=0}^k \left({k\choose i} \text{ mod }(n-1)\right)< 2^n.$$ (The sequence of these values of $k$ is in the OEIS as A251738.)
E.g., for $n=3$, the value for $k$ is $4$ since $$\begin{align} 3\cdot\sum_{i=0}^4 \left({4\choose i} \text{ mod }2\right)&=3\cdot\left((1\text{ mod }2)+(4\text{ mod }2)+(6\text{ mod }2)+(4\text{ mod }2)+(1\text{ mod }2)\right)\\ &=3\cdot(1+0+0+0+1)\\ &=6\\ &<8=2^3\text{, but }\\ 3\cdot\sum_{i=0}^3 \left({3\choose i} \text{ mod }2\right)&=3\cdot\left((1\text{ mod }2)+(3\text{ mod }2)+(3\text{ mod }2)+(1\text{ mod }2)\right)\\ &=3\cdot(1+1+1+1+1)\\ &=12\\ &>8=2^3\text{.}\\ \end{align}$$ The value $k=4$ is in fact also the minimum number of throws needed to simulate a $D_3$ by a $C_p$ (with a suitable $p$), but the proof is quite ugly since it involves several case distinctions. For larger values of $n$ that aren't powers of $2$, I have no clue whether the OEIS sequence A251738 is in fact the answer to question (2), even though I strongly suspect it is.
Does anyone know of a result that may help in proving or disproving my hypothesis?
