33
$\begingroup$

I am asking if it is possible to choose a random integer using a certain set of dice. Assume for these calculations that the dice are perfectly randomly distributed. There are 7 dice in a set, with the following possible outcomes for each dice:

2, 4, 6, 8, 10, 12, and 20

You are free to interpret the outcomes as any value you like.

The dice can be rolled in any order, combination, or quantity desired.

The objective is to have 13 possible outcomes, perfectly random and uniformly distributed.

$\endgroup$
  • 5
    $\begingroup$ One option is roll the 4D and 10D and interpret the values respectively as the 10s and 1s value of an integer in $\{1, \ldots, 40\}$. If the result is $40$, discard and re-roll. Otherwise, take the result modulo $13$. Since $13$ divides the number ($39$) of undiscarded possibilities, all outcomes are equally likely. $\endgroup$ – Travis Willse May 8 '15 at 17:26
  • 17
    $\begingroup$ @Travis If we allow discards, why not simply roll the 20-dice until we get a number from 1 to 13? $\endgroup$ – Amitai Yuval May 8 '15 at 17:36
  • 3
    $\begingroup$ @Sam: there are $24$ equally likely things that can happen if you do that, and $24$ isn't divisible by $13$. $\endgroup$ – Qiaochu Yuan May 8 '15 at 18:15
  • 3
    $\begingroup$ @Amitai: because you'll have to discard 35% of rolls, rather than 2.5%. $\endgroup$ – user14972 May 8 '15 at 19:50
  • 2
    $\begingroup$ It has to be said, the internet gods demanded it... xkcd.com/221 $\endgroup$ – Sabre May 9 '15 at 4:35
30
$\begingroup$

This is impossible if you require that there is a fixed upper bound on the number of possible rolls: in this case, the only probabilities you can get are of the form $\frac{n}{m}$ where $m$ is a product of the numbers $2, 4, 6, 8, 10, 12, 20$, and in particular cannot be divisible by $13$.

This is straightforward if you don't require such a fixed upper bound: as mentioned in the comments, you can discard and reroll. This strategy, like any successful strategy, necessarily has the property that it is possible that you'll have to reroll arbitrarily many times. But the probability is exponentially decaying so it's not really an issue.

Edit: An interesting follow-up question might be to find a strategy that minimizes the expected number of rolls. Suppose you have a strategy involving $n$ rolls per iteration, with probability $p$ of succeeding each iteration (and probability $1 - p$ of needing to reroll). Then the expected number of rolls turns out to be $E = \frac{n}{p}$. So, comparing the strategies that have been suggested so far:

  • Travis's $4$ and $10$ strategy has $n = 2, p = \frac{39}{40}$, so $E = \frac{80}{39} \approx 2.05$.
  • Amitai's $20$ strategy has $n = 1, p = \frac{13}{20}$, so $E = \frac{20}{13} \approx 1.54$.
  • M. Wind's "all the dice" strategy has $n = 7, p = \frac{921596}{921600}$, so $E = \frac{6451200}{921596} \approx 7.00$.

Amitai's strategy is in fact the only possible strategy with an expected number of rolls of less than $2$ (so I take back what I said about it requiring more rolls than Travis's!), although one might go on to calculate and compare the variance of the number of rolls as well...

$\endgroup$
  • 9
    $\begingroup$ I don't know that your $n$ is a good measure of efficiency. Rolling multiple distinct dice simultaneously doesn't really take longer than rolling a single die. In practice, I'm thinking Travis's strategy is likely to be the best balance between expected number of (multi-)die rolls and expected amount of required mental arithmetic, though this is admittedly hard to formalize. $\endgroup$ – Micah May 8 '15 at 18:56
  • $\begingroup$ That's a fair point. $\endgroup$ – Qiaochu Yuan May 8 '15 at 18:57
  • $\begingroup$ This answer has provided the most relevant information to me. Excellent response! $\endgroup$ – Sam Weaver May 8 '15 at 19:17
  • 12
    $\begingroup$ One can augment the d20 strategy by taking advantage of the fact that $40=3\cdot13+1$. Roll a d20, and accept any roll of 1–13. On a 14–20, subtract 14 and double (yielding one of $\{0,2,4,6,8,10,12\}$), and add the result of a d2. Accept 1–13, and on a 14, start over. This strategy has an expected number of rolls equal to $\frac{18}{13} \approx 1.38$. $\endgroup$ – Greg Martin May 8 '15 at 19:26
  • 1
    $\begingroup$ Another simple yet efficient strategy would be to use dice ${2, 6, 12}$. This gives $144$ possibilities, which is equal to $143 + 1 = 11 * 13 + 1$. $\endgroup$ – M. Wind May 8 '15 at 22:07
