Skip to content

5.1 The hiring problem

5.1-1

Show that the assumption that we are always able to determine which candidate is best in line 4 of procedure $\text{HIRE-ASSISTANT}$ implies that we know a total order on the ranks of the candidates.

A total order is a partial order that is a total relation $(\forall a, b \in A:aRb \text{ or } bRa)$. A relation is a partial order if it is reflexive, antisymmetric and transitive.

Assume that the relation is good or better.

  • Reflexive: This is a bit trivial, but everybody is as good or better as themselves.
  • Transitive: If $A$ is better than $B$ and $B$ is better than $C$, then $A$ is better than $C$.
  • Antisymmetric: If $A$ is better than $B$, then $B$ is not better than $A$.

So far we have a partial order.

Since we assume we can compare any two candidates, then comparison must be a total relation and thus we have a total order.

5.1-2 $\star$

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

1
2
3
4
5
6
7
8
RANDOM(a, b)
    if a == b
        return a
    mid = (a + b) / 2
    r = RANDOM(0, 1)
    if r == 0
        return RANDOM(a, floor(mid))
    else return RANDOM(ceil(mid), b)

The expected running time is $\Theta(\lg(b - a))$.

5.1-3 $\star$

Suppose that you want to output $0$ with probability $1 / 2$ and $1$ with probability $1 / 2$. At your disposal is a procedure $\text{BIASED-RANDOM}$, that outputs either $0$ or $1$. It outputs $1$ with some probability $p$ and $0$ with probability $1 - p$, where $0 < p < 1$, but you do not know what $p$ is. Give an algorithm that uses $\text{BIASED-RANDOM}$ as a subroutine, and returns an unbiased answer, returning $0$ with probability $1 / 2$ and $1$ with probability $1 / 2$. What is the expected running time of your algorithm as a function of $p$?

To get an unbiased random bit, given only calls to $\text{BIASED-RANDOM}$, call $\text{BIASED-RANDOM}$ twice. Repeatedly do so until the two calls return different values, and when this occurs, return the first of the two bits:

1
2
3
4
5
6
UNBIASED-ANSWER()
    while true
        x = BIASED-RANDOM()
        y = BIASED-RANDOM()
        if x != y
            return x

To see that $\text{UNBIASED-RANDOM}$ returns $0$ and $1$ each with probability $1 / 2$, observe that the probability that a given iteration returns $0$ is

$$\Pr\{x = 0 \text{ and } y = 1\} = (1 - p)p,$$

and the probability that a given iteration returns $1$ is

$$\Pr\{x = 1 \text{ and } y = 0\} = p(1 - p).$$

(We rely on the bits returned by $\text{BIASED-RANDOM}$ being independent.) Thus, the probability that a given iteration returns $0$ equals the probability that it returns $1$. Since there is no other way for $\text{UNBIASED-RANDOM}$ to return a value, it returns $0$ and $1$ each with probability $1 / 2$.

Assuming that each iteration takes $O(1)$ time, the expected running time of $\text{UNBIASED-RANDOM}$ is linear in the expected number of iterations. We can view each iteration as a Bernoulli trial, where "success" means that the iteration returns a value. The probability of success equals the probability that $0$ is returned plus the probability that $1$ is returned, or $2p(1 - p)$. The number of trials until a success occurs is given by the geometric distribution, and by equation $\text{(C.32)}$, the expected number of trials for this scenario is $1 / (2p(1 - p))$. Thus, the expected running time of $\text{UNBIASED-RANDOM}$ is $\Theta(1 / (2p(1 - p))$.