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

There are 4 outcomes when we call $\text{BIASED-RANDOM}$ twice, i.e., $00$, $01$, $10$, $11$.

The strategy is as following:

  • $00$ or $11$: call $\text{BIASED-RANDOM}$ twice again
  • $01$: output $0$
  • $10$: output $1$

We can calculate the probability of each outcome:

  • $\Pr\{00 | 11\} = p^2 + (1 - p)^2$
  • $\Pr\{01\} = (1 - p)p$
  • $\Pr\{10\} = p(1 - p)$

Since there's no other way to return a value, it returns $0$ and $1$ both with probability $1 / 2$.

The pseudo code is as follow:

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

This algorithm actually uses the equivalence of the probability of occurrence of $01$ and $10$, and subtly converts the unequal $00$ and $11$ to $01$ and $10$, thus eliminating the probability that its probability is not equivalent.

Each iteration is a Bernoulli trial, where "success" means that the iteration does return a value.

We can view each iteration as a Bernoulli trial, where "success" means that the iteration returns a value.

$$ \begin{aligned} \Pr\{\text{success}\} & = \Pr\{0\text{ is returned}\} + \Pr\{1\text{ is returned}\} \\ & = 2p(1 - p). \end{aligned} $$

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