18
$\begingroup$

You could use all seven dice in one throw. This gives you $2 \cdot 4 \cdot 6 \cdot 8 \cdot 10 \cdot 12 \cdot 20 = 921600$ possible outcomes. Next you need a procedure to assign to each outcome a unique number. This allows you to distribute outcomes into $13$ groups of equal size. It is not difficult to do so.

Note that the multiple of $13$ that is closest (from below) to $921600$ is $921596 = 70892 \cdot 13$ This means that only in $4$ cases out of $921600$ you would have to reject the result and throw the dice again. The probability that this happens is $1$ in $230400$.

$\endgroup$
  • $\begingroup$ Interesting solution, it sure minimizes the probability of rejection. :) $\endgroup$ – Sam Weaver May 8 '15 at 18:30
  • 5
    $\begingroup$ Note that you can leave out the 4-sided die and arrive at the same ratio of 1 in 230400 rejections. $\endgroup$ – Greg Martin May 8 '15 at 19:10
  • $\begingroup$ Excellent. Thank you for pointing this out. $\endgroup$ – M. Wind May 8 '15 at 22:02
  • $\begingroup$ Assigning the outcomes to distinct numbers is also not hard. You can consider the result as a mixed base number by subtracting one from the result of each die, so the result of the d20 is 0-19, the result of the d12 is 0-11, etc. After doing that, your number is $d20+20d12+240d10+1920d8+\dots$ Every number in $[0,921599]$ is equally probable. You accept any number in $[0,921595]$ and reroll the rest. With probability $921596/921600$ you are done in one roll. Good approach. $\endgroup$ – Ross Millikan May 9 '15 at 3:37
  • $\begingroup$ @GregMartin: If the aim is to minimise the expected number of multi-dice throws, then you should throw the $4$ too, because if you have to re-throw, it gives you a random number $0-3$ for free. You can use this in combination with the second throw, as explained in Jim Belk's answer. $\endgroup$ – TonyK May 18 '15 at 22:26
17
$\begingroup$

1) You could roll d20 and reroll anything over 13. So sometimes you reroll once or twice. (~96% of the time it takes no more than two rerolls to get a result)

2) you could roll two (distinguishable) d12s ('regular' & 'special' say) together

  • if both dice show "12", reroll both
  • if only the special die is 12, the result is "13"
  • if the special die is not 12, use the result on the regular die

(This works especially well if at least one of the d12's has a very distinguishable 12 face; if only one does, use it as the special die)


In response to the request for clarification why the second method is correct:

Note that $12\times 12=144 = 11\times 13+1$. So if we can assign the 144 outcomes from rolling two 12-sided dice to the 13 results we want - each getting 11 of the 144 outcomes with one left over - then we'll have a discrete uniform distribution on $1,\ldots,13$.

So, step 1 is to take out the 144th option; (12,12).

We also just want to read a die to get a number most of the time. So we want to make one of the dice take its face value 11x12 times (i.e. when the other die doesn't show 12). The remaining 11 times (when it does show 12 but the other one doesn't) then takes the last value. Like so:

          special die
       1    2    3    4    5    6    7    8    9   10    11 :  12 
reg.______________________________________________________________
 1 |   1    1    1    1    1    1    1    1    1    1     1 :  13 
 2 |   2    2    2    2    2    2    2    2    2    2     2 :  13 
 3 |   3    3    3    3    3    3    3    3    3    3     3 :  13 
 4 |   4    4    4    4    4    4    4    4    4    4     4 :  13 
 5 |   5    5    5    5    5    5    5    5    5    5     5 :  13 
 6 |   6    6    6    6    6    6    6    6    6    6     6 :  13 
 7 |   7    7    7    7    7    7    7    7    7    7     7 :  13 
 8 |   8    8    8    8    8    8    8    8    8    8     8 :  13 
 9 |   9    9    9    9    9    9    9    9    9    9     9 :  13 
10 |  10   10   10   10   10   10   10   10   10   10    10 :  13 
11 |  11   11   11   11   11   11   11   11   11   11    11 :  13 
12 |  12   12   12   12   12   12   12   12   12   12    12 : Reroll

As you can readily verify, each of the numbers 1:13 appears 11 times in the table.


d11

You can also do d11 in similar fashion. Of course, you could just roll the regular die and reroll it on 12, but this way rerolls become quite rare.

Again roll a regular and a special d12, and then read the regular die unless it's 12, in which case read the special die (if they're both 12, reroll them both).

