Draw integers independently & uniformly at random from 1 to $N$ using fair d6?

Question

I wish to draw integers from 1 to some specific $N$ by rolling some number of fair six-sided dice (d6). A good answer will explain why its method produces uniform and independent integers.

As an illustrative example, it would be helpful to explain how a solution works for the case of $N=150$.

Furthermore, I wish for the procedure to be as efficient as possible: roll the least number of d6 on average for each number generated.

Conversions from senary to decimal are permissible.

---

This question was inspired by this Meta thread.

Answer 1

The set $\Omega(d,n)$ of distinct identifiable outcomes in $n$ independent rolls of a die with $d=6$ faces has $d^n$ elements. When the die is fair, that means each outcome of one roll has probability $1/d$ and independence means each of these outcomes will therefore have probability $(1/d)^n:$ that is, they have a uniform distribution $\mathbb{P}_{d,n}.$

Suppose you have devised some procedure $t$ that either determines $m$ outcomes of a $c (=150)$-sided die--that is, an element of $\Omega(c,m)$--or else reports failure (which means you will have to repeat it in order to obtain an outcome). That is,

$$t:\Omega(d,n)\to\Omega(c,m)\cup\{\text{Failure}\}.$$

Let $F$ be the probability $t$ results in failure and note that $F$ is some integral multiple of $d^{-n},$ say

$$F = \Pr(t(\omega)=\text{Failure}) = N_F\, d^{-n}.$$

(For future reference, note that the expected number of times $t$ must be invoked before not failing is $1/(1-F).$)

The requirement that these outcomes in $\Omega(c,m)$ be uniform and independent conditional on $t$ not reporting failure means that $t$ preserves probability in the sense that for every event $\mathcal{A}\subset\Omega(c,m),$

$$\frac{\mathbb{P}_{d,n}\left(t^{*}\mathcal{A}\right)}{1-F}= \mathbb{P}_{c,m}\left(\mathcal{A}\right) \tag{1}$$

where

$$t^{*}\left(\mathcal A\right) = \{\omega\in\Omega\mid t(\omega)\in\mathcal{A}\}$$

is the set of die rolls that the procedure $t$ assigns to the event $\mathcal A.$

Consider an atomic event $\mathcal A = \{\eta\}\subset\Omega(c,m)$, which must have probability $c^{-m}.$ Let $t^{*}\left(\mathcal A\right)$ (the dice rolls associated with $\eta$) have $N_\eta$ elements. $(1)$ becomes

$$\frac{N_\eta d^{-n}}{1 - N_F d^{-n}} = \frac{\mathbb{P}_{d,n}\left(t^{*}\mathcal{A}\right)}{1-F}= \mathbb{P}_{c,m}\left(\mathcal{A}\right) = c^{-m}.\tag{2}$$

It is immediate that the $N_\eta$ are all equal to some integer $N.$ It remains only to find the most efficient procedures $t.$ The expected number of non-failures per roll of the $c$ sided die is

$$\frac{1}{m}\left(1 - F\right).$$

There are two immediate and obvious implications. One is that if we can keep $F$ small as $m$ grows large, then the effect of reporting a failure is asymptotically zero. The other is that for any given $m$ (the number of rolls of the $c$-sided die to simulate), we want to make $F$ as small as possible.

Let's take a closer look at $(2)$ by clearing the denominators:

$$N c^m = d^n - N_F \gt 0.$$

This makes it obvious that in a given context (determined by $c,d,n,m$), $F$ is made as small as possible by making $d^n-N_F$ equal the largest multiple of $c^m$ that is less than or equal to $d^n.$ We may write this in terms of the greatest integer function (or "floor") $\lfloor*\rfloor$ as

$$N = \bigg\lfloor \frac{d^n}{c^m} \bigg\rfloor.$$

Finally, it is clear that $N$ ought to be as small as possible for highest efficiency, because it measures redundancy in $t$. Specifically, the expected number of rolls of the $d$-sided die needed to produce one roll of the $c$-sided die is

$$N \times \frac{n}{m} \times \frac{1}{1-F}.$$

Thus, our search for high-efficiency procedures ought to focus on the cases where $d^n$ is equal to, or just barely greater than, some power $c^m.$

