Simulate a 12-sided fair die with a 10-sided fair die

Question

If I have a single 10-sided fair die and I want to simulate a 12-sided fair die, what would be the most efficient way to do so?

Thus, we have to ensure that the likelihood of each result is equally likely.

Answer 1

Let the faces be labelled $0,\ldots,9$. Repeatedly roll the die $m$ times to form a decimal $\alpha=0.a_1a_2a_3\ldots a_m$ and say that the outcome is $\lfloor 12\alpha\rfloor$. The challenge is to make $m$ as small as possible. To do so, stop as soon as $\alpha\le x<\alpha+10^{-m}$ implies $\lfloor 12x\rfloor =\lfloor 12\alpha\rfloor$.

Answer 2

You could simulate a 12-sided die by rolling multiple times. Since $12 = 2 \cdot 2 \cdot 3$, you could do the following:

1. Throw a first time, result $r_1$ modulo 2. Throw a second time, result $r_2$ modulo 2. Throw a third time until you don't hit a 10, result $r_3$ modulo 3. Then set the result $r = 6 r_1 + 3 r_2 + r_3 + 1$. The expected number of rolls equals $2 + \frac{10}{9} \approx 3.11$.

2. Throw a first time until you don't hit a 7, 8, 9 or 10, result $r_1$ modulo 6. Throw a second time, result $r_2$ modulo 2. Then set the result $r = 2 r_1 + r_2 + 1$. The expected number of rolls equals $\frac{10}{6} + 1 \approx 2.67$.

3. Throw a first time until you don't hit a 9 or 10, result $r_1$ modulo 4. Throw a second time until you don't hit a 10, result $r_2$ modulo 3. Then set the result $r = 3 r_1 + r_2 + 1$. The expected number of rolls equals $\frac{10}{8} + \frac{10}{9} \approx 2.36$.

Answer 3

One of the first ideas that could come to mind is to roll the $10$-sided fair die twice. Substract $1$ to each result, you get two random integers from $0$ to $9$. Consider these as the digits of a single integer $n$ between $0$ and $99$. If $n\geqslant96$, start all over again. If $n\leqslant95$, divide $n$ by $12$, keep the rest, add $1$ to it. You are now contemplating a result of a $12$-sided fair die.

In this procedure, one starts all over again in $4$ cases from $100$ and each round uses two rolls of the $10$-sided fair die, thus, to get each (simulated) result of the $12$-sided fair die, one needs a mean number of $$\frac2{1-\frac4{100}}=\color{brown}{\bf 2.083}$$ rolls of the (real) $10$-sided fair die.

But one can do significantly better...

Roll the $10$-sided fair die $\color{red}{\bf 109}$ times. Substract $1$ to each result, you get $\color{red}{\bf 109}$ random integers from $0$ to $9$. Consider these $\color{red}{\bf 109}$ integers as the digits of a single integer $n$ between $0$ and $10^{\color{red}{\bf 109}}-1$. The base-$12$ expansion of $n$ is a number with at most $102$ base-$12$ "digits". If the leading base-$12$ "digit" is $1$, start all over again. Otherwise, the leading base-$12$ "digit" is $0$, that is, $n$ is a number with at most $\color{green}{\bf 101}$ base-$12$ "digits". Add $1$ to each of these $\color{green}{\bf 101}$ base-$12$ "digits". You are now contemplating $\color{green}{\bf 101}$ results of a $12$-sided fair die.

In this procedure, the chances to start all over again are $$1-\frac{12^{\color{green}{\bf 101}}}{10^{\color{red}{\bf 109}}}=0.62\%$$ (but see note 3 below), thus, to get a large number $N$ of (simulated) results of the $12$-sided fair die, one needs roughly $$\frac{\color{red}{\bf 109}}{\color{green}{\bf 101}}\cdot\frac{10^{\color{red}{\bf 109}}}{12^{\color{green}{\bf 101}}}=\color{purple}{\bf 1.086}$$ times $N$ rolls of the (real) $10$-sided fair die.

Note 1: Yes, the trick is that $12^{\color{green}{\bf 101}}=9.938\cdot10^{108}$ is only marginally smaller than $10^{\color{red}{\bf 109}}$, and the idea is simply to pick a power of $10$ very close to, and larger than, a power of $12$, to minimize the number of times one must start all over again.

Note 2: No, this procedure is not optimal since one could pick some higher power of $12$ smaller than, and even closer to, some higher power of $10$, and proceed likewise. This remark shows that there can be no optimal procedure because, for every $p<1$, there exists some integers $m$ and $n$ such that $$p\cdot10^n\leqslant12^m<10^n$$ (this is a standard consequence of the ergodicity of irrational rotations of the unit circle), thus, the procedure based on $n$ rolls of the $10$-sided fair die yields a new result of the $12$-sided fair die roughly every $$r=\frac{n}{p\cdot m}$$ rolls of the $10$-sided fair die. If $p$ is close to $1$ and if $n$ and $m$ are very large, then $$r\approx\frac{\ln(12)}{\ln(10)}=\color{blue}{\bf1.079}$$ which is thus the theoretical optimal efficiency one can approach but never reach.

Note 3: One could try to reach an even higher efficiency of the $\color{red}{\bf 109}$-throws-for-$\color{green}{\bf 101}$-results procedure described above, re-using the rounds producing a base-$12$ number with leading "digit" $1$ since each of these rounds produces a number uniformly distributed on $6.18\cdot10^{106}$ values. Decomposing these values into $10$ stacks of size $12^{98}=5.75\cdot10^{105}$, one could generate $98$ results of a $12$-sided fair die when falling in one of these stacks, and start all over again otherwise. But the gain in the mean number of (simulated) results of the $12$-sided fair die per result of the $10$-sided fair die is negligible.