Some questions about `RANDOM(a, b)`

Question

This is a question from CLRS:

Describe an implementation of the procedure RANDOM(a, b) that only makes calls to RANDOM(0, 1). What is the expected running time of your procedure, as a function of $a$ and $b$?

Here RANDOM(a, b) is a random number in the range $a, \ldots, b$.

Here is the answer:

RANDOM(a, b)
range = b - a
bits = floor(log(2, range)) + 1
result = 0
for i = 0 to bits - 1
    r = RANDOM(0, 1)
    result = result + r << i
if result > range
    return RANDOM(a, b)
else return a + result

Now I have some questions: Why has the book used the term randomized algorithm(expected running time which is for randomized algorithms)? Apparently, we call an algorithm randomized when there's some pseudorandom number generator in some part of it. So why has it called this algorithm itself randomized? As a result of RANDOM(0, 1)? what's the exact definition of a randomized algorithm? Is it possible that this algorithm doesn't terminate ?

Answer 1

Here is an algorithm that outputs a uniformly random number in the range $0,1,2,3$ given two uniformly random numbers in the range $0,1$:

RANDOM4(r0, r1):
    return r0 + 2*r1

In contrast, there is no algorithm that outputs a uniformly random number in the range $0,1,2$ given $N$ uniformly random numbers in the range $0,1$, for any value of $N$. The reason is that the probability that such an algorithm outputs $0$ is of the form $a/2^N$ for some integer $a$, and this cannot be equal to $1/3$.

However, given an infinite supply of uniformly random numbers in the range $0,1$, we can generate a uniformly random number in the range $0,1,2$ using a technique known as rejection sampling:

RANDOM3(r):
    for t in ℕ:
        a = r(2*t) + r(2*t+1)
        if a < 3:
            return a

Each iteration succeeds with probability $3/4$, and so the expected number of iterations is $4/3$. However, it is potentially unbounded.

Your algorithm also uses rejection sampling. The success probability is always more than $1/2$, so the expected number of iterations is less than $2$.