Use a k-sided die to generate integer in range [0 n] with the least number of throws.

Question

Given a fair $k$-sided die, with $k < n$, what is a generic method that allows me to generate a number in the range $[0...n]$ with the same probability and with the least amount of throws?

I have found many answer to similar specific questions, but I could not figure out a general method to achieve this.

Answer 1

It cannot be done unless every prime divisor of $n+1$ is a prime divisor of $k$.

That's because in $m$ tosses, there are $k^m$ possible outcomes, and an equal number of them must go to each of the $n+1$ values, $0,1,2,...,n$, which means that $k^m$ must be divisible by $n+1$. That's possible if and only if every prime divisor of $n+1$ is a divisor of $k$.

It is certainly possible to do it in $m$ tosses when $n+1$ is a divisor $k^m$. Take most intuitive algorithm is to take the $m$ numbers, $a_1,...,a_m$ from $0$ to $k-1$ and write them as a base $k$ number:

$$a_1+a_2k+a_3k^3+...+a_mk^{m-1}$$

then divide this number by $n+1$ and take the remainder.

Answer 2

Assuming that the numbers on the sides of the die are $\{1,2,3,\cdots,k\}$

First we will subtract one from every side so it becomes $\{0,1,2,\cdots,k-1\}$

Now we will throw the die $\lfloor \log_{k} (\frac{n}{k-1}) \rfloor + 1$ times, each time we will multiply its side subtract one with $k^{\lfloor \log_{k} (\frac{n}{k-1}) \rfloor + 1-j}$ where $j$ is from $0$ to$\lfloor \log_{k} (\frac{n}{k-1}) \rfloor + 1$,and then sum all the results together, so by this way we can generate any number between $0$ and $k^{j+1}-1$ inclusive (base $k$ representation).

note : if before throwing the die the sum is less than $n$ and after throwing the side the sum is bigger than $n$ then we will not include it and throw it again(its guaranteed to produces numbers between $[0,n]$ with fair (equal probability to each number), the only down side is that you sometimes need to throw more than once to reach a valid side.

Example : for given $k=3$ and $n=17$ so the sides of the die are numerated from $0$ to $2$, also $\lfloor \log_3 \frac{17}{2} \rfloor +1 =2$ ,so we start by throwing the die and it land on $2$ but since $2*3^2$ is bigger than $17$ so we throw it again and landed on $0$ now the sum is $0*3^2$ so its 0 which is less than 17(good) now we throw it again and we land at $1$ so its equal to $1*3^1$ which is equal to 3 and its less than 17 and finally we throw it again and it land on $2$ so its $2*3^0$ and the sum is $3+2=5$ which is less than 17.

so we generate $5$ randomly with $3$ sided die and it must be less or equal to 17.

to sum it up (all that i did is representing $n$ in base $k$) so if you don't understand the answer, read about base $b$ representation in Wikipedia.

also i would like to see someone who could overcome the re-throwing problem in my solution!

i hope you see what you are looking for.