Just for fun, I am trying to find a good method to generate a random number between 1 and 10 (uniformly) with an unbiased six-sided die.

I found a way, but it may requires a lot of steps before getting the number, so I was wondering if there are more efficient methods.

My method:

  1. Throw the die and call the result $n$. If $1\leq n\leq 3$ your number will be between $1$ and $5$ and if $4\leq n\leq 6$ your number will be between $6$ and $10$. Hence, we reduced to the problem of generating a random number between $1$ and $5$.
  2. Now, to get a number between $1$ and $5$, throw the die five times. If the $i$th throw got the largest result, take your number to be $i$. If there is no largest result, start again until there is.

The problem is that although the probability that there will eventually be a largest result is $1$, it might take a while before getting it.

Is there a more efficient way that requires only some fixed number of steps? Edit: Or if not possible, a method with a smaller expected number of rolls?

  • 9
    Since $6$ is not divisible by all the factors of $10$, there is no such method, but one can still ask for the method whose expected number of rolls required to produce a number is as small as possible. – Travis Jun 6 '15 at 12:36
  • 4
    Of course, I'd rather just buy a D10. – Travis Jun 6 '15 at 12:37
  • 4
    Indeed, throwing the dice $n$ times yields $6^n$ equiprobable results, whose set cannot be partitioned into $10$ subsets of the same size since $10$ does not divide $6^n$. – Did Jun 6 '15 at 12:37
  • 13
    For 2., roll one die once. If a "6" results, roll again? – David Mitra Jun 6 '15 at 12:39
  • 3
    Go to gaming shop. "Hello, I'd like a 1d10, would you take this lovely 1d6 in part exchange?" :) – Julia Hayward Jun 8 '15 at 15:17

21 Answers 21

You may throw the die many ($N$) times, take the sum of the outcomes and consider the residue class $\pmod{10}$. The distribution on $[1,10]$ gets closer and closer to a uniform distribution as $N$ increases.


You may throw the die once to decide if the final outcome will be even or odd, then throw it again until it gives an outcome different from six, that fixes the residue class $\pmod{5}$. In such a way you generate a uniform distribution over $[1,10]$ with $\frac{11}{5}=\color{red}{2.2}$ tosses, in average.


If you are allowed to throw the die in a wedge, you may label the edges of the die with the numbers in $[1,10]$ and mark two opposite edges as "reroll". In such a way you save exactly one toss, and need just $\color{red}{1.2}$ tosses, in average.


Obviously, if you are allowed to throw the die in decagonal glass you don't even need the die, but in such a case the lateral thinking spree ends with just $\color{red}{1}$ toss. Not much different from buying a D10, as Travis suggested.


At last, just for fun: look at the die, without throwing it. Then look at your clock, the last digit of the seconds. Add one. $\color{red}{0}$ tosses.

  • Could you explain why this is uniform and how to compute the expected number of tosses? – P.A. Jun 6 '15 at 12:54
  • 3
    @P.A. This algorithm gives a uniform distribution over $\mathbb{Z}_2\times\mathbb{Z}_5\simeq\mathbb{Z}_{10}$, and the expected number of tosses is given by: $$1+\sum_{n\geq 1}\frac{5n}{6^n}.$$ – Jack D'Aurizio Jun 6 '15 at 12:56
  • 3
    It is uniform as any even number has equal probability, conditioned on the first toss saying "even"; same for odd numbers (conditioned on the first toss saying "odd"). Now, the first coin toss has equal probability of saying "even" or "odd", so overall all outcomes have equal probability. – Clement C. Jun 6 '15 at 12:58
  • 5
    For the expected number of tosses: you always pay the first toss; then, a "unit operation" is one coin toss, and succeeds with probability $\frac{5}{6}$ (it fails only when getting a $6$, in which case one has to make another attempt with this "unit operation"). The number of times this unit operation must be repeated before success is then a geometric random variable, and its expectation is $\frac{6}{5}$. Therefore, the total is $$1+\frac{6}{5} = \frac{11}{5}$$. – Clement C. Jun 6 '15 at 12:59
  • @JackD'Aurizio Incidentally, this method actually uses the minimum possible number of die rolls. Specifically, since $6^n\equiv 6\;(\text{mod }10)$, there's always $6$ possibilities out of $6^n$ left over after $n$ rolls, so there's always at least a $6/6^n = 1/6^{n-1}$ probability that you have to roll $n+1$ dice. – Jim Belk Jun 7 '15 at 15:19
up vote 35 down vote
+100

Write out the base-$6$ decimals of $\frac{0}{10}$ through $\frac{10}{10}$.

$$\begin{array}{cc} \frac{0}{10} & = 0.00000000\dots\\ \frac{1}{10} & = 0.03333333\dots\\ \frac{2}{10} & = 0.11111111\dots\\ \frac{3}{10} & = 0.14444444\dots\\ \frac{4}{10} & = 0.22222222\dots\\ \frac{5}{10} & = 0.30000000\dots\\ \frac{6}{10} & = 0.33333333\dots\\ \frac{7}{10} & = 0.41111111\dots\\ \frac{8}{10} & = 0.44444444\dots\\ \frac{9}{10} & = 0.52222222\dots\\ \frac{10}{10} & = 1.00000000\dots\\ \end{array}$$

Treat rolls of a $6$ as a $0$. As you roll your $6$-sided die, you are generating digits of a base-$6$ decimal number, uniformly distributed between $0$ and $1$. There are $10$ gaps in between the fractions for $\frac{x}{10}$, corresponding to the $10$ uniformly random outcomes you are looking for. You know which outcome you are generating as soon as you know which gap the random number will be in.

This is kind of annoying to do. Here's an equivalent algorithm:

