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.