1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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]$. $\endgroup$ – Jack D'Aurizio Jan 8 '18 at 12:30
  • $\begingroup$ @JackD'Aurizio Thank you I got it. $\endgroup$ – Skyris Jan 8 '18 at 12:34
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Mark Bennet Jan 8 '18 at 13:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.