13
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ Another approach, which generalizes to efficiently give an infinite stream of $p$-rolls (though it may not be optimally efficient for a single roll): Consider your string of coinflips as a binary expansion, and convert it to base $p$. I haven't checked the details but I believe this is "optimally" efficient in the sense that almost surely, the ratio of coin flips to $p$-rolls obtained converges to $\log_2 p$. $\endgroup$ – Eric Wofsey Jan 10 '15 at 16:14
  • 1
    $\begingroup$ You're correct that your method is suboptimal for a single roll. For $p = 7$, there's a probability of $\frac{1}{4}$ of terminating after three flips, so the expectation must be at least $3.75$. But the naive method gives $\frac{24}{7} \approxeq 3.429$. $\endgroup$ – Adam P. Goucher Jan 10 '15 at 16:28
  • 1
    $\begingroup$ Yes, exactly. It is efficient for getting lots of $p$-rolls because it never throws away any information (it remembers the path you took to get the first roll and uses that to get the second roll more efficiently, for instance). I suspect your greedy algorithm (which is kind of similar) might be more efficient for getting just a single roll though. $\endgroup$ – Eric Wofsey Jan 10 '15 at 16:28
  • 2
    $\begingroup$ Note that any method that has only finitely many states (which includes all of yours) must have rational expected value and thus cannot achieve the theoretical lower bound of $\log_2 p$. $\endgroup$ – Eric Wofsey Jan 10 '15 at 16:50
  • 2
    $\begingroup$ Efficiently sampling from a probability distribution using coin flips is isomorphic to efficiently encoding signals sampled from that probability distribution using bits. If you use arithmetic encoding (en.wikipedia.org/wiki/Arithmetic_coding) you get @Eric Wofsey's answer $\endgroup$ – Dan Piponi Jan 11 '15 at 1:46
6
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.