Photo by Jonathan Petersson on Unsplash

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.

Simulating the result of a five-sided die (D5) with a six-sided one (D6)

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.

How to combine the results of a D4 die and a D6 die to simulate the result of a D24 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.

Simulating a D4 die with a D6 die using rejection sampling

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.

Simulating a D4 die with exactly two rolls of a D6 die which simulates a D36. This result can then be viewed as a combination of a D9 and a D4, which gives the final result.

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.

Simulating a D4 die with a D6 die with as few die rolls as possible. Accept the result of the first D6 if in the range 1–4. Otherwise, view the result as a D2, then roll another D6 to simulate a D12. This result can then be viewed as the combined result of a D3 and a D4, which gives the final 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:

1. At the start, we are provided with a simulated, imaginary D1 die. It always has a result of 1.
2. 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.
3. 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.
4. 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.
5. 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).

Simulating a D10 die with a D6 die with as few rolls as possible. Two rolls of a D6 simulates a D36. The largest multiple of 10 that fits is 30. If the D36 result is in the range 1–30, we view this as the combined result of a D3 and a D10, which gives the final result. Otherwise, if the D36 result is in the range 31–36, we view this as the result of a D6 (by subtracting 30), then roll another D6 to simulate a D36 again, and so forth.

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.

Simulating a seven-sided die with a six-sided one

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