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\)?
RANDOM(a, b)
1 n = ceil(lg (b-a))
2 while true:
3 result = a
4 for i = 1 to n:
5 result += 2ⁱ⁻¹ · RANDOM(0, 1)
6 if result ≤ b:
7 return result
Firstl of all, note that RANDOM(0, 1) returns either the integer 0 or the integer 1. In order to generate an arbitrary value between \(a\) and \(b\) we use this procedure to produce the binary representation of some integer between \(0\) and \(\lceil \lg (b-a) \rceil\) (which is then added to \(a\) to produce the final result). This method works perfectly for a range that ends up being a perfect power of 2, but can produce results out of range in other cases. So our last step is to verify that the result is within the allowable range, repeatedly trying again until a suitable result is found.
The expected run time needs to account for this possibility that our result is not within the allowed range. The for loop takes \(O(\lceil \lg (b-a) \rceil)\) time and may be repeated when we fail to stop. The likelihood of stopping as a function of \(a\) and \(b\) is \((b-a+1)/2^{\lceil \lg (b-a) \rceil}\), and the likelihood of continuing is \(1 -\) the stop chance. We can use the sum of an infinite series to calculate the expected run time:
\[\begin{split} & \sum\limits_{i \geq 1}^{\infty} \lceil \lg (b - a) \rceil \cdot \frac{b - a + 1}{2^{\lceil \lg (b - a) \rceil}} \cdot \left( 1 - \frac{b - a + 1}{2^{\lceil \lg (b - a) \rceil}} \right)^{i-1} \text{// let n} = \lceil \lg (b - a) \rceil \\ & \sum\limits_{i = 0}^{\infty} n \cdot \frac{b-a+1}{2^n} \cdot \left( 1 - \frac{b - a + 1}{2^n} \right)^{i} \text{//geometric series} \\ & n \cdot \frac{b - a + 1}{2^n} \cdot \frac{1}{1 - \left( 1 - \frac{b - a + 1}{2^n}\right)} \\ & n \cdot \frac{b - a + 1}{2^n} \cdot \frac{2^n}{b - a + 1}\\ & n \\ \end{split}\]So the runtime is \(O(\lceil \lg (b - a) \rceil)\).