Roll a die $$\begin{array}{c|c} 1 & A(0,1)\\ 2 & B(1,2,3)\\ 3 & A(4,3)\\ 4 & A(5,6)\\ 5 & B(6,7,8)\\ 6 & A(9,8)\\ \end{array}$$ $A(x,y)$: Roll a die $$\begin{array}{c|c} 1,2,3 & x\\ 4 & A(x,y)\\ 5,6 & y\\ \end{array}$$ $B(x,y,z)$: Roll a die $$\begin{array}{c|c} 1 & x\\ 2 & C(x,y)\\ 3,4 & y\\ 5 & C(z,y)\\ 6 & z\\ \end{array}$$ $C(x,y)$: Roll a die $$\begin{array}{c|c} 1 & x\\ 2 & C(x,y)\\ 3,4,5,6 & y\\ \end{array}$$

One sees that:

  • $A(x,y)$ returns $x$ with probability $\frac35$ and $y$ with probability $\frac25$.
  • $B(x,y,z)$ returns $x$ with probability $\frac15$, $y$ with probability $\frac35$, and $z$ with probability $\frac15$.
  • $C(x,y)$ returns $x$ with probability $\frac15$ and $y$ with probability $\frac45$.

Overall, it produces the $10$ outcomes each with $\frac1{10}$ probability.

Procedures $A$ and $C$ are expected to require $\frac65$ rolls. Procedure $B$ is expected to require $\frac23 \cdot 1 + \frac13 (1 + E(C)) = \frac75$ rolls. So the main procedure is expected to require $\frac23 (1 + E(A)) + \frac13(1 + E(B)) = \frac{34}{15} = 2.2\overline{6}$ rolls.

  • 2
    Quite explicit, which is nice, +1. One could add a computation of the expected number of rolls needed to get one 1-10 outcome. – Did Jun 7 '15 at 12:06
  • Which might be $$\frac{34}{15}=2.2667.$$ – Did Jun 7 '15 at 12:09
  • 4
    It looks strange that this efficient method requires more tosses, in average, than my naive method to choose the parity, then the residue class $\pmod{5}$ by rerolling every $6$. – Jack D'Aurizio Jun 7 '15 at 17:30
  • 2
    The $B$ procedure is somehow slightly inefficient. $\frac16$ of the time it should delegate to itself, instead of delegating to another procedure with $\frac65$ expected rolls $\frac13$ of the time. That would reduce its expected time from $\frac76$ to $\frac65$. But modifying it that way would obscure the relationship to the base-6 decimals. – NovaDenizen Jun 7 '15 at 17:52
  • 1
    It's interesting to compare this answer with the one by MJD. – David K Jun 7 '15 at 20:26

Here is an alternative method, rather different from the ones described earlier, and the only one which approaches the maximum theoretical efficiency.

Let $a=0 $ and $b=10$. We are going to imagine that these describe the set of real numbers between 0 and 10, including 0 but not including 10, which we write as $[0,10)$. Each die roll narrows the set, and when the set is narrow enough, we have our answer.

The procedure for narrowing down the interval is as follows:

  1. Roll a die, producing an integer $d$ between 1 and 6.
  2. Cut the interval $[a, b)$ into six equal parts and choose the $d$th part, throwing away the rest:
    1. $\ell \leftarrow \frac16(b-a)\quad$ (the interval had length $b-a$ before; $\ell$ is one-sixth of this size)
    2. $a \leftarrow a + (d-1)\ell$
    3. $b\leftarrow a+\ell\quad$ (the new interval now has length $\ell$)
  3. If at this point the integer parts of $a$ and $b$ are the same, then the result is that integer part; stop. If not, return to step 1. (We write the integer part of $x$ as $\lfloor x \rfloor$.)

For example, let's see what happens when we throw 3, then 5.

$$\def\db#1{\color{darkblue}{#1}}\begin{array}{ccc|cccc|c} [a, b) & \db\ell & \text{roll} & \text{new } a & \text{new } b & \lfloor a\rfloor & \lfloor b \rfloor & \lfloor a\rfloor = \lfloor b \rfloor \\\hline [0,10)&\db{\frac{10}6} & 3 & 0 + 2\cdot\db\ell = \frac{20}{6} & \frac{20}{6} + \db{\frac{10}6} = \frac{30}6 & 3 & 5 & \text{no} \\ \left[\frac{20}{6},\frac{30}6\right) & \db{\frac{10}{36}}& 5 & \frac{20}6 + 4\cdot\db\ell = \frac{160}{36}& \frac{160}{36} + \db{\frac{10}{36}} = \frac{170}{36} & 4 & 4 & \text{yes} \end{array} $$

The integer parts at the end are both 4, so the result is 4. This time the result took only 2 throws, but it can take more:

$$\begin{array}{ccc|cccc|c} [a, b) & \db\ell & \text{roll} & \text{new } a & \text{new } b & \lfloor a\rfloor & \lfloor b \rfloor & \lfloor a\rfloor = \lfloor b \rfloor\\\hline [0,10)&\db{\frac{10}6} & 5 & 0 + 4\cdot\db\ell = \frac{40}{6} & \frac{40}6 + \db{\frac{10}6} = \frac{50}6 & 6 & 8 & \text{no} \\ \left[\frac{40}6,\frac{50}6\right)&\db{\frac{10}{36}} & 2 & \frac{40}6 + 1\cdot\db\ell = \frac{250}{36} & \frac{250}{36} + \db{\frac{10}{36}} = \frac{260}{36} & 6 & 7 & \text{no} \\ \left[\frac{250}{36},\frac{260}{36}\right)&\db{\frac{10}{216}} & 2 & \frac{250}{36} + 1\cdot\db\ell = \frac{1510}{216} & \frac{1510}{216} + \db{\frac{10}{216}} = \frac{1520}{216} & 6 & 7 & \text{no} \\ \left[\frac{1510}{216},\frac{1520}{2166}\right)&\db{\frac{10}{1296}} & 6 & \frac{1510}{216} + 5\cdot\db\ell = \frac{9110}{1216} & \frac{9110}{1296} + \db{\frac{10}{1296}} = \frac{9120}{1296} & 7 & 7 & \text{yes} \\ \end{array} $$

