Simulating a seven-sided die with a six-sided one
Or, how to draw random integers from any range with dice
How can we use a standard six-sided die to draw a random integer from any range, where each number in the range is equally likely? We explore this question using real and imagined dice.
Many types of dice exist, usually labeled by the number of sides they have. A standard six-sided die is known as a D6 and gives a result in the range 1–6, where each result is equally likely. Dice with 4, 8, 10, 12 and 20 sides are—not surprisingly — known as D4, D8, D10, D12 and D20.
Here, we refer to a die with n sides as Dn, which gives a result in the range 1–n, where each possible result is equally likely to occur. This allows us to imagine die types that do not actually exist, such as D13, D29 or D137. Our current challenge is to take whatever die available, such as a D6, and use this to simulate the result of any type of die, real or imagined.
Simulate a smaller die from a larger one
To simulate a smaller die than what is available, there is a straightforward solution to make all possible results equally likely — accept the result if it is within the desired range, otherwise roll again. This approach is known as rejection sampling, and is a general approach that guarantees all possible results to be equally likely to occur.
For example, if we want to simulate a D5 with a D6, we accept the result if it is within the range 1–5. If the result is 6, we continue rolling until we get a result within the desired range.
Simulate a larger die from smaller ones
In order to take full advantage of rejection sampling, we need to be able to simulate arbitrarily large dies. Fortunately, there is a straightforward solution to this as well — we can combine several die rolls to simulate the roll of a larger die.
If we have a result from one die, and then roll another one, we can combine their results as follows to make sure that all possible results are equally likely to occur:
combined result = (result of first die − 1) × sides of the second die + result of the second die
When we combine die rolls like this, the sides of the combined die is the product of the sides of the two dice:
sides of combined die = sides of the first die × sides of the second die
With just a D6 available, we can roll it twice to simulate the result of a D36. We can then take the result of the D36, roll a D6 again, and combine these results to simulate the result of a D216, and so forth. Nine rolls of a D6 will thus enable us to simulate the result of a die with 10 077 696 sides.
Now that we know how to simulate an arbitrarily large die, we have all we need to start simulating any type of die from another — roll until simulating a large enough die, accept the result if it is within the desired range. Otherwise, start over again.
But, this is not always efficient.
Simulate any die from another efficiently
With the use of rejection sampling and combined die rolls to simulate large dice, it is possible to generate integers uniformly at random from any desired range, but not always in the most efficient way — in the sense of using as few die rolls as possible.
To illustrate this, let us simulate rolling a D4 with a D6. With rejection sampling, we accept the result if it is in the range 1–4, otherwise we continue rolling until we get a result in the desired range.
This procedure has a probability of 1/3 to require two rolls or more, 1/9 to require three rolls or more, 1/27 to require four rolls or more, and so forth. In theory, this could go on infinitely — although that would only happen with an infinitely small probability.
Yet, it is possible to simulate a D4 with a D6 using at most two die rolls. By rolling a D6 twice, we simulate the result of a D36. Since 36 is a multiple of 4, the result of a D36 can be considered as the combined result of a D9 and a D4. We can easily extract the result of the D4 and accept this as our result. This approach — rolling a D6 twice to simulate a D4 — always requires exactly two die rolls.
But, we can do even better. We know that it often is possible to simulate a D4 with a D6 using only one die roll by using rejection sampling. If the result is in the range 1–4, we accept the result. But, if the result is in the range 5–6, we may consider this as the result of a D2 (by subtracting 4). Then, when we roll the D6 again, we can combine this result with the D2 to simulate the result of a D12. Since 12 is a multiple of 4, we may consider this result as the combined result of a D3 and a D4, and accept the D4 as our result.
With this approach, we often only need one roll from a D6, this will happen about 2/3 of the time, and we are guaranteed to need at most two rolls from a D6, which will happen about 1/3 of the time. It is not possible to simulate a D4 with a D6 more efficiently than this.
Putting the pieces together
Now, we have all the basic pieces we need to construct a general procedure for simulating any type of die with another one with as few die rolls as possible:
- At the start, we are provided with a simulated, imaginary D1 die. It always has a result of 1.
- While our current simulated die has a smaller range than our target die, we roll an available real die, and combine its result with the current result of the simulated die. This becomes our new simulated die. We repeat this step for as long as necessary.
- When the range of the simulated die is large enough, we figure out the largest multiple of the target die range that fits in the simulated range. This marks the limit for rejection sampling.
- If the current value of the simulated die is larger than this largest multiple, (1) subtract the largest multiple from the current value of the simulated die, and set this as the new value of the simulated die, (2) reduce the range of the simulated die by subtracting the value of the largest multiple, and (3) return to step 2 above.
- If the current value of the simulated die is equal to or less than the largest multiple, subtract 1 from current value of the simulated die, compute the remainder from dividing by the number of sides of the target die, then add 1 to get the final result (computed as (value − 1) mod sides of the target die + 1).
To illustrate this procedure, let us simulate a D10 with a D6:
- We roll the D6 with a result of 6. This also becomes our current simulated die, but does not yet have a large enough range.
- We roll the D6 again, now with a result of 2. Our current simulated die is now a D36 with a result of 32 (computed as (6 − 1) × 6 + 2). This has a large enough range to proceed.
- The largest multiple of 10 that fits 36, is 30. Our current result of 32 is larger than this, which means there is no result to accept yet. We subtract 30 from our current result and range. Our current simulated die is now a D6 with a result of 2.
- We roll the D6 again, now with a result of 3. Our current simulated die is now a D36 with a result of 9 (computed as (2 − 1) × 6 + 3). This has a large enough range to proceed again.
- The largest multiple of 10 that fits 36, is still 30. Our current result of 9 is within the range 1–30, which means there is a result to accept. We divide (9 − 1) by 10, which gives a remainder of 8, then add 1 to get a final result of 9.
- Here, we needed three rolls of a D6 (with the results 6, 3, and 2) to simulate a D10 with a result of 9.
Simulating a seven-sided die with a six-sided one
Now we are ready to return to the title of this post — how to simulate a D7 with a D6. Using the general procedure above, this turns out to be pretty straightforward. We need two rolls of a D6 to cover a large enough range, this simulates a D36. The largest multiple that fits this range is 35, which means that we need to start over if the result is 36. Otherwise, we subtract 1 from the result of the D36, compute the remainder from dividing this number by 7, then add 1 to return the final result.
What about drawing random integers from other ranges?
Sometimes, we may want to draw a random integer from a range that does not start at 1, such as 0–10 or 7–11. To accommodate this, we map the range to one that starts with 1 to figure out which die to simulate, then map the result back afterwards.
To figure out the number of sides of the die we need, we compute the range of the included integers like this:
range = largest value − smallest value + 1
Then, we compute the offset — the number we need to add afterwards — like this:
offset = smallest value − 1
In the case of 0–10, there are 11 possible outcomes in this range. Thus, we can simulate the result of rolling a D11 and then subtract 1 from the result afterwards to cover this range. Similarly, in the case of 7–11, we simulate the result of rolling a D5 and add 6 to the result afterwards.
Let it roll
We should now be able to efficiently generate a random integer uniformly from any range we would need, just by using whatever die we have available. Alea iacta est.
(In a follow-up story to this one, we demonstrate how to operate a manual random number generator with dice.)