Let $p$ be a positive integer (which is not a power of $2$), and suppose we want to generate a number uniformly randomly in the set $\{ 0, 1, \dots , p-1 \}$ (to emulate a dice roll). We are given access to an unbiased coin (where successive coin flips are iid Bernoulli random variables with probability $\frac{1}{2}$ of heads and $\frac{1}{2}$ of tails).


The challenge is to minimise the *expected* number of coin flips.


Strategy 1: Naive method
------------------------


Choose the smallest $n$ such that $2^n \geq p$, and flip $n$ coins to obtain a number uniformly distributed over $\{ 0, 1, \dots, 2^n - 1 \}$. If the number is less than $p$, we are done; otherwise forget everything and start again.


Calculating the expected number of coin flips for this strategy is easy:


$$\mathbb{E}[N] = \dfrac{n 2^n}{p}$$


For the case $p = 3$, this gives an expectation of $\frac{8}{3}$. For $p = 6$, corresponding to an ordinary die, the expectation is $\frac{24}{6} = 4$.


Strategy 2: Divide and conquer
------------------------------


The naive method is clearly suboptimal for $p = 6$, since it gives an expectation of $4$, whereas we can reduce it to $\frac{11}{3}$ by applying the naive strategy for $p = 3$ followed by another coin flip (to determine the parity of the roll). This suggests an alternative approach:


Factorise $p$ into a product of prime factors, and apply some strategy to each factor in isolation.


Unfortunately, this isn't optimal either. For $p = 125$, this would advocate performing three instances of the strategy for $p = 5$, each of which must require at least three flips in the best-case scenario (since after flipping two coins, the probability of each outcome is greater than $\frac{1}{5}$, so we require a further flip). Hence we would need at least $9$ flips for strategy 2, whereas the naive strategy requires merely $7.168$ flips on average.


Strategy 3: Greedy method
-------------------------


The idea behind this is that the naive method 'wastes' lots of information if we get a number in $\{ p, \dots, 2^n - 1\}$. We can attempt to reuse this information to a certain extent.


We keep track of a 'state', which will be an ordered pair $(a, b)$, initially set to $(1, 0)$, where $b$ is guaranteed to be uniformly distributed in the set $\{ 0, 1, \dots, a-1\}$ at all times. Now repeatedly apply whichever condition holds:


* If $a < p$, then flip a coin. If heads, move to state $(2a, 2b + 1)$. If tails, move to state $(2a, 2b)$.
* If $a \geq p$ and $b < p$, then output the value $b$ and terminate.
* If $a \geq p$ and $b \geq p$, then move to state $(a - p, b - p)$.


I suspect that the greedy method is optimal, although I haven't proved it. It's more difficult to calculate expected values since we're essentially dealing with a finite Markov chain with a separate state for each value of $a$.


Punchline
---------


The three strategies mutually coincide if and only if $p$ is a Mersenne prime.



How to roll a $p$
Here is an optimal method that I think is equivalent to your greedy method.


We start with a constant random variable, say $0$. Inductively, after $n$ steps we have a random element uniformly distributed on a set of $k$ elements where $k \equiv 2^n \mod p$ and $k \lt p$. At each step, we flip the coin and produce a random element in a set of size $2k \equiv 2^{n+1} \mod p$. If $2k \ge p$ then we take $p$ elements from the set, label them $0$ through $p-1$, and stop with those, continuing with the remaining $2k$ or $2k-p$ elements. 


This is optimal because we minimize the probability of not stopping by the $n$th step, and the expected number of flips is the sum of the probabilities that we have to make the $n$th flip for $n = 1, 2, 3,...$. If the probability of stopping were any higher, then by the pigeonhole principle some outcome would be weighted too highly. It generalizes to the optimal way to roll a $p$-sided die with a $q$-sided die. 


I put this in my August 2013 backgammon column, ["Rolling Coins."](http://www.gammonvillage.com/backgammon/magazine/article_display.cfm?resourceid=6513) That link requires a subscription but I can send a copy to anyone who is interested. I don't know who came up with this method first but I'd guess it was no later than Turing's work on communication.


