2
$\begingroup$

I'm reading Chapter 5 of the CLRS Algorithms book. Specifically, it discusses the hiring problem in which we want to assess the expected number of hires given that candidates arrive in random order and each candidate has a distinct rank. All permutations of candidates are deemed equally likely.

As an example of what's deemed a 'hire', let's say candidate 1 has rank 5 and candidate 2 has rank 10. Since candidate 2 has the highest rank seen so far, candidate 2 is hired. In order for a candidate to be hired, it needs to thus have the maximum rank of all ranks seen up until that point.

The book states "Because we have assumed that the candidates arrive in a random order, the first $i$ candidates have appeared in a random order. Any one of these first $i$ candidates is equally likely to be the best-qualified so far".

I know this sounds trivial, but why does random order over all $n$ candidates guarantee random order over the first $i$ candidates? Intuitively, it seems to make sense but I can't explain it formally and thus don't feel like I really understand it.

$\endgroup$
  • 1
    $\begingroup$ Absolutely @owen88. I'll take a look tonight and choose an answer. I get it. $\endgroup$ – Noah Stebbins May 7 at 14:26
1
$\begingroup$

Suppose there are $n$ individuals; we will ignore the ranks and consider the random permutation $\pi \colon \{1,\ldots, n\} \rightarrow \{1,\ldots, n\}$, with the interpretation $\pi(k)$ is the position of individual ranked $k$.

To make calculations easier we consider the marginal for a single person,though the calculations extend to pairs etc. (which in turn will characterise the full distribution).

So we consider $\mathbf P(\pi(k) = m)$, the probability that the $k$-th ranked person is the $m$-th arrival, and from uniformity we have

$$\mathbf P(\pi(k) = m) = \frac{1}{n}, \qquad \mathbf P(\pi(k) \leq m) = \frac{m}{n}.$$

Conditioning on $\pi(k) \leq i$, for $m \leq i$ Bayes formula gives:

$$\begin{align} \mathbf P (\pi(k) = m | \pi(k) \leq i) & = \frac{\mathbf P(\pi(k) < i|\pi(k) = m) P(\pi(k) = m)}{P(\pi(k) \leq i)} \\ & = \frac{1 \times \frac1n}{\frac{i}{n}}\\ & = \frac1i \end{align} $$

which is to say their position is uniform amongst the first $i$, as required.


To prove the full generality takes a bit more conceptual work, but in practice follows from the same argument via Bayes rule.

When considering the joint distribution of $j$ individuals, it is easiest to do the calculations up to proportionality.

Eg. In the above, uniformity told us that $P(\pi(k) = m) \propto 1$, as a function of the position $m$. This property extends to multiple individuals $k_1,\ldots, k_j$: $$ P(\pi(k_1) = m_1, \ldots, \pi(k_j) = m_j) \propto 1,$$ and moreover characterises uniform distributions.

When you evaluate Bayes rule as in the above, up to proportionality all of the terms will be $1$, meaning that we have characterised the uniform distribution on $i$ individuals.

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

Feel free to edit your post with the exact wording (verbatim) of the hiring problem if this does not address it. Instead of explaining in a way that will basically be a re-statement of what you wrote, which you intuitively get but formally don't yet, I'll try a different approach. I think the difficult part is separating the individuals from the order they come in.

Suppose you have $n$ individuals, with ranks $r_1,\dots,r_n$ and you know that for any $i\neq j, r_i \neq r_j$. Now consider taking a group of $i$ individuals from this group randomly. They have ranks $r_{l_1},\dots,r_{l_i}$. In this group of $i$, only one rank is the highest. Note that of these i individuals, because of random arrival, the probability that $l_1$ is first is the same as the probability that $l_2$ is first, which is the same as the probability that $l_k$ is first for any $k=1,\dots,i$. Similarly, the probability that $l_k$ is in the $a$-th order is the same for any $k$. Since they all have the same probability of being in the $a$-th spot, and since one of them has to be in the $a$-th spot, we know that this is a sum of mutually exclusive events that must sum to $1$ and so the probability of $l_k$ being in the $a$-th spot, denoted $P_a$ is $$\sum_{k=1}^i P(\text{$l_k$ is in a}) = 1 \implies i P_a = 1 \implies P_a = 1/i$$

And so for any spot $a$ and any individual $l_k$, $P(\text{$l_k$ is in a}) = 1/i$. Now we know that one of these individuals $l_k$ has the highest rank $r_{l_k}$. Suppose it is individual $l^*$. Well this individual has a 1/i chance of being in any of the spots, and so any of the spots has a 1/i chance of having $l^*$, and so any of the first $i$ candidates is equally likely to be this special $l^*$, as required.

Makes sense?

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.