5.1 The hiring problem

5.1-1

Because we are always able to determine which candidate is best, that means we can compare any two candidates and know which is better. Thus we are able to sort the candidates based on this knowledge, which implies that we know a total order on the ranks of the candidates.

5.1-2

First we find the smallest number p, such that 2^p > b - a. Then call RANDOM(0, 1) to generate p bits, thus we have a random number r. If r + a <= b, then that's what we want, otherwise we regenerate r. (Link 1, link 2)

import math
import random


def random_number(a, b):
    bits = math.ceil(math.log2(b - a + 1))

    while True:
        number = random_binay(bits)

        if a + number <= b:
            return a + number


def random_binay(bits):
    number = 0

    for i in range(bits):
        number = number * 2 + random.randint(0, 1)

    return number

The running time of function random_binay is $O(\lg{(b - a)})$. And it's possible that we need to call random_binay multiple times if a + number > b, but that doesn't affect the expected running time, since $cO(\lg{(b - a)})$ is still $O((\lg{(b - a)}))$.

Thus the expected running time is $O(\lg{(b - a)})$.

5.1-3

We can call BIASED-RANDOM twice to get two numbers x and y. The results would be 0, 0, '1, 0', '0, 1', '1, 1', with probability (1 - p)(1 - p), p(1 - p), (1 - p)p, pp respectively. Since p(1 - p) = (1 - p)p, we can treat one as 0 and the other as 1. So we can generate 0 with probability 1/2 and 1 with probability 1/2.

The probability to generate 0, 1 and 1, 0 is $2p(1 - p)$, so we have to try $\frac{1}{2p(1 - p)}$ times. Thus the expected running time is $O(\frac{1}{p(1 - p)})$.

def unbiased_random():
    while True:
        x = BIASED-RANDOM()
        y = BIASED-RANDOM()

        if x != y:
            return x