Again, the table makes this clear:

          special die
       1    2    3    4    5    6    7    8    9   10   11   12 
reg._____________________________________________________________
 1 |   1    1    1    1    1    1    1    1    1    1    1    1 
 2 |   2    2    2    2    2    2    2    2    2    2    2    2 
 3 |   3    3    3    3    3    3    3    3    3    3    3    3 
 4 |   4    4    4    4    4    4    4    4    4    4    4    4 
 5 |   5    5    5    5    5    5    5    5    5    5    5    5 
 6 |   6    6    6    6    6    6    6    6    6    6    6    6 
 7 |   7    7    7    7    7    7    7    7    7    7    7    7 
 8 |   8    8    8    8    8    8    8    8    8    8    8    8 
 9 |   9    9    9    9    9    9    9    9    9    9    9    9 
10 |  10   10   10   10   10   10   10   10   10   10   10   10 
11 |  11   11   11   11   11   11   11   11   11   11   11   11 
.. |  .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. 
12 |   1    2    3    4    5    6    7    8    9   10   11 : Reroll

The same ideas can be applied to any of the other dice in your dice-set (like the d20), so for example d7, d9, d19, d21 can all be emulated this way (well, d3 and d5 could also, but you can do them using d6 and d10 easily enough)

$\endgroup$
  • $\begingroup$ I think they needn't be physically distinguishable if you adopt some other rule for distinguishing them after the roll, for example ordering them by how far from the roller they stopped, or by which was rolled with the left hand and which with the right. $\endgroup$ – Doug McClean May 9 '15 at 4:15
  • $\begingroup$ @DougMcClean Indeed, that will work -- there can be a variety of ways of distinguishing them, but generally it's better if it's unambiguous, to avoid any accusation of fudging. Usually someone playing D&D will have access to two different colours at least. If you don't have distinguishable dice or only have one die, "first roll/second roll" would suffice. $\endgroup$ – Glen_b May 9 '15 at 4:27
  • $\begingroup$ Such a great answer. The first one so simple; the second one so clever. $\endgroup$ – aepryus May 9 '15 at 4:39
  • $\begingroup$ @RalphJ see my update $\endgroup$ – Glen_b May 9 '15 at 6:11
  • $\begingroup$ +1 I found calling them the 'big' and 'small' dice slightly confusing; I'd suggest 'regular' and 'special' respectively, since you do something special when you get a 12 on the special die. It's also worth mentioning that the same method works for simulating a d7 with 2 d6s or a d11 with 2 d10s. $\endgroup$ – Michael Shaw May 9 '15 at 10:47
14
$\begingroup$

If the goal is to minimize the expected number of dice rolled (as suggested by Qiaochu Yuan), one can improve on Amitai's method by saving the information from discarded die rolls. Here's how it works:

  1. Roll a d20. If the result is between 1 and 13, stop. Otherwise roll again.

  2. After the second roll, we have 140 equal possibilities, with 7 choices left from the first roll, and 20 from the second roll. If the result is one of the first 130, stop and generate a number. Otherwise roll again.

  3. After the third roll, we have 200 equal possibilities, with 10 left from the second roll and 20 from the new roll. If the result is one of the first 195 (which is a multiple of 13), stop. Otherwise continue.

The expected number of rolls for this strategy is $$ 1 \,+\, \frac{7}{20} \,+\, \frac{10}{20^2} \,+\, \frac{5}{20^3} \,+\, \frac{9}{20^4} \,+\, \cdots \;=\; \frac{1238418740163877}{900219780219780} \;\approx\; 1.375685, $$ where the numerators of the fractions on the left are the powers of 20 modulo 13. The numerators repeat every 12 terms, and grouping sets of 12 terms together yields a geometric series, which is how I calculated the sum.

