CLRS Solutions | Exercise 5.1-2 | Probabilistic Analysis and Randomized Algorithms

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

The key insight is to build a random number in the range $[0, n-1]$ where $n = b - a + 1$, by generating random bits and interpreting them as a binary number.

The Algorithm

We use a rejection sampling approach:

Calculate $n = b - a + 1$ (the size of the range)
Find $k = \lceil \lg n \rceil$ (the number of bits needed)
Generate $k$ random bits to form a number $r$ in $[0, 2^k - 1]$
If $r < n$, return $a + r$
Otherwise, reject this sample and repeat from step 3

$$\textsc {Random }(a, b)$$$$\begin{aligned}1& \quad n=b-\text { a }+1 \\2& \quad k=⌈lgn⌉ \\3& \quad \textbf {while }true \\4& \quad \qquad r=0 \\5& \quad \qquad \textbf {for }i=0\textbf { to }k-1 \\6& \quad \qquad \qquad r=2\cdot\,\,r+\textsc {Random}(0,\,1) \\7& \quad \qquad \textbf {if }r<n \\8& \quad \qquad \qquad \textbf {return }\text { a }+r \\\end{aligned}$$

Analysis of Expected Running Time

Each iteration generates $k = \lceil \lg n \rceil$ bits, which takes $\Theta(k)$ time.

The probability of accepting a generated number is:

\[P(\text{accept}) = \frac{n}{2^k}\]

Since $2^{k-1} < n \le 2^k$, we have:

\[\frac{n}{2^k} \ge \frac{2^{k-1}}{2^k} = \frac{1}{2}\]

The expected number of iterations is the reciprocal of the acceptance probability:

\[E[\text{iterations}] = \frac{1}{P(\text{accept})} = \frac{2^k}{n} \le 2\]

Therefore, the expected running time is:

\[E[T] = E[\text{iterations}] \cdot k = O(\lg n) = O(\lg(b - a + 1))\]

Since each iteration takes $\Theta(\lg n)$ time and we expect at most 2 iterations on average, the total expected running time is $\Theta(\lg(b - a))$.

Python Implementation

import random import math def Random01(): """Simulates RANDOM(0, 1) - returns 0 or 1 with equal probability""" return random.randint(0, 1) def RandomAB(a, b): """ Generates a random integer in [a, b] using only Random01() Args: a: lower bound (inclusive) b: upper bound (inclusive) Returns: Random integer in [a, b] """ n = b - a + 1 k = math.ceil(math.log2(n)) while True: # Generate k random bits to form a number in [0, 2^k - 1] r = 0 for i in range(k): r = 2 * r + Random01() # Accept if r < n, otherwise reject and try again if r < n: return a + r # Test the implementation print("Testing Random(3, 7):") print("Generating 20 random numbers in [3, 7]:") results = [] for _ in range(20): results.append(RandomAB(3, 7)) print(results) # Verify distribution (generate many samples) print("\nDistribution test with 10000 samples:") counts = {i: 0 for i in range(3, 8)} for _ in range(10000): counts[RandomAB(3, 7)] += 1 for value, count in sorted(counts.items()): percentage = (count / 10000) * 100 bar = '█' * int(percentage / 2) print(f"{value}: {count:4d} ({percentage:5.2f}%) {bar}") print("\nExpected: Each number should appear ~20% of the time (2000/10000)")