Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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.
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:
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...
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$.
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
(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)
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:
Roll a d20. If the result is between 1 and 13, stop. Otherwise roll again.
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.
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.
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:
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} $$
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.
Try rolling a D10 and a D6 with the D6 values being:
1-2 = 1 3-4 = 2 5-6 = 3
