2
$\begingroup$

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 ?

$\endgroup$
4
2
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Am I correct in saying that the expected number of calling RANDOM(a,b) is $\frac{2^{k}}{({2^{k} - 1})^{2}}$ where $k = \lfloor \log_{2}^{b - a} \rfloor + 1$? I calculated it this way: $$\sum_{i = 1}^{+\infty} \frac{i}{2^{ik}}$$ $\endgroup$
    – Emad
    Aug 10 '21 at 10:08
  • $\begingroup$ How do you get this formula? $\endgroup$ Aug 10 '21 at 12:55

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.