How do I use a small die to get a larger, linearly-distributed random number?

Question

Say I have a coin, aka 1d2, aka a 2-sided die. I need to get a random integer from 1 to n with equal probability of all n integers. I can flip/roll my coin/1d2 as many times as I need to (within reason/practicality).

How can I use a coin/1d2 to get, say, an evenly/linearly distributed random number from 1 to 6?

My initial approach is to simply roll 6 times and add up the number of times I get heads/1, and ignore any tails/2 values. But over multiple iterations this yields a (gaussian?) distribution matching a bell curve; 3 is most likely, followed by 2 and 4, then 1 and 5, and least likely 0 and 6 (which is another problem; the result can be 0).

I'll accept something that's a close approximation to equal probability, provided the procedure works for multiple values of n and not just 6.

Answer 1

There are lots of ways to do this, some less efficient than others. Powers of $2$ are easy, because for $1$ to $4$, for example, you can assign $1,1\to 1$; $1,2\to2$; $2,1\to3$; and $2,2\to4$. If you wanted to do $1$ to $3$, you can use the same method, but let $2,2$ map to "start over." Generalize this idea to $n$.

Answer 2

Here is another strategy: Interpret the coin flips as $0$ and $1$ and throw the coins $k>\log_2 n$ times. So, for $n=6$ you can take $k=3$ and obtain $000, 001, .. .$ or $111$. interprete this as a binary number, discard it if it's $>6$ and otherwise choose that number. That way you generate numbers with the desired distribution.

Answer 3

Here’s a variation on the answers already given. It is essentially a base conversion algorithm from base $2$ to base $n$ and will save you some coin tosses on average since it produces a sequence of random numbers essentially without wasting any information.

1. Start with the triple $(a_0, b_0, c_0) = (0, n, 1)$.
2. Toss your coin. The next triple $(a_{k+1}, b_{k+1}, c_{k+1})$ will be $(2a_k, a_k + b_k, 2c_k)$ if heads and $(a_k + b_k, 2b_k, 2c_k)$ if tails.
3. If $$\left \lfloor \frac{a_k}{c_k} \right \rfloor = \left \lfloor \frac{b_k - 1}{c_k} \right \rfloor = m \in \{0, \ldots, n-1 \}$$ then output $m$, set $$(a_{k+1}, b_{k+1}, c_{k+1}) =(n \cdot(a_k \operatorname{mod} c_k), n \cdot(b_k \operatorname{mod} c_k), c_k)$$ and go to step 3.
4. Otherwise, go to step 2.

Example with $n=3$ and tosses HTTHTT (and note that $0.011011_2 = 0.102..._3$ in base $2$ and base $3$ respectively): $$ \begin{eqnarray} \mathrm{toss} & & \mathrm{triple} & &\mathrm{output} \\ & & (0,3,1) & &\\ \mathrm{H}& &(0,3,2) & & \\ \mathrm{T}& &(3,6,4) & & \\ \mathrm{T}& &(9,12,8) & & 1\\ & &(3,12,8) & & \\ \mathrm{H}& &(6,15,16) & & 0 \\ & &(18, 45, 16) & & \\ \mathrm{T}& &(63,90,32)& &\\ \mathrm{T}& &(153, 180, 64)& &2\\ & &(75,156,64)& &\\ \end{eqnarray} $$