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:
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?
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.
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:
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.
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:
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.
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:
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.
P.s. Yes, it is a level distribution. See the comments below.
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
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 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.
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.
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.
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.
@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.
A very simple procedure :
Use three 6 sided dice.
Throw them all at once, then $R=Y+Z-1$.
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.
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
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.
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:
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:
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$).
Calculate $m_i = \lfloor r_i/k \rfloor$.
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$
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:
Throw your dice once. This gives you the result $a$ (from $1$ to
$6$).
Now throw until you have something other than a $6$. That gives
you the result $b$ (from $1$ to $5$).
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.