How many random bits does this algorithm use on average?

Question

Here, flip() is a function that returns 0 or 1 with equal probability. It can be proved function Random(n) returns a number from 0 to n-1 with identically distributed probabilities (using loop invariant).

function Random(n):
    v = 1;
    c = 0;
    loop
        v = 2v;
        c = 2c + flip();
        if (v >= n) then
            if (c < n) then
                return c;
            else
                v = v - n;
                c = c - n;
            end if
        end if
    end loop
end function

My question is how many random bits does this algorithm use in average (expected number of times that the flip() function is called)?

Answer 1

I don't have a formal proof, but I expect the expected value is $\lg n + O(1)$ bits. In particular, heuristically I am expecting something like $\lg n + 2.9$ bits or so (but I don't trust that the constant is exactly right, so take this with a large grain of salt).

Where did I obtain this from? Well, after $\lg n$ steps, $v$ will be of size comparable to $n$.

Now as a heuristic, suppose that $v$ is uniformly distributed in the range $[n/2,n)$ at a particular step. Of course $c$ will be uniformly distributed on the range $[0,v)$, as this is an invariant of the algorithm. Then this step will terminate if $c < n/2$. The probability of this is

$$\begin{align*} \Pr[c<n/2] &= \sum_{v=n/2}^n \Pr[c<n/2 \mid v] \Pr[v] = \sum_{v=n/2}^n {n/2 \over v} \cdot {1 \over n/2}\\ &\approx \int_{1/2}^1 {1 \over x} \; dx = \log 2 \approx 0.69. \end{align*}$$

On the other hand, if $c>n/2$, then it will not terminate, and after the next step, $v$ will be uniformly distributed on $[0,n-1)$ and $c$ uniformly distributed on $[0,v)$. Starting from a point where $v$ is uniformly distributed on $[0,n-1)$, it takes approximately 1 more step (on average) to reach a point where $v$ is uniformly distributed on $[n/2,n-1)$, and then we're back to where we started. We expect to have to repeat this procedure $1/0.69 \approx 1.45$ times before it terminates, and each repetition takes 2 steps, so in total once we reach the point where $v$ is uniformly distributed on $[n/2,n)$, we expect the algorithm to take $2 \times 1.45 \approx 2.89$ steps (on average) before terminating.

Summing these up ($\lg n$ steps in the first phase and $2.89$ steps in the second phase, on average) yields a number like $\lg n + 2.9$.

I have made some approximations and shortcuts and used some heuristics here, so this answer is a bit sketchy, but I would bet that it is approximately correct, though the constant term might not be exactly right.