# Some questions about RANDOM(a, b)

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

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 ?

• Jul 14, 2021 at 17:53
• It is possible that this algorithm doesn't terminate although it terminates almost surely (i.e., with probability $1$). For example when $b-a$ is not a power of two and the generated number before the final if is always $2^{range}$. A randomized algorithm is an algorithm that has access to an oracle that can generate numbers according to some distribution. Usually this oracle can simulate a fair con flip, i.e., it return $0$ with probability $1/2$ and $1$ with probability $1/2$. All deterministic algorithms are trivially also randomized algorithms (but not vice-versa). Jul 14, 2021 at 17:53
• @vonbrand It should actually be floor(log(2, range) + 1. I'll edit it.
Jul 14, 2021 at 17:55
• @Steven So any algorithm which contains a random number generator(whatever it is) is called randomized. Right? Should the numbers be equiprobable? Or it can be any distribution?
Jul 14, 2021 at 18:07

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

• 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}}$$