The problem you are describing is a well-known probability puzzle called "The Secretary Problem" or "The Marriage Problem," which involves the optimal stopping theory.
We have n candidates, and the hiring strategy is to interview the first n/2 candidates without hiring any of them, building a "benchmark" from the best candidate seen so far. Next, the manager hires the first candidate that is better than everyone in the benchmark group. If no such candidate appears, the manager hires the last candidate.
Let’s find out the probability that the manager hires the best candidate using this strategy.
Define P(n) as the probability of hiring the best candidate when there are n candidates in total. Note that for n = 1, P(1) = 1 as there is only one candidate.
Now, consider the case for general n. The best candidate can be in any of the n positions with equal probability, say $\frac{1}{n}$. There are two distinct cases:
1. The best candidate is in the benchmark group.
2. The best candidate is in the rest of the candidates.
Case 1 - If the best candidate is in the first n/2 positions, then the manager will never hire them as per the strategy. Therefore, the probability of successfully hiring the best candidate in this case is 0.
Case 2 - Let’s assume the best candidate is in position k such that k > n/2. For the manager to hire this best candidate, the second-best candidate should be in the first k − 1 positions (since the manager will not consider candidates within benchmark for hiring). The probability of this occurring is $\frac{k-1}{n/2}$. As k can take any value in the range (n/2, n], we have:
$$P(n) = \frac{1}{n} \sum_{k=\frac{n}{2}+1}^{n} \frac{k-1}{\frac{n}{2}}$$
Now, we simplify the expression:
$$P(n) = \frac{2}{n^{2}} \sum_{k=\frac{n}{2}+1}^{n} (k-1) = \frac{2}{n^{2}} \left[\sum_{k=1}^{n} (k-1) - \sum_{k=1}^{\frac{n}{2}} (k-1) \right]$$
To evaluate the summations, we use the fact that $\sum_{k=1}^{n} (k-1) = \frac{n(n-1)}{2}$ and $\sum_{k=1}^{\frac{n}{2}} (k-1) = \frac{n(n-2)}{4}$. Substituting and simplifying the expression:
$$P(n) = \frac{2}{n^{2}} \left[\frac{n(n-1)}{2} - \frac{n(n-2)}{4}\right] = \frac{2}{n^{2}} \cdot \frac{n^{2} - n}{4} = \frac{n-1}{2(n-1)} = \frac{1}{n}$$
Therefore, for any given n, the probability of successfully hiring the best secretary using this strategy is $\frac{1}{n}$.
This is an example of the "Optimal Stopping Problem" or the "Secretary Problem". The objective of this problem is to select the best option from a sequence of independent and identically distributed random variables.
The strategy mentioned in the question is to reject the first n/2 candidates and then hire the first candidate who is better than any of the ones you’ve seen before.
The optimal strategy for the general problem, assuming n applicants, is to interview and reject the first n/e candidates, where n/e is the greatest integer less than or equal to e (Euler’s number is approximately equal to 2.71828), then hire the first candidate who is better than any you’ve seen so far.
The optimal stopping rule prescribes always skipping the first n/e applicants and then stopping at the first applicant who is better than the best applicant seen so far. This leads to a winning probability of approximately 1/e for a large number of applicants.
However, the strategy in this problem differs from the optimal stopping problem in that the manager is rejecting the first n/2 candidates rather than n/e candidates.
If we use this strategy, the probability of selecting the best candidate can be calculated as follows:
The best candidate could be in the first half of the pool, with probability 1/2, in which case we never hire them.
Or the best candidate could be in the second half of the pool, with probability 1/2, and the probability we select them is 1/(n/2) because they have to be the best of the remaining n/2 candidates.
So, the overall probability of success is
1/2 * 1/(n/2) = 1/n.
So, for large n, the probability of hiring the best secretary with the strategy provided is 1/n. This is samse as one would simply randomly pick any candidate.
Note: The strategy of rejecting the first n/e candidates and then choosing the first candidate better than those is considered optimal as it gives a probability of success of approximately 1/e ( 37%), which is higher than the 1/n probability of success for the strategy you proposed.