More generally, instead of just using a sequence of d20's, one can use any sequence of allowed dice, with $k_1$ sides for the first die, $k_2$ sides for the second die, and so forth. In this case, the expected number of rolls is $$ 1 \,+ \sum_{n=1}^\infty \frac{k_1\cdots k_n \text{ mod }13}{k_1\cdots k_n} $$ Though I'm not entirely sure, I believe this sum is minimized for the following sequence of dice: $$ 20,\;\;8,\;\;20,\;\;20,\;\;20,\;\;8,\;\;20,\;\;20,\;\;20,\;\;8,\;\;\ldots $$ In this case, the expected number of rolls is $$ 1 \,+\, \frac{7}{20} \,+\, \frac{4}{20\cdot 8} \,+\, \frac{2}{20^2 \cdot 8} \,+\, \frac{1}{20^3\cdot 8} \,+\, \frac{7}{20^4 \cdot 8} \,+\, \frac{4}{20^4 \cdot 8^2} \,+\, \cdots $$ which sums to $$ \frac{88040}{63999} \;\approx\; 1.375646\text{ rolls}. $$ I think this may be the best possible strategy for minimizing the number of dice rolled.

$\endgroup$
5
$\begingroup$

Any single die (or even a coin for 1d2) can be used to decide arbitrary probabilities between 0 and 1 if the number of rolls is not restricted. Higher is faster; pick the d20. Subtract 1 from each face so it rolls 0 to 19. Now write a base-20 fraction: $$ \frac{r_0}{20^1} \,+ \frac{r_1}{20^2} \,+ \frac{r_2}{20^3} \,+ \cdots = \frac{1}{20}(r_0 + \frac{1}{20}(r_1 + \frac{1}{20}(r_2 + \cdots))) = \frac{r_0 + \frac{r_1 + \frac{r_2}{20}}{20}}{20} $$

(Each $r_i$ is one dice roll.) You can stop rolling when, regardless of future rolls, the infinite expression falls completely within the interval $[\frac{k}{13} , \frac{k+1}{13})$. $k + 1$ is your result. And of course, if you have multiple dice of the same type, roll them all at once and compute multiple place values at once.

To generalize to multiple dice of multiple types, use the telescoping form above with varying denominators. Bigger dice first converges faster. Let's roll a d20, d12 and d10 together, one of each subtracting one from all the face values. If we roll 4, 11 and 7 respectively, we have: $$ \frac{3 \,+ \frac{10 \,+ \frac{6 \,+ \cdots}{10}}{12}}{20} = \frac{466}{2400} + \cdots $$

We now check to see if the interval $[\frac{466}{2400}, \frac{467}{2400})$ is fully within the interval $[\frac{k}{13}, \frac{k+1}{13})$. If it is, $k + 1$ is the result. Otherwise, we keep rolling and continuing the fraction. We have $\frac{2}{13} < \frac{466}{2400} < \frac{467}{2400} < \frac{3}{13}$ so we rolled a 3 on 1d13. (Rolling the d10 turned out to be unnecessary this time.)

To incrementally add new rolls to previous ones, keep the floor of your interval ($\frac{466}{2400}$ from above), and add the fraction for the next batch of rolls divided by the product of all previous dice sizes. Each set of multiple dice rolls corresponds to one element of the following second-order place value series:

$$ \frac{\frac{r_0 + \frac{r_1 + \frac{r_2}{10}}{12}}{20}}{2400^0} + \frac{\frac{r_3 + \frac{r_4 + \frac{r_5}{10}}{12}}{20}}{2400^1} + \frac{\frac{r_6 + \frac{r_7 + \frac{r_8}{10}}{12}}{20}}{2400^2} + \cdots $$ $$ = \frac{x_0}{2400^0} + \frac{x_1}{2400^1} + \frac{x_2}{2400^2} + \cdots $$ $$ = x_0 + \frac{x_1 + \frac{x_2 + \cdots}{2400}}{2400} $$

It follows from this how to change the particular group of dice being used for each step in mid-stream without starting over. Just use the product of all dice sizes used in the current batch as the denominator under the remainder of the telescoping fraction. To continue rolling at any point, use the product of all dice sizes cumulatively rolled as the denominator of the remainder of the series.

