Generating a random number using a fair die

We're given a fair die and we were asked to find a way to randomly get a number $r$ such that $0\leq r<n$, where $n$ is arbitrary positive integer.

When $n=5$, the way to generate a random number is by simply rolling the dice once, if the result $s$ is in $\{1,2,3,4,5 \}$, then we compute $s-1$ and get our random number. Otherwise, if $s=6$, we roll again.

From what I've been able to observe, $n=5$ is the smallest $n$ for which there is no maximum on the number of throws (i.e if we keep getting unlucky and we keep getting $6$'s when throwing the die).

After doing a couple of internet searches, I've been able to find that this is due to the fact that 5 is the smallest integer that has a prime factor that does not divide 6, and that in general, when using a fair die, a maximum number of rolls can only be guaranteed if and only if $n$ has only factors $2$ or $3$.

I don't understand how the fact that $5$ does not divide $6$ influences my original experiment. Also, how come that if $n$ has only $2$'s or $3$'s as prime factors, then then there is always a maximum on the number of throws?

• With $n$ throws of a fair die the possible outcomes are $6^n$. If $m$ is not a divisor of $6^n$, it is impossible to simulate a uniform distribution over $[1,m]$. – Jack D'Aurizio Jan 8 '18 at 12:30
• @JackD'Aurizio Thank you I got it. – Skyris Jan 8 '18 at 12:34

Your research is right. Using a fair six-sided die we can make a random number, uniformly distributed, in the range $0\leq r<n$ for any $n$ of the form $2^a\cdot 3^b$ in a guaranteed finite number of throws. I'll do $24 = 2^3\cdot 3$ as an example, and you should be able to adapt it to any number.

First off, $24$ is divisible by $6$, so let's make $6$ uniform sets $$0, 1, 2, 3\\4, 5, 6, 7\\8, 9, 10, 11\\12, 13, 14, 15\\16, 17, 18, 19\\20, 21, 22, 23$$and throw a die to decide which one of them we land in, for instance letting a $1$ on the die correspond to the first row, and so on.

Let's say we threw a $3$. That means we now have the four numbers $8, 9, 10, 11$, that are still available as our $r$. Four is divisible by $2$, so we divide this set into two groups. For instance $8, 9$ in one and $10, 11$ in the other. Now throw a die, and if the result was a $1, 2$ or $3$, go with the first, and if the result was $4, 5$ or $6$ go with the second. Finally, do the same thing to decide between the two final numbers.

If $n$ has a prime factor that isn't a factor of the number of sides on our die, then we can't split into uniform categories in a way that makes every side on the die correspond to a category. We can still get a uniform distribution, but we're not guaranteed to get a result, and we must therefore be prepared to repeat the entire thing, possibly indefinitely.

For instance, if $n = 23$, we can do the above thing, but if the result is $r = 23$, we will have to do it all over again. Similarily if $n$ has $23$ as a factor, and you divide into $23$ categories, and have to choose one of them, you follow the same strategy as above, only instead of the result being $r$, the result is which of the $23$ categories you then continue to split.

As for what division into categories is fastest (not to mention what you mean by "fastest"), that's a totally different question. I know you can do the $24$ example in two throws two thirds of the time and three throws the rest of the time: in the second throw, instead of letting the categories be $8, 9, 10, 11$, we can let the categories be $8, 9, 10, 11, \{8,9\}, \{10,11\}$, and throw a single die to decide between those six. Is this the fastest? I don't know.

• You can look at this the other way around in your example. You are allocating $216$ possibilities equally amongst $24$ options. That makes nine each. You can allocate six possibilities with the first two throws equal to each of the $24$ options. That gets you two thirds in two throws, and you clearly can't do better. Then however the others are allocated they will identify the outcome on the third throw. – Mark Bennet Jan 8 '18 at 13:51