Had we rolled another 2 at the end instead of a 6, we would still have had $\lfloor a\rfloor = 6$ and $\lfloor b\rfloor = 7$ and we would have had to continue. Any other roll, such as the 6 we actually got, would stop the process.

What is happening here is that we imagine we are choosing a real number from $[0,10)$, and we will then throw away the fraction part of this real number. Each die roll determines a base-6 digit from $\{0,1,2,3,4,5\}$. The sequence of digits rolled can be concatenated together with a fractional point to produce the base-6 version of a decimal fraction between 0 and 1. If we convert this fraction to base 10, then take its tenths-place digit, we will have the uniformly distributed result we want.

The calculations with $[a,b)$ are keeping track of our uncertainty in the real number we are generating from die rolls. To generate the entire real number, we would have to roll the die forever, But we don't need the entire real number. Rolling a die narrows down the interval of uncertainty by a factor of 6; the interval becomes $\frac 16$ as wide. (This is what $\ell$ is tracking.) When the interval has shrunk sufficiently, it is likely to lie entirely within an interval $[0.p000\ldots, 0.p999\ldots)$ and at that point we know the tenths-place digit, which is all we need.

We can't guarantee to bound the number of die rolls in advance (no method can, as explained in the comments) but for producing large numbers of digits, this method produces results with the theoretically optimal average number of rolls, which is $$\frac{\log 10}{\log 6} \approx 1.2851,$$ far better than any of the methods described elsewhere in this thread. For generating a single decimal digit, we still need at least two rolls. But suppose we want to generate 10 decimal digits. In that case instead of stopping when $a $ and $b$ agree in their first decimal place, we stop when they agree to 10 decimal places. This takes, on average, a bit more than $10\frac{\log 10}{\log 6} $ rolls, say around 13 or 14. For example, suppose we roll $1,5,3,5,4,2,2,6,6,2,4,5,3,1$. This narrows down $[a,b)$ to $$\left[\frac{9707055060}{78364164096}, \frac{9707055070}{78364164096}\right) \approx \left[.1238710981, .1238710982\right)$$ so our 14 rolls have in this case generated 8 decimal digits $1\,2\,3\,8\,7\,1\,0\,9\,8$ (and almost a ninth, which is either 1 or 2), an efficiency of greater than $\frac{14}8=1.75$ rolls per digit.

  • 1
    I think your result $\log_6 10$ is not correct. Your process terminates after $x \geq 2$ rolls since the interval size after first roll is $> 1$. Thus the expectation should be $\geq 2$. – PSPACEhard Jun 6 '15 at 14:56
  • Thanks. I have clarified that the $\log_6 10$ result is correct if one uses the method to generate more than one digit at a time. $\log_6 10$ is easily seen to be correct on information-theoretic grounds: Each die produces $\log_2 6$ bits of information, and each decimal digit consumes $\log_2 10$ bits of information. So an optimal method requires $\frac{\log_2 10}{\log_2 6}$ rolls per digit, and Hamming's theorem tells us that we can approach this limit arbitrarily closely. – MJD Jun 6 '15 at 15:23
  • 1
    Note that since $\log_6 10$ rolls are required per decimal digit, but fractional rolls do not make sense, the minimum number of rolls required to generate $n$ decimal digits is then $\lceil n\log_6 10\rceil$. For $n=1$ this does give the correct lower bound, 2. – MJD Jun 6 '15 at 18:39
  • 2
    With a little of lateral thinking (i.e. exploiting the fact that a cube has twelve edges) it is also possible to break the $1.2851\ldots$ barrier. – Jack D'Aurizio Jun 7 '15 at 15:50
  • It would be nice to add to the the expected number of rolls to generate a single value. – Michael Anderson Jun 18 '15 at 3:02

