How to generate a random number between 1 and 10 with a six-sided die?

Question

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?

• Travis Willse: 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 Willse: Of course, I'd rather just buy a D10.
• Did: 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$.
• David Mitra: For 2., roll one die once. If a "6" results, roll again?
• Julia Hayward: Go to gaming shop. "Hello, I'd like a 1d10, would you take this lovely 1d6 in part exchange?" :)

Answer 1

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.

• P.A.: Could you explain why this is uniform and how to compute the expected number of tosses?
• Jack D'Aurizio: @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}.$$
• Clement C.: 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.: 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}$$.
• Jim Belk: @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.

Answer 2

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.

• Did: 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: Which might be $$\frac{34}{15}=2.2667.$$
• Jack D'Aurizio: 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ドル$.
• NovaDenizen: 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.
• David K: It's interesting to compare this answer with the one by MJD.

Answer 3

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.

• PSPACEhard: 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$.
• MJD: 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: 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.
• Jack D'Aurizio: 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.
• Michael Anderson: It would be nice to add to the the expected number of rolls to generate a single value.

Answer 4

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 easily 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, maybe 1 would understand that rolling two dice does not give you "a 'random' number between 1 and 12."

• Jay: 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.
• Fattie: 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!
• 355durch113: Did you mean 2-12 with the 2 dices? Also shouldn't the kids be saying "it's either 2 or 7"?
• Fattie: 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 :)
• m1m1k: This is the best answer, hands down. Thank you sir. The OP original question involves 1D6, meaning that they're making/playing a boardgame (or doing back-of-napkin calcs) in a physical setting using some physical dice that they have on-hand. This tells us that they're not (D&D players, computer scientists, nor do they have mathmatica or wolfram around to give them the exact answers). So coming up with a simple, easy-to-remember algo is the best. Your description could be a tad clearer... ```

Answer 5

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.

• Mike Scott: That's not a level distribution. You have a higher probability of generating 1-6 than of generating 7-10.
• David K: @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.
• Mike Scott: @DavidK Yes, you're right and I was wrong. I didn't like the asymmetry, and jumped to incorrect conclusions.
• 1110101001: @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?
• David K: @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.

Answer 6

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)

Answer 7

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.

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

Answer 8

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.

• DRF: If you're rounding up you only get a number between 1 and 9
• Mike Scott: @DRF No, you get a number between 1 and 10. Anything above 81 degrees will round up to 10.
• DRF: @mikescott yes in the edited version you do:)
• Chronocide: Before, it read "Divide that angle by 10, rounding up." My brain had confused number of segments with denominator.
• NovaDenizen: This procedure does not work when rolling the die on the north or south pole.

Answer 9

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.

• Jack D'Aurizio: Maybe a number between zero and 6ドル^{\color{red}{N}}$. It is the same method of MJD, anyway.
• Tad: +1 as it is much more concisely expressed than MJD's answer.

Answer 10

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.

• Clement C.: 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}$).
• MJD: Correct. Jack D'Aurizio's calculation of $\frac{11}5$ is mistaken; it actually requires $\frac{12}5$.
• Clement C.: 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 2ドルX$.
• MJD: That's a good point, thanks.

Answer 11

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.

• Fattie: HEH sweet idea ... :)

Answer 12

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.

Answer 13

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 2ドルk$-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.)

Answer 14

@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

Answer 15

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.

Answer 16

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.

• sh1: 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.

Answer 17

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.

Answer 18

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.

Answer 19

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.)

Answer 20

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 "

Answer 21

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.