Is there a way to simulate any $n$-sided die using a fixed set of die types for all $n$?

Question

I am assuming that we can increase the number of dice based on $n$, but they have to be $k$-sided, $k\ge3$.

When I say die types, I mean that we are allowed to use non-standard dice such as non-transitive dice, but we cannot create more die types as we increase $n$. i.e. we have a fixed set of dice from which we can choose from, and we can choose as many as necessary from this set for a given $n$, but we are restricted to choose from this set of dice.

Also, all numbers from $1$ to $n$ should be equally likely in our simulation.

Answer 1

Hint:

• You can simulate a $n$-sided die with only fair-coin throws (a biased coin would also work, but with more throws).
• Throw a coin $k = \lceil\log_2 n\rceil$ times and create a number $x$ in $\{0,1,\ldots, 2^k-1\}$.
• If $x+1 > n$ then repeat the previous bullet.
• The expected number of throws is $\Theta(\log n)$.

I hope this helps $\ddot\smile$

Answer 2

Do $0$ through $n-1$ rather than $1$ through $n$; it's a little easier to work through the arithmetic.

If you have a 10-sided die, you can simply roll it repeatedly to get the digits of the random number you're trying to generate. If the result gives you a number that's too big, you try again.

If you have a 6-sided die, then you can do the same thing, except you write numbers in base $6$ rather than base $10$, and so forth.

There are simplifications you can do: e.g. if you have a 10-sided die, you can use it as a five-sided die by simply reducing the result modulo $5$. This would also help if you're trying to simulate a $50$-sided die: roll it as a 10-sided die for the units digit, then as a 5-sided die for the tens digit.

A 12-sided die can work as a 4-sided die similarly, and so forth.