Purely FTR. I believe (in a, let's say, marketing sense),

the most simple, understandable method is this:

Roll once: odd means it's a number 1-5, even means it's a number 6-10.

Roll again: very simply, if you get a six ignore that and keep rolling until you get a not-six.

You have your answer.

Note that in any, say, casino or similar setting - even just a board game with kids -

this is the only approach that is so understandable (to non-mathematicians) that it's the way to go.

It's worth remembering that only one person in a gazillion understands distributions: I bet that out of 1000 adults, only maybe 1 (if that) would understand that rolling two dice does not give you "a 'random' number between 1 and 12!" {Yes, I meant to type 1, not 2 :-) }

BTW a number of other people have mentioned this approach in comments or answers. Here, I have specifically spelled out the actual raison d'etre (because it is understandable to the layman.)

For serious mathematicians on here, it's an interesting point to put that in to your thinking mix: if you were, as it were, working for Hasbro, a casino, or perhaps making "app" games, any complex ideas would be dismissed out of hand. So it's a bit like finding a proof that is not only strong .. but elegant.

The interesting challenge here is to find the most "understandable" way to do it.

{Just FTR a detail, in step "1" I choose odd/even rather than 123-456, because, I believe it's more "catchy" and, really, simpler to understand.}

A catchy name for this whole procedure would probably be the:

"add five" ..

ie, in step two just "add five" if the first key roll was even. add five!

"How the hell can we roll a number to ten with this dice? Hey man, do the "add five" thing!"

Nobody would riffle shuffle if it didn't have a catchy name :)


Footnote. I was thinking about this. Regarding this "add five" method. It might actually be preferable for most humans, if you did it the other way around - so, do the 1-5 roll first.

So picture this then, you say to your kids: "ok, we're going to do an 'add five' kids, since we need a number up to ten!" "Oh boy, Mom!". First you roll for 1 through 5. (Unfortunately with the nuisance of discarding any 6s.) Then you declare - "Wow, a 2! What does that mean kids?!" "Alright! It's either 2 or 7, right Mom?!" "Right! And now how do we ....... " (they all interject) "WE ROLL AN ODD OR AN EVEN!"

The excitement is now palpable.

You roll for the odd/even, and the various age groups scream (littlest kid:) "Wow, a two . that's even right Stevie?!" (next kid:) "Even, I knew it!" (Big sister:) "That means eight!"

I mean this is better than, you know, taking everyone to ride Pirates of the Caribbean when it's running backwards.

Note that it contains the absolutely critical elements of minor/gentle pedagogy (could be the first time your kid learns about parity, say) and is an excellent example of rule-and-step following (indeed, those two pedagogic devices are, perhaps, the entire raison d'etre of jeux d'societe, card and board games.)

So anyway (a) it would take some consumer testing but I think it adds a certain frisson to do the 1-5 roll first. and (b) I'd really like to think of an even MORE elegant system .. in particular I'm troubled by the "discard sixes" step. Who knows, maybe someone will think of a way around that.

  • Yes. This was my first thought, too. Many of the schemes suggested on here leave me thinking, Hmm, I'd have to work out the probabilities on this, whether that would really give the desired result. This is simple and obviously correct. – Jay Jun 8 '15 at 14:03
  • You know it's my "catchy name" that clinches the deal :) But for me it was an interesting insight that the, let's say, pan-logical stuff you have to do in thinking up a "marketing" "pop song" approach to something, is, in a sense not unlike finding an elegant proof in math: an elegant versus long-winded correct proof are equally rigorous, but in math it's great when a simple, elegant proof comes along for something that previously had only a long-winded proof. For me that's kind of the challenge here. indeed, I've been trying to think of a "more simpler", "more catchy" way to do it! – Fattie Jun 9 '15 at 3:43
  • Did you mean 2-12 with the 2 dices? Also shouldn't the kids be saying "it's either 2 or 7"? – 355durch113 Aug 25 '15 at 17:25
  • Ah thanks for the typo check! 2 or 7 indeed :) I meant 1-12 because, I fear, most people are so unthinking that they'd assume without too much thought you can roll a 1 through 12 with two dice :) – Fattie Aug 26 '15 at 10:26
  • I like this as is explainable, you could probably feed your discarded sixes, and the other bits of discarded entropy from the even / odd roll to another random number generation algorithm (as long as it remained unrelatable to the first result). I'd do this calculation on paper, and call it the efficiency troll. – daniel Apr 20 '17 at 12:19
  1. Roll a d6. Now you have a random number in $[1;6]$, in level distribution.
  2. Roll a d6 again. If the result is odd, add 6 to the previous result. Now you have a random number in $[1;12]$, in level distribution.
  3. If the result is 11 or 12, then restart the whole process agan (from 1).
  4. If you are here, now you have a random number in $[1;10]$, in level distribution.

P.s. Yes, it is a level distribution. See the comments below.

  • 1
    That's not a level distribution. You have a higher probability of generating 1-6 than of generating 7-10. – Mike Scott Jun 7 '15 at 19:55
  • 3
    @MikeScott If you want a uniform distribution from 1 to 10, you should have a higher probability of generating 1-6 than 7-10: in fact, the odds should be $60:40$. Which in fact is exactly what this procedure accomplishes. – David K Jun 7 '15 at 20:13
  • 1
    @DavidK Yes, you're right and I was wrong. I didn't like the asymmetry, and jumped to incorrect conclusions. – Mike Scott Jun 7 '15 at 20:22
  • @DavidK Could you please explain why that is the case? If you have a uniform distribution shouldn't each of the numbers have equal probability? – 1110101001 Jun 8 '15 at 1:31
  • 2
    @1110101001 Of course all numbers have equal probability, but the probability of rolling a number in the set $\{1,2\}$ is twice the probability of rolling a 1. You are more likely to roll something in the set $\{1,2,3,4,5,6\}$ than to roll something in the set $\{7,8,9,10\}$ because there are six equally likely ways to get the first set but only four ways to get the second set. – David K Jun 8 '15 at 2:11

Roll the die. One of the sides will be facing between 0 and 90 degrees to the right of due north. Divide that angle by 9 (ty,DRF), rounding up.

  • 2
    If you're rounding up you only get a number between 1 and 9 – DRF Jun 7 '15 at 11:21
  • @DRF No, you get a number between 1 and 10. Anything above 81 degrees will round up to 10. – Mike Scott Jun 7 '15 at 19:50
  • 1
    @mikescott yes in the edited version you do:) – DRF Jun 7 '15 at 20:05
  • Before, it read "Divide that angle by 10, rounding up." My brain had confused number of segments with denominator. – Chronocide Jun 11 '15 at 8:38
  1. Roll the die to decide high/low. If you get 1-3 do step (2) for 1,2,3,4,5. If you get 4-6, do step (2) for 6,7,8,9,10

  2. Roll the die to choose a number. 1,2,3,4,5 correspond to 1,2,3,4,5 if low and to 6,7,8,9,10 if high. If you roll a 6, redo (2)

