Chap 3. Page 92 Excercise 23 - Barbara Smith’s interview Problem

Barbara’s Strategy

1. Interview the first half of the \(n\) candidates and do not select any of them. This sets a benchmark for comparison.
2. In the second half, select the first candidate who is better than all the candidates in the first half.

The total number of candidates is \(n\), and Barbara interviews \(\frac{n}{2}\) candidates first, then considers the remaining \(\frac{n}{2}\) candidates.

Combinatorial Analysis

Let’s consider a specific case where \(n = 6\) to illustrate the combinatorial reasoning:

1. Best Candidate in the First Half:
   • If the best candidate is among the first three (which we are not selecting), there’s no chance of selecting the best candidate.
   • The probability of this happening is \(\frac{1}{2}\) since the best candidate has an equal chance of being in any position.
2. Best Candidate in the Second Half:
   • The best candidate is the first one in the second half: Barbara will select them immediately because they are better than all candidates in the first half. There is one way for this to occur.
   • The best candidate is the second one in the second half: The first one cannot be the best; otherwise, Barbara would have selected them. There is one way for this to occur.
   • The best candidate is the third one in the second half: Both previous candidates cannot be the best, and the first one must not be better than all in the first half, or they would have been selected. There is one way for this to occur.

Now, let’s generalize for any \(n\):

• No Selection in the First Half: There are \(\frac{n}{2}\) candidates in the first half, and we do not select any of them. So, the best candidate must be in the second half for us to have a chance to select them.

• Selection in the Second Half: When we are in the second half, the probability of selecting the best candidate depends on the best candidate’s position within this half.

  • If the best candidate is the first in the second half, we will select them.
  • If the best candidate is the second in the second half, the first candidate must not be better than all in the first half, or they would have been selected.
  • This pattern continues until the last candidate of the second half.

The probability of selecting the best candidate, when they are the \(k\)-th candidate in the second half, is \(\frac{1}{k+1}\). This is because there are \(k+1\) candidates who could have been the best from the first candidate in the second half up to the \(k\)-th candidate.

Combinatorial Formula

The combinatorial formula for the probability of selecting the best candidate using Barbara’s strategy when \(n\) is even is:

\[ P = \frac{1}{2} \times \left( \frac{1}{1+1} + \frac{1}{2+1} + \ldots + \frac{1}{\left(\frac{n}{2}\right)+1} \right) \]

where \(\frac{1}{2}\) accounts for the fact that the best candidate has to be in the second half.

This formula is equivalent to the sum we computed earlier. For each term in the sum \(\frac{1}{k+1}\), it represents the probability of selecting the best candidate given that they are the \(k\)-th person interviewed in the second half.

Using this combinatorial reasoning, we can see that the sum of these probabilities will always be greater than \(\frac{1}{4}\) (25%) when \(n\) is large enough, thus showing that Barbara’s strategy is better than simply choosing a candidate at random, which would give a \(\frac{1}{n}\) probability of success.