Performance:

  • As a practical matter, this method requires a little bookkeeping, and a calculator for all but the true mental arithmetic nerds. To eliminate rounding error, work with fractions, or multiply by common denominators to compare only numerators.
  • This method wastes no information; you never have to discard rolled values.
  • The probability that, after rolling a certain number of dice, you will have to continue rolling at least one more die, is the quotient of the number of non-colliding partitions between possible outcomes and the product of all the dice sizes rolled so far. So in our example of rolling 1d20 + 1d12 + 1d10 to decide 1d13, the probability that you will need further rolls is $\frac{13 - 1}{20 \times 12 \times 10} = \frac{1}{200}$.
  • The expected value of the number of throws you need is an interesting calculation, and depends obviously on the roll you're simulating and the pattern of dice rolls you intend to use. If the probabilities you're simulating are all rational and share all prime factors with the product of the dice faces you use, you have a finite maximum number of throws. Otherwise you theoretically could end up rolling forever, but as long as you repeat the same combinations of dice with each throw, the expected number of throws can be solved for using a telescoping fraction. In our example, 13 is relatively prime to $20 \times 12 \times 10 = 2400$, so if we throw those same dice every time, we initially have a 1 in 200 chance of a re-throw, but only 1 in 2400 after that. So our expected number of throws is (applying the definition of expected value): $$ \frac{199}{200} \times 1 + \frac{1}{200} \times (1 + \frac{2399}{2400} \times 1 + \frac{1}{2400} \times (1 + \frac{2399}{2400} \times 1 + \frac{1}{2400} \times \cdots)) $$ Which reduces to $\frac{199 + \frac{4799 + \frac{4799 + \cdots}{2400}}{2400}}{200} = \frac{2411}{2399} \approx 1.005002$. (Let $x = \frac{4799 + x}{2400}$ and solve.)

    Applying the same formula to rolling 1d13 using a single d6, we have to roll at least twice, stopping two thirds of the time, and stopping after that five sixths of the time. So the expected number of throws is $$ \frac{2}{3} \times 2 + \frac{2 + \frac{5}{6} \times 1 + \frac{1 + \frac{5}{6} \times 1 + \frac{\cdots}{6}}{6}}{3} = \frac{4}{3} + \frac{17}{18} + \frac{\frac{11 + \frac{11 + \cdots}{6}}{6}}{3} = \frac{271}{90} = 3.0\overline{1} $$

$\endgroup$
  • $\begingroup$ In terms of "least entropy wasted" this is the winner. You could even just flip a coin, and this starts to look a lot like a data compression algorithm (called Range Encoding or Arithmetic coding). Simple discard-when-out-of-range though is going to be much more practical without a computer. $\endgroup$ – Neil Slater May 10 '15 at 9:22
  • $\begingroup$ @NeilSlater Yes, this is arithmetic encoding generalized to more than just binary fractions. Although to implement arithmetic encoding in messaging or storage you have to also represent what probabilities are being modeled. $\endgroup$ – wberry May 22 '15 at 18:28
3
$\begingroup$

By perfectly random, do you mean uniformly random? Because any combination that produces 13 values (say 1d10 + (1d4-1)) would produce a (completely) random result. Just maybe not a uniformly random result (i.e. the numbers may not show up with the same frequency).

The frequency table of the out comes of the 1d10 + (1d4-1) scheme: $$ \begin{array}{cccccccccccccc} \text{outcome} & 1 & 2 & 3& 4 & 5& 6& 7& 8& 9&10&11&12&13\\ \hline \text{frequency} & .025 & .05 & .075 & .1 &.1 &.1 &.1 &.1 &.1 &.1&.075&.05&.025 \end{array} $$ You might be able to put a penalty on the outcomes 2 to 12 and somehow produce a more uniform distribution, but likely the best approaches would be the rejection methods specified in the comments.

$\endgroup$
  • $\begingroup$ Uniformly random, sorry for not being clear. $\endgroup$ – Sam Weaver May 8 '15 at 18:06
-1
$\begingroup$

Try rolling a D10 and a D6 with the D6 values being:

1-2 = 1 3-4 = 2 5-6 = 3

$\endgroup$
  • 3
    $\begingroup$ Are you then suggesting to add the values? This will have a minimum of 2, and the outcome won't be uniform. $\endgroup$ – Teepeemm May 9 '15 at 14:31

Your Answer

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

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