How do I use a small die to get a larger, linearly-distributed random number? 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.
 A: 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$.
A: 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.
A: 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. 


*

*Start with the triple $(a_0, b_0, c_0) = (0, n, 1)$.

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

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

*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}
$$
