Is it possible to simulate a d20 roll using smaller dice?

Question

I'm wondering if it's possible to simulate a d20 using smaller dice, and if so, how would one figure out how many you would need?

This question provides an algorithm to do so using 2 coins with p = 1/2 and p = 1/n, but is there an algorithm that would work for multiple like dice of the same probability? eg. can you find an x such that if you roll x 6 sided dice you are left with exactly 20 distinct outcomes?

Answer 1

If you aim for a fixed number $x$ of dice, I agree with the comment of Thomas Andrews that the product of the numbers of their sides has to be a multiple of $20$. However, if the number $x$ may vary, then this algorithm provides a solution:

1. Roll a 6-sided die with outcome $\omega_1$. Set $a_1=0$, if $\omega_1\in\{1,2,3\}$, and $a_1=10$ otherwise.

2. Roll a 6-sided die with outcome $\omega_2$. Set $a_2=0$, if $\omega_2\in\{1,2,3\}$, and $a_2=5$ otherwise.

3. Roll a 6-sided die with outcome $\omega_3$. Set $a_3=\omega_3$, if $\omega_3\in\{1,2,3,4,5\}$. If $\omega_3 = 6$ repeat step 3.

Eventually, the algorithm will terminate and $a = a_1 + a_2 + a_3$ will be uniformly distributed in $\{1,\dots,20\}$.

Answer 2

For what it's worth, you can use a single $(6)$ sided die (or one red die and one green one) to fairly simulate a $(19)$ sided die, as follows:

Roll the die until you get a number less than $(6)$. Denote the satisfying roll as $(r_1)$. Then roll the die again until you get less than $(5)$. Denote this roll as $(r_2)$. Then compute $T_1 = [4 \times (r_1 - 1)] + (r_2)$. As has already been discussed, $T_1$ is equally likely to be assigned any of the numbers in $\{1,2,\cdots, 20\}.$

Now, repeat the exact same procedure, computing $T_2$. If $T_2 = T_1$, reject $T_2$ and compute $T_2$ from scratch. Finally, once $T_2 \neq T_1$, for $T_2 > T_1$, set $T_2 = T_2 - 1.$

Note that the objection that it theoretically could take an unbounded number of rolls until $T_2$ is determined also applies to the original procedure of emulating a $(20)$ sided die. That is, it theoretically could take an unbounded number of rolls until you roll $< (6)$.

To verify that this procedure works, the case of $T_1 = 1$ or $T_1 = 20$ is trivial.

Consider 1 < $T_1 < 20$. Then, consider the computation of $T_2$, once $T_2 \neq T_1$, and before $T_2$ is adjusted to ($T_2 - 1 ~:~$ if necessary). The $(19)$ possible values of $T_2$ represented by $\{1,\cdots, (T_1 - 1), (T_1 + 1), \cdots, 20\}$ are equally likely. This is because $T_1$ was computed at random.

Then, the final computation of $T_2$ will be represented by shifting $\{(T_1 + 1), \cdots, 20\}$ down $(1)$ if the unadjusted value of $T_2$ happened to be $> T_1$.