Roll the dice in pairs to generate pairs. Doubles don't count and are rerolled. A roll of 1–2, 1–3, or 1–4 is the digit 0. A roll of 1–5, 1–6, or 2–1 is the digit 1. A roll of 2–3, 2–4, or 2–5 is the digit 2. And so on up to digit 9, which is a roll of 6–3, 6–4, or 6–5.

(This method is not optimal; it has the same performance as Jack D'Aurizio's method, requiring (on average) 2.4 (not 2.2) die throws per decimal digit.)

I found this method by applying a more general method, which may be instructive. Suppose we throw two dice. There are 36 possible outcomes. We can tabulate these 36 outcomes and assign 3 outcomes to each decimal digit, by simply assigning the numbers from 0 through 9 to outcomes any way we want. We will then have 6 of 36 outcomes left over, and we mark these as "roll again", shown below as an “$X$”. One possible assignment (described above) is:

$$\begin{array}{c|cccccc} & 1 & 2 & 3 & 4 & 5 & 6 \\ \hline 1 & X & 0 & 0 & 0 & 1 & 1 \\ 2 & 1 & X & 2 & 2 & 2 & 3 \\ 3 & 3 & 3 & X & 4 & 4 & 4 \\ 4 & 5 & 5 & 5 & X & 6 & 6 \\ 5 & 6 & 7 & 7 & 7 & X & 8 \\ 6 & 8 & 8 & 9 & 9 & 9 & X \end{array} $$

Another, (similar to the one) described by Jack D'Aurizio, is:

$$ $$\begin{array}{c|cccccc} & 1 & 2 & 3 & 4 & 5 & 6 \\ \hline 1 & 1 & 2 & 3 & 4 & 5 & X \\ 2 & 1 & 2 & 3 & 4 & 5 & X \\ 3 & 1 & 2 & 3 & 4 & 5 & X \\ 4 & 6 & 7 & 8 & 9 & 0 & X \\ 5 & 6 & 7 & 8 & 9 & 0 & X \\ 6 & 6 & 7 & 8 & 9 & 0 & X \\ \end{array}

Any assignment of 0–9 to 30 of the 36 outcomes will work and will produce a method for generating (on average) 1 decimal digit per $2\cdot\frac{36}{30}=2.4$ die throws.

We can extend this method. There are $6\cdot6\cdot 6=216$ possible outcomes of throwing three dice. If we assign 2 of these outcomes to each of 00—99, and mark the remaining 16 as "reroll", we get another method, this time one that produces (on average) 2 decimal digits per $3\cdot \frac{216}{200}$ throws, or 1 digit per $\frac{81}{50} = 1.62$ throws, a significant improvement, much closer to the theoretical optimum of $$\frac{\log 10}{\log 6} \approx 1.2851$$ throws per digit.

  • 1
    To check my understanding and help with the original (edited) question's goal: this results on an expected number of tosses of $2.4$, not $2.2$, is that correct? (each unit operation requires two tosses, and is successful with probability $\frac{5}{6}$). – Clement C. Jun 6 '15 at 12:47
  • Correct. Jack D'Aurizio's calculation of $\frac{11}5$ is mistaken; it actually requires $\frac{12}5$. – MJD Jun 6 '15 at 13:05
  • 4
    I believe his calculation is correct: the first parity-deciding die toss made in his approach need not be repeated, so the total number of tosses is $1+X$ with $X$ being a geometric distribution with parameter $\frac{5}{6}$. In your approach, however, each "independent unit" requires two coin tosses, so the overall number of repetitions turns out to be $2X$. – Clement C. Jun 6 '15 at 13:07
  • That's a good point, thanks. – MJD Jun 6 '15 at 13:48

Why don't you just roll it N times (pick the N you want for the number of random digits base 6). For each roll, subtract 1 from the result (so you get a digit from 0-5 instead of 1-6), and write the results down in order. For example, if N = 10, so you roll 5 times, you might get a number like: 4301205223.

Consider this as a number base 6. Convert it to base 10, and that gives you number between 0 and 6N. If you want to normalize this to a number between 0 and 1, just divide by 6N.

  • Maybe a number between zero and $6^{\color{red}{N}}$. It is the same method of MJD, anyway. – Jack D'Aurizio Jun 7 '15 at 15:55
  • +1 as it is much more concisely expressed than MJD's answer. – Tad Jun 9 '15 at 4:40

going back to the original poster's idea.

Roll 1 dice, 1,2,3 means 1 to 5, 4,5,6, means 6 to 10 so now we need a D5.

Just roll the dice until a number from 1 to 5 comes. i.e. reroll on a 6. The expected number of throws is low.

  • Can't understand why this was downvoted, as it is exactly the same solution as Joe Blow's. – mweiss Jun 8 '15 at 14:24
  • his was downvoted too. I upvoted his. However, I am mystified about why either was downvoted. The solution is short, accurate and good. – Mark Joshi Jun 8 '15 at 21:47

@Jack D'Aurizio suggested throwing the die in a wedge, glass, etc.

If you can throw the die so that it always lands occupying exactly the same square on the table, then you can get more information from a die throw than just the number showing on top: you can also see what number is showing on the face closest to the thrower (or certain designated direction).

Actually, most of the time you can still determine this "closest face" even under regular conditions. Let's assume that the thrower can always detect both which face is up and which face is closest to the thrower, and let's call those faces "top" and "South", respectively.

Then each throw yields not just $6$ but $24$ separate possible outcomes, all equally likely. For example, a $1$ on top may be paired with a $2, 3, 4$, or $5$ on the South face (though not with a $6$ since the $1$ and $6$ are on opposite faces on a standard die). Labeling those $24$ outcomes by the numbers $1$ through $24$, we now effectively have a $24$-sided die.