The analysis ends by showing that for given $d$ and $c,$ there is a sequence of multiples $(n,m)$ for which this approach approximates perfect efficiency. This amounts to finding $(n,m)$ for which $d^n/c^m \ge 1$ approaches $N=1$ in the limit (automatically guaranteeing $F\to 0$). One such sequence is obtained by taking $n=1,2,3,\ldots$ and determining

$$m = \bigg\lfloor \frac{n\log d}{\log c} \bigg\rfloor.\tag{3}$$

The proof is straightforward.

This all means that when we are willing to roll the original $d$-sided die a sufficiently large number of times $n,$ we can expect to simulate nearly $\log d / \log c = \log_c d$ outcomes of a $c$-sided die per roll. Equivalently,

It is possible to simulate a large number $m$ of independent rolls of a $c$-sided die using a fair $d$-sided die using an average of $\log(c)/\log(d) + \epsilon = \log_d(c) + \epsilon$ rolls per outcome where $\epsilon$ can be made arbitrarily small by choosing $m$ sufficiently large.

---

Examples and algorithms

In the question, $d=6$ and $c=150,$ whence

$$\log_d(c) = \frac{\log(c)}{\log(d)} \approx 2.796489.$$

Thus, the best possible procedure will require, on average, at least $2.796489$ rolls of a d6 to simulate each d150 outcome.

The analysis shows how to do this. We don't need to resort to number theory to carry it out: we can just tabulate the powers $d^n=6^n$ and the powers $c^m=150^m$ and compare them to find where $c^m \le d^n$ are close. This brute force calculation gives $(n,m)$ pairs

$$(n,m) \in \{(3,1), (14,5), \ldots\}$$

for instance, corresponding to the numbers

$$(6^n, 150^m) \in \{(216,150), (78364164096,75937500000), \ldots\}.$$

In the first case $t$ would associate $216-150=66$ of the outcomes of three rolls of a d6 to Failure and the other $150$ outcomes would each be associated with a single outcome of a d150.

In the second case $t$ would associate $78364164096-75937500000$ of the outcomes of 14 rolls of a d6 to Failure -- about 3.1% of them all -- and otherwise would output a sequence of 5 outcomes of a d150.

A simple algorithm to implement $t$ labels the faces of the $d$-sided die with the numerals $0,1,\ldots, d-1$ and the faces of the $c$-sided die with the numerals $0,1,\ldots, c-1.$ The $n$ rolls of the first die are interpreted as an $n$-digit number in base $d.$ This is converted to a number in base $c.$ If it has at most $m$ digits, the sequence of the last $m$ digits is the output. Otherwise, $t$ returns Failure by invoking itself recursively.

For much longer sequences, you can find suitable pairs $(n,m)$ by considering every other convergent $n/m$ of the continued fraction expansion of $x=\log(c)/\log(d).$ The theory of continued fractions shows that these convergents alternate between being less than $x$ and greater than it (assuming $x$ is not already rational). Choose those that are less than $x.$

In the question, the first few such convergents are

$$3, 14/5, 165/59, 797/285, 4301/1538, 89043/31841, 279235/99852, 29036139/10383070 \ldots.$$

In the last case, a sequence of 29,036,139 rolls of a d6 will produce a sequence of 10,383,070 rolls of a d150 with a failure rate less than $2\times 10^{-8},$ for an efficiency of $2.79649$--indistinguishable from the asymptotic limit.

Answer 2

For the case of $N=150$, rolling a d6 three times distinctly creates $6^3=216$ outcomes.

The desired result can be tabulated in this way:

• Record a d6 three times sequentially. This produces results $a,b,c$. The result is uniform because all values of $a,b,c$ are equally likely (the dice are fair, and we are treating each roll as distinct).
• Subtract 1 from each.
• This is a senary number: each digit (place value) goes from 0 to 5 by powers of 6, so you can write the number in decimal using $$(a-1) \times 6^2 + (b-1) \times 6^1 + (c-1)\times 6^0$$
• Add 1.
• If the result exceeds 150, discard the result and roll again.

The probability of keeping a result is $p=\frac{150}{216}=\frac{25}{36}$. All rolls are independent, and we repeat the procedure until a "success" (a result in $1,2,\dots,150$) so the number of attempts to generate 1 draw between 1 and 150 is distributed as a geometric random variable, which has expectation $p^{-1}=\frac{36}{25}$. Therefore, using this method to generate 1 draw requires rolling $\frac{36}{25}\times 3 =4.32$ dice rolls on average (because each attempt rolls 3 dice).

