Generating uniform integers in a range from a random generator with another range

Question

Let $p$ and $q$ be two positive integers. I have an oracle that can generate a uniform integer in $\{1, \ldots, p\}$, the integers thus produced being independent across oracle calls. My goal is to generate a random number in $\{1, \ldots, q\}$ with uniform probability, and to do so in a way that minimizes the expected number of oracle calls required.

My question is: What is an optimal algorithm to solve this problem? I expect this to be a standard problem, so I'd be interested in pointers to the name of this problem in the literature. A special case of this problem ($p = 5$ and $q = 7$) is a standard puzzle or interview question (see here, but I was unable to find pointers to a generalization, and I don't see any optimality proof in those answers.

Of course, in general, the problem will not be solvable with a bounded number of oracle calls. Take for instance $p = 2$ and $q = 3$, or more generally, cases where some prime divisor of $q$ is not a divisor of $p$, and it is clear that for any bound $N$, the number of possible outcomes when doing $N$ calls, i.e,. $p^N$, cannot be divided evenly in $q$ buckets for each possible value.

One natural approach outlined here is to see the oracle calls as generating a uniform real number in [0, 1] from its $p$-ary writing, and terminate whenever the first decimal in the $q$-ary writing of that number is certain: think of it as using the oracle to select a subdivision of size $1/p^k$ in the interval $[0, 1]$, and concluding whenever the interval that you fall in is included in one of the $q$ intervals $[i/q, (i+1)/q]$ for $0 \leq i < q$. However, this approach does not seem optimal: for instance, for $p = q+1$, the approach only concludes in one call if the call returns 1, otherwise a second call is necessary. By contrast, a simpler rejection-based approach that calls the oracle, concludes if it falls in $\{1, \ldots, q\}$, and rejects and tries again if it falls in $q+1$, seems to have better performance.

One can try to generalize the rejection-based approach to the following: letting $k$ be minimal such that $p^k \geq q$, use $k$ oracle calls to get a uniform integer $n$ in $\{1, \ldots, p^k\}$. If $n$ falls in $\{1, \ldots, M\}$, for $M > 0$ the smallest multiple of $q$ which is $\leq p^k$, return $n \text{ mod } q$, otherwise try again. However it would seem that the additional information of which excess value in $\{M+1, \ldots, p^k\}$ was obtained could be also used in the next attempt. I can imagine how to do this (see here for a proposed algorithm, which I think is correct), but I have no idea of how to prove the optimality of such a scheme.

I am also curious about the natural variation of this problem where you want to generate not a single random number in $\{1, \ldots, q\}$, but a stream of such numbers. What's the expected number of calls per number, and an optimal method in this case?

[Note that an alternative vision of the problem that does not involve randomness at all is to think of the outcome trees: each node is either a leaf with label in $\{1, \ldots, q\}$ corresponding to a decision, or an internal node with $p$ children corresponding to an oracle call. An algorithm is a (generally infinite) such tree where, for each $1 \leq l \leq q$, the probability mass of all the leaves labeled $l$ (i.e., the sum of the mass over leaves, where the mass of each leaf is $1/p^h$, where $h$ is its height) is equal to $1/q$; and its expected performance is the sum, over all leaves, of $h/p^h$ (probability mass of this leaf, times the number of oracle calls performed in that case).]

Answer 1

I think I can show the optimality of a scheme that I skteched in the question, the one that does rejection sampling but reuses the remaining entropy.

Description of the scheme. Thinking as an algorithm, the scheme is the following. It has two parameters, an integer $n$, and a bound $m$, $0 \leq n < m$, with the invariant that $n$ was drawn uniformly at random in $[0, m[$. (I'll rephrase everything to ranges of the form [0, n[ rather than $\{1, \ldots, n\}$ because it's simpler.)

At each step we do the following:

• if $m < q$, then we need more entropy: let $n'$ be the result of calling the oracle that samples in $[0, p[$ uniformly, and recurse with $n := n p + n'$ (i.e., a combination of the current $n$ and the new draw) and $m := m p$ (a larger interval). It is clear that if $n$ is uniform in $[0, m[$ and $n'$ is uniform in $[0, p[$ then the combination $n p + n'$ is uniform in $[0, mp[$

• if $m \geq q$, then let $M$ be the largest multiple of $q$ which is smaller than $m$. If $n$ is in $[0, M[$, then we return $n \text{ mod } q$ as the result: this is uniform. Otherwise, the remainder $n - M$ is uniform in the range $[0, m - M[$, so we recurse with $n := n - M$ and $q := q - M$.

In pseudocode, reformulating the second point to substract $q$ multiple times instead of finding $M$, we get the following very simple algorithm:

int algo(int n, int m) {
  // invariant: n is uniform in the range [0, m[
  if (m < q)
    return algo(p*n + randint(p), m * p);  
  if (n < q)
    return n;
  return algo(n-q, m-q);
}

algo(0, 1);

Optimality. This algorithm is, I think, optimal. To see why, let me reformulate it in terms of decision trees. What the algorithm does is, at every level, if we have at least $q$ leaves then turn into leaves the largest multiple of $q$ that you can, and grow the other nodes; otherwise just grow all nodes. (This makes it clear that the scheme is uniform, because the labels in $[0, q[$ on the tree are used in exactly the same way.)

Let us consider the (generally infinite) tree $T$ obtained by such a scheme, and consider a hypothetical tree $T'$ which denotes a uniform strategy with a better expected score.

It is clear that the performance of the tree depends only on the number of internal nodes at every depth. In other words, if I can show that, at every level, the number of internal nodes of $T'$ is at least that of $T$, then $T'$ cannot be better than $T$.

But consider any depth $k$. It is clear that, in $T$, the number of internal nodes is precisely $p^k - M$ for $M$ the largest multiple of $q$ which is below $p^k$: let's write $M = mq$. Now if $T'$ does better than this and has less than this number of internal nodes, let us divide the $p^k$ possible outcomes at depth $k$ of $T'$ between the decided ones and the yet undecided ones: more than $mq$ must be decided (to be better than $T$) and they must be split between $q$ outcomes, so the most probable outcome $v$ at that level must have probability at least $(m+1)/p^k$. Now by maximality of $m$ we have $(m+1)q > p^k$, so that $(m+1)/p^k > 1/q$. But by uniformity the probability of $v$ overall (so, in particular, at depth $k$) should not be more than $1/q$. So $T'$ cannot be uniform: outcome $v$ has probability $> 1/q$.

Hence, $T'$ never does better than $T$.

Expected performance. To compute the expected performance of this optimal strategy, one can just write out an equation system based on which recursive calls are performed by the pseudocode above (with the indicated probability distribution). The value of the parameters is bounded, so presumably, for given values of $p$ and $q$, this should be solvable as a geometric series or something like that. (This can be interpreted as an equation system describing the expected number of draws required for a decision forest with $n$ root nodes, $n$ being the number of nodes at the current level.)

Extending to multiple draws. One can generalize this scheme to draw multiple values, in the following way: when you have made a draw in $[0, q[$, instead of starting at a single-root decision tree for the next draw, start at a forest with $m$ nodes, the number of the outcomes with the same label at the level at which you decided, to use this remaining entropy. My conjecture would be that the resulting scheme would have the same performance as the $p$- and $q$-ary solution sketched in my question (so be optimal for multiple draws while concluding faster for a single draw). I have no proof of this fact, though.