With our $24$-sided die, we can simulate a $10$-sided die by just taking the result mod $10$ (discard the $10$'s digit and have $0$ mean $10$ if you like), except you have to reroll if the result is $21$ or higher: a $4/24 = 1/6$ chance of rerolling. The expected number of rolls, $E$, using this method is thus calculated by $$ E = (5/6)(1) + (1/6)(1+E), $$ so $E = 1.2$, exactly $1$ roll better than in @Jack D'Aurizio's answer.

For readers interested in group theory, we have just seen that the group of rigid symmetries of a cube must have $24$ elements. Indeed this group is isomorphic to $S_4$ (although you don't need that for this problem). See also: Proof that cube has 24 rotational symmetries

I think Joe Blow's answer is the best one, but here's another:

Draw 10 boxes of equal size on sheet of cardboard. Number them from 1 to 10. Roll the die so that it lands on this cardboard. Take the number of the box that it lands in. Disregard the number showing on the die.

Addendum

It occurs to me that, as the prime factors of 6 are 2 and 3, while the prime factors of 10 are 2 and 5, that therefore there is no finite number of rolls of a D6 that can possibly give an equal probability of 10 different outcomes. There's just no way to multiply 2's and 3's and come up with a multiple of 10. So any solution must rely on either: (a) An infinite series that will converge on a power of 10; or (b) Ignoring some values and re-rolling. Either way, you can set up a system where in practice you'll get an answer after a reasonable number of rolls, but in principle, it is always possible that you could roll and roll for days and never get to a final answer.

  • HEH sweet idea ... :) – Fattie Jun 8 '15 at 15:02

A very simple procedure : Use three 6 sided dice.

  1. A dice $X$ with 3 faces $0$ and 3 faces $5$
  2. Two dice $Y$ and $Z$ with faces $1,2,3,4,5,6$

Throw them all at once, then $R=Y+Z-1$.

  • If $1\le R\le 5$, add $X$
  • If $6\le R\le 10$, substract $X$
  • If $R=11$, reroll all of them.

You obtain a uniform result in the range $[1;10]$.

So rerolls only occur with probability $\frac{1}{36}$, when both $Y$ and $Z$ show $6$, which is better than most other proposed solutions, and it's very simple.

  • The chances of a re-roll are lower but the cost is three times higher, and the minimum number of rolls is three while most others start at two. – sh1 Nov 15 '16 at 8:55

There is an alternate method for getting the 2.2 expected value, which is to reuse the residual uniformly distributed "leftover" after subtracting 30 from the 1-36 result. Inspired by https://math.stackexchange.com/a/1273824/11560

Assume we have a value $p$ uniformly distributed from 0 -5.

Roll a single die, call its value $k$. then $N = k*6+p$ is uniformly distributed from 0-35. If $N<30$ we can use $N\%10 +1$ as our result. If $N \ge 30$ then $N-30$ is uniformly distributed in 0-5, so we can repeat this step.

Once we've got an initial p, we would expect to repeat the core of the algorithm 36/30 = 1.2 times. Obtaining the initial p is 1 roll, so we have an expected number of rolls of 2.2

Extension to 1-11

This is more extensible than the other method that give n=2.2, since we can find a value from 1-11 in a similar way (with $n\approx2.10$)

Roll 2 dice $k_1$ and $k_2$ to get $N = 6*(k_1-1)+(k_2-1)$ uniformly in 0-35.

  • $N < 33$ (done) result is $N\%11+1$ : probability $\frac{33}{36}$
  • residual $p=33-N$ is uniformly distributed in 0-2 : probability $\frac{3}{36}$
    • Throw another die to get $k$ 1-6 then $v = 3*p+(k-1)$ is uniformly distributed in 0-17
    • $v < 11$ (done) result is $v+1$ : probability $\frac{11}{18}\frac{3}{36}$
    • residual $p = v - 11$ is uniformly distributed in $0-6$ : probability $\frac{7}{18}\frac{3}{36}$
    • Throw another die to get $k$ in 1-6 then $v = 6*p + k$ is uniformly distributed in 0-41
      • $v < 33$ (done) result is $N\%11+1$ probability $\frac{33}{42}\frac{7}{18}\frac{3}{36}$
      • residual $p=v-33$ is uniformly distributed in 1-9

Using just these first three steps will terminate with probability

$$P_T = \frac{33}{36} + \frac{11}{18}\frac{3}{36} + \frac{33}{42}\frac{7}{18}\frac{3}{36} \approx 0.993$$

with an expected number of throws (if terminated) of

$$ E(n|T) = (2 \frac{33}{36} + 3 \frac{11}{18}\frac{3}{36} + 4 \frac{33}{42}\frac{7}{18}\frac{3}{36})/P_T \approx 2.0879 $$

Meaning that if we just repeat this procedure should it fail after three steps we will require an expected

$$ n = \frac{E(n|T)}{P_T} \approx 2.102 $$

throws. Note that this should be worse than continuing the algorithm above, so is an upper bound on the expected number of throws.

You can generate a uniform random number in $\{1,\dots,2^m\}$ "easily" (although not in the least number of tosses possible, maybe) by some "binary descent" (see your dice as a coin, with $\{1,2,3\}$ being Heads and $\{4,5,6\}$ being Tails). If Heads, recurse on $\{1,\dots,2^{m-1}\}$, and if Heads on $\{2^{m-1}+1,\dots, 2^m\}$. This will require $m$ coin tosses.

Now, this means you can generate a uniform random number between 1 and 16, say. To get one between 1 and 10, you then can use the above as a blackbox, and perform rejection sampling: this will only give you a bound on the expected number of tosses needed, which on average will be a factor $\frac{10}{16}$ more than before -- i.e., on expectation you'll make $4\cdot \frac{10}{16} = 2.5$ tosses.


Edit: As a side comment: this method generalizes to any $2k$-sided die, and even if the dice happen to be biased (applying a Von Neumann trick first). The main drawback regarding its non-optimality comes directly from its main idea: by looking at the die as if it were basically only a (possibly biased) coin, you loose a lot of possible leverage. Note that this can be improved by looking at variants other than binary descent -- i.e., to generate uniform random numbers in $\{1,\dots,K^m\}$, as long as $K$ divides the number of sides of the die (improves efficient, slightly, when applicable.)

You can convolve the uniform discrete function of 6 values a number of times with itself. This corresponds to summing the values of consecutive throws. This function will fast be possible to approximate with a gaussian ( low number of throws ). Then you can use the cumulative function at the points closest to 0.1,0.2,0.3 etc. to find bounds to approximate your D10.

Roll the dice one time. Let us say $a$ shows up on the dice.If $a=1$, rethrow the dice.

Note down $A=a-1$.

So, $A$ can be $1,2,3,4,5$, since $a$ can be $2,3,4,5,6$.

Note down $B=2A$.

So, $B$ can be $2,4,6,8,10$.(Each value of $B$ has equal probability.)

Throw the dice again. If an even number shows up, note down:-

Result, $R=B$ else note down $R=B-1$.

Hence,the overall result is $R$, produced by throwing the dice only two times (if there was no rethrow.)

When a dice is viewed from roughly a 45 degree angle from above you can always see the upper face and depending how the dice falls you can also see either a front face or a left and right face. Whichever way it happen to fall you can always discern three faces.(you can actually discern ALL the faces) This fact is used in the following method to generate a random number from 1 to 10.
For example if the upper face is 1 then there are four equally possible pairs of left/right faces----(5,4) (5,3) (2,3) (2,4).
If we let two of these pairs represent a number between 1 and ten, for example 1 with (5,4) or 1 with (5,3) represents 1.
Building up a table with method in mind gives-----

TABLE 1
1 with-(2,3) or (2,4) =1
1 with-(5,3) or (5,4) =2
2 with-(6,4) or (6,3) =3
2 with-(1,4) or (1,3) =4
3 with-(6,5) or (6,2) =5
3 with-(1,2) or (1,5) =6
4 with-(6,5) or (6,2) =7
4 with-(1,5) or (1,2) =8
5 with-(6,4) or (6,3) =9
5 with-(1,4) or (1,3) =10

Now, as for the occurrence of a 6 on the upper face, there are a number of ways that this situation can be handled.
It could be considered a non event, and even if considered as such it would still be fairly efficient, nonetheless it is a waste of a throw.
So, how can a 6 be utilised ? There are a number of ways this can be done.
You could simply keep count of the number of 6's and assign 1 to the first 6, 2 to the second 6, 3 to the third 6,......,10 to the tenth 6, 1 to the eleventh 6 and so on. This method may introduce a somewhat slight Bedford's Law effect, which I can't see as being a major problem, as this occurs in a lot of natural random processes anyway.

You could, when a 6 appears on the upper face, rotate the dice on one of its 4 three-fold axes, for example call each of the axes $A_{1},A_{2},A_{3},A_{4}.$
Keeping count of the number of 6's, for the first 6 you rotate along $A_{1}$,along $A_{2} $ for the second 6, along $A_{3}$ for the third 6 and along$ A_{4}$ for the fourth 6, using TABLE 1 this will give you equally probable occurrences of {3,4,5,6,7,8,9,10}
On the occurrence of the fifth 6 on the upper face just pretend the 6 is actually a 1 and again use TABLE 1 to determine the resultant number, which is a 1 or a 2.
This method is repeated every 5 occurrences of a 6 appearing on the upper face thereby giving each number from 1 to 10 an equal chance.

These methods though crude and far from mathematically elegant, I am sure do work and are efficient, requiring only one roll of the dice for a result. I'm sure many on this site could greatly improve on this method especially in regard to the " 6's problem "

If you can use a compass (not the one mathematicians use, but the one geographers use), you can do the following:

  • First throw a die. If the result is even, your number will be even, if it is odd, your result will be odd.
  • Then throw the die again. If the result is 1,2,3,4 or 5, then that is your residue class mod 5. If it is a 6, look to the compass. If the line through the middle and perpedicular on the side of the die with a the three on it, points on your compass between 0 and 72 degrees, the result is 1, if it is between 72 and 144, then the result is 2, if it is between 144 and 216, then the result is three, etcetera.

Two throws.

Alternatively, if you have a mathematical compass and a straightedge, you can construct a regular pentagon and do the same thing.

Note that $6^9=10077696\doteq1.008\cdot 10^7$. This suggests the following procedure to obtain a maximal number of decimal digits per throw of the die: Throw the die $9$ times resulting in nine numbers $a_k\in[6]$. If the number $$N:=\sum_{k=1}^9(a_k-1)6^{k-1}\ \in{\mathbb N}_{\geq0}$$ is $\geq10^7$ restart (this happens with a probability of $<0.8\%$). Otherwise write $N$ as a seven-digit decimal, padding it with leading zeros if necessary.

Let's first generalize the problem, find an optimal solution for that, and then specialize it to the given problem.

OK, so the general problem is: We have a source that gives us one of $n$ different results randomly with uniform distribution. We want to emulate a source giving us $k$ different results randomly with uniform distribution. And we want to do it with as few possible draws from the original source as possible.

Since we want $k$ different results, we need $k$ equally probable events. For $d$ draws from the source, we get $n^d$ equally probable results. So unless $k=n^d$ for some $d$, we are going to have to throw away some information (if $k=n^d$, the solution is obvious: Draw a random number $d$ times). But of course we want to throw away as little information as possible.

Now it is obvious that we cannot give $n$ equally probable results if there are less than $n$ results from our source. So the first step is to draw as many times from the source that $n^{d_0}>k$ where $d_0$ is the number of draws. For example, for emulating a coin with a standard six-sided die, we only need to throw once, while for emulating a six-sided die with a coin, we need at least $3$ tosses (because $2^2<6<2^3$).

Next, we want $k$ equal-probability events. We have $n^d$ equal-probability base events. We now find the largest multiple of $k$ that's not larger than $n^{d_0}$; say that multiple is $m_0k$. Then we make $k$ groups of $m_0$ base events each, leaving $r_0:=n^{d_0}-m_0k$ base events not covered by any group. Obviously those $k$ groups have equal probability, so if the base event of our draw is in one of the groups, we can just take as result which of the group is in. Note that there's another uniform-distributed information we didn't use, which is which of the elements in that group we selected; that information may be reused if we want to draw another number in the same way as explained below for the case that we get one of the "leftover" base events.

When we get one of the $r_0$ base events that are not in one of the group. we have failed so far to get a result. Now the simplest way to continue would be to start over; however that way we would discard information; namely information about which of the $r_0$ "leftover" events we got (unless $r_0=1$, then there is of course no information left). Those are also uniformly distributed, so we can easily use them to generate the new uniform set. Thus if we draw an addition $d_1$ times, we get not just $n^{d_1}$, but $r_0n^{d_1}$ equally distributed values.

Note that this reuse also implies that we can simplify our step before; if the number of events after some throw is too small, we simply get groups of zero elements (and thus zero probability of getting a result; as it should be given that we haven't yet thrown often enough to generate sufficient events).

To accomodate the case of $k\le n$ (where a single draw from the source might generate one or even several

So the algorithm goes as follows:

  1. You have an uniform distribution of size $r_i$ left over by previous steps (for no information left, which includes the initial state, that distribution has size $r_n=1$), and a value $v_i$ from that distribution (which I assume for simplicity to go from $0$ to $r_i-1$; for $r_i=1$ we obviously then have $v_i=0$).

  2. Calculate $m_i = \lfloor r_i/k \rfloor$.

  3. If $v_i < m_ik$, give as result $d_i=\lfloor v_i/m_i \rfloor$ and generate as new leftover data (for possible further draws) $r_{i+1}=m_i$ and $v_{i+1} = v_i-m_id_i$

  4. Otherwise, don't generate a result, draw a new random number $s_i$ from the source (which I assume to give numbers from $0$ to $n-1$), set $r_{i+1} = r_i n$, $v_{i+1} = v_i n + s_i$ and start over.

Now let's apply that algorithm to the specific problem, where $n=6$ and $k=10$ (where I implicitly subtract $1$ for the dice throws and add $1$ for the results wherever applicable).

So we start out with $r_0=1$ and $v_1=0$. Then we get $m_0=0$. Since clearly $0 < 0$ is false, we throw once, resulting (after subtraction of $1$) in a random value $s_0$ between $0$ and $5$. Our new leftover values are thus $r_1 = 1\cdot 6=6$ and $v_1 = 0\cdot 6 + s_0$. That is, our leftover distribution contains a number between $0$ and $5$.

In the next iteration, we still find $m_1=0$ (we don't yet have enough data) and thus we again get to draw a new number (that is, throw again). We therefore now arrive at a random distribution from $0$ to $35$.

In the next iteration, we get $m_2=3$. So if our randomly distributed number is less than $30$ (which happens in $30/36 = 5/6$ of all cases), we get a result (and a leftover distribution from $0$ to $2$ for further throws; noite that this means drawing a second number from $1$ to $10$ in the best case needs only one further dice throw).

Otherwise, we get a leftover distribution of size 6 (namely between 31 and 36), which is exactly as if we had thrown only once. Therefore, the following iterations are exactly like this one.

Indeed, when changing slightly the way the result is calculated, this gives rise to the following specific algorithm for drawing the first number:

  1. Throw your dice once. This gives you the result $a$ (from $1$ to $6$).

  2. Now throw until you have something other than a $6$. That gives you the result $b$ (from $1$ to $5$).

  3. Take the last digit of $a+6b$ and add $1$.

This gives a minimal number of two throws, and an average number of $11/5 = 2.2$ throws.

Let's also consider mathmandan's idea of using not only the top side, but the complete orientation of a cube forced to lie on a given square.

Here we have $n=24$, which is larger than $10$, so we have a chance at every throw. For the first throw, the algorithm gives already a result with probability $20/24 = 5/6$ (while leaving a single bit as leftover for generating another random number). However, unlike with mathmandan's solution, in the other case we don't just start over, but reuse the remaining information, which is an uniform distribution of 4 values. After another throw, we now have an uniform distribution of $4\cdot 24 = 96$ different values. Now with probability $90/96 = 15/16 \approx 0.94$ you get a result (and a comfortable $9$-value distribution for a possible next draw). If despite that great chance you again fall into the leftover range, you've got a uniform distribution of length $6$, so after the next throw you get a distribution of length $6\cdot 24 = 144$. Now you have a probability of a whopping $140/144 = 35/36 \approx 0.97$ to get a result (and in that case a comfortable starter distribution of size $14$ for a possible further draw). If you're unlucky enough to fall into the remaining $3\%$ you again have a leftover distribution of size $4$, so we get repetition.

So with the "full cube orientation" method, the algorithm gives an average number of $1 + 153/840 \approx 1.18$ tosses for the first draw.

Note that further draws are more efficient because you've got a leftover from the previous draw.

protected by Community Jun 7 '15 at 19:58

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

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