---

Credit to @whuber to for suggesting this in chat.

Answer 3

Here is an even simpler alternative to the answer by Sycorax for the case where $N=150$. Since $150 = 5 \times 5 \times 6$ you can perform the following procedure:

Generating uniform random number from 1 to 150:

• Make three ordered rolls of 1D6 and denote these as $R_1, R_2, R_3$.
• If either of the first two rolls is a six, reroll it until it is not 6.
• The number $(R_1, R_2, R_3)$ is a uniform number using positional notation with a radix of 5-5-6. Thus, you can compute the desired number as: $$X = 30 \cdot (R_1-1) + 6 \cdot (R_2-1) + (R_3-1) + 1.$$

This method can be generalised to larger $N$, but it becomes a bit more awkward when the value has one or more prime factors larger than $6$.

Answer 4

As an illustration of an algorithm to choose uniformly between $150$ values using six-sided dice, try this which uses each roll to multiply the available values by $6$ and making each of the new values equally likely:

• After $0$ rolls, you have $1$ possibility, not enough to distinguish $150$ values
• After $1$ roll, you have $6$ possibilities, not enough to distinguish $150$ values
• After $2$ rolls, you have $36$ possibilities, not enough to distinguish $150$ values
• After $3$ rolls, you have $216$ possibilities, enough to distinguish $150$ values but with $66$ remaining values; the probability you stop now is $\frac{150}{216}$
• If you have not stopped, then after $4$ rolls you have $396$ remaining possibilities, enough to distinguish $150$ values two ways but with $96$ remaining values; the probability you stop now is $\frac{300}{1296}$
• If you have not stopped, then after $5$ rolls you have $576$ remaining possibilities, enough to distinguish $150$ values three ways but with $96$ remaining values; the probability you stop now is $\frac{450}{7776}$
• If you have not stopped, then after $6$ rolls you have $756$ remaining possibilities, enough to distinguish $150$ values five ways but with $6$ remaining values; the probability you stop now is $\frac{750}{46656}$

If you are on one of the $6$ remaining values after $6$ rolls then you are in a similar situation to the position after $1$ roll. So you can continue in the same way: the probability you stop after $7$ rolls is $\frac{0}{279936}$, after $8$ rolls is $\frac{150}{1679616}$ etc.

Add these up and you find that the expected number of rolls needed is about $3.39614$. It provides a uniform selection from the $150$, as you only select a value at a time when you can select each of the $150$ with equal probability

---

Sycorax asked in the comments for a more explicit algorithm

• First, I will work in base-$6$ with $150_{10}=410_6$
• Second, rather than target values $1_6$ to $410_6$, I will subtract one so the target values are $0_6$ to $409_6$
• Third, each die should have values $0_6$ to $5_6$, and rolling a die involves adding a base $6$ digit to the right hand side of the existing generated number. Generated numbers can have leading zeros, and their number of digits is the number of rolls so far

The algorithm is successive rolls of dice:

• Roll the first three dice to generate a number from $000_6$ to $555_6$. Since $1000_6 \div 410_6 = 1_6 \text{ remainder } 150_6$ you take the generated value (which is also its remainder on division by $410_6$) if the generated value is strictly below $1000_6-150_6=410_6$ and stop;

• If continuing, roll the fourth die so you have now generated a number from $4100_6$ to $5555_6$. Since $10000_6 \div 410_6 = 12_6 \text{ remainder } 240_6$ you take the remainder of the generated value on division by $410_6$ if the generated value is strictly below $10000_6-240_6=5320_6$ and stop;

• If continuing, roll the fifth die so you have now generated a number from $53200_6$ to $55555_6$. Since $100000_6 \div 410_6 = 123_6 \text{ remainder } 330_6$ you take the remainder of the generated value on division by $410_6$ if the generated value is strictly below $100000_6-330_6=55230_6$ and stop;

• If continuing, roll the sixth die so you have now generated a number from $552300_6$ to $555555_6$. Since $1000000_6 \div 410_6 = 1235_6 \text{ remainder } 10_6$ you take the remainder of the generated value on division by $410_6$ if the generated value is strictly below $1000000_6-10_6=555550_6$ and stop;

• etc.