- There is a single position to fill.
- There are (n) candidates for the position, and the value of (n) is known.
- The candidates, if seen altogether, can be ranked from best to worst unambiguously.
- The candidates are interviewed sequentially in random order, with each order being equally likely.
- Immediately after an interview, the interviewed candidate is either accepted or rejected, and the decision is irrevocable.
- The decision to accept or reject a candidate can be based only on the relative ranks of the candidates interviewed so far.
- The objective is to select the best candidate with the highest possible probability.
The optimal strategy is to reject a certain number of candidates. Call the number of rejected candidates (k-1), where (k) is the first candidate that won’t be automatically rejected, ie that you’ll actually consider. We will refer to this let (k−1) go by strategy as strategy (k). Let (M) be the best candidate among these (k-1). Then choose the first subsequent candidate that’s better than (M).
So if we’re given (n), what (k) should we pick to give us the highest probability of picking the best candidate? What is this probability? What happens when (n) goes to infinity?
Let (p_{n}(k)) be the probability of choosing the best candidate with (n) candidates using strategy (k).
Case (bf{n = 3})
We list the 6 permutations of ({1, 2, 3}). 1 is the best, 3 the worst.
- 1, 2, 3
- 1, 3, 2
- 2, 1, 3
- 2, 3, 1
- 3, 1, 2
- 3, 2, 1
Possible values for (k) range from 1 to 3. If (k=1), we always pick the first candidate. If (k=3), we always pick the last. If (k=2), we always reject the first candidate and pick the first subsequent candidate that’s better than the first. So if the first candidate was 2, we end up picking 1. If the first is 3, we end up picking 1 or 2 depending on which one we see first. If the first candidate is 1, we never find a better candidate and end up picking the last one. Tragic.
Now we list (p_{n}(k)) for each value of (k):
k
(bf{p_{n}(k)})
1
1/3
2
½
3
1/3
(k=2) is optimal.
Case (bf{n = 4})
There are 24 permutations of ({1, 2, 3, 4}). 1 is the best, 4 the worst.
k
(bf{p_{n}(k)})
1
6/24
2
11/24
3
10/24
4
6/24
(k=2) is optimal.
Case (bf{n = 5})
There are 120 permutations of ({1, 2, 3, 4, 5}).
k
(bf{p_{n}(k)})
1
24/120
2
50/120
3
52/120
4
42/120
5
24/120
(k=3) is optimal.
The general case
For n candidates, let (X_{n}) denote the number or arrival order of the best candidate, and let (S_{n, k}) denote the event of success (that we pick (X_{n})) for strategy (k). All orderings/permutations of the candidates are equally likely so (X_{n}) is uniformly distributed on ({1, 2, …, n}).
There are two ways we can fail:
- the best candidate is among the first (k-1)
- the best candidate is not among the first (k-1) but is preceded by a candidate with a higher score than any in the first (k-1)
Since we can only pick one candidate from (k) to (n) and these events are exclusive, the probability of picking the best candidate is the sum of the probabilities that the one we picked is indeed the best.
So what’s probability that we succeed by picking a particular candidate? It’s the probability that this candidate is the best multiplied by the probability that we’ll pick him. This second part is very important. It can be rephrased as the probability that the best candidate before him was in the first (k-1). He has to be the best and no one before him can be better than the ones we automatically rejected. Since (X_{n}) is uniformly distributed on ({1, 2, …, n}), the probability that any particular candidate is the best is (1/n).
We calculate the probability of succeeding with candidate (k). The probability that he’s the best candidate is (1/n). The probability that the best candidate before him is in the first (k-1) is 1. So the probability of succeeding with candidate (k) is (1/n cdot 1 = 1/n).
We calculate the probability of succeeding with candidate (k 1). The probability that he’s the best candidate is (1/n). The probability that the best candidate before him is in the first k-1 is (frac{k-1}{k}). So the probability of succeeding with candidate k is (1/n cdot frac{k-1}{k} = frac{k-1}{nk}).
We calculate the probability of succeeding with candidate (k 2). The probability that he’s the best candidate is (1/n). The probability that the best candidate before him is in the first (k-1) is (frac{k-1}{k 1}). So the probability of succeeding with candidate (k) is (1/n cdot frac{k-1}{k 1} = frac{k-1}{n(k 1)}).
…
We calculate the probability of succeeding with the last candidate. The probability that he’s the best candidate is (1/n). The probability that the best candidate before him is in the first (k-1) is (frac{k-1}{n-1}). So the probability of succeeding with candidate (k) is (1/n cdot frac{k-1}{k 1} = frac{k-1}{n(n-1)}).
We sum up these probabilities.
begin{align}
p_{n}(k) &= mathbb{P}(S_{n,k}) = frac{1}{n} frac{k-1}{nk} frac{k-1}{n(k 1)} ldots frac{k-1}{n(n-1)}\
&= frac{k-1}{n} sum_{j=k}^n frac{1}{j-1}
end{align}
So what’s the optimal strategy for (n=100)?
The maximum for (y) or (p_{100}(x)) is about (x=38) with (p_{100}(38) approx 0.37104). So given 100 candidates, we should reject the first 37.
Using Drake’s Equation to estimate eligible individuals
The Drake equation is used to estimate the number of detectable extraterrestrial civilizations that might exist in the Milky Way.
[
N = R* cdot f_{p} cdot n_{e} cdot f_{l} cdot f_{i} cdot f_{c} cdot L
]
(N) = the number of civilizations in our galaxy with which communication might be possible
(R*) = the average rate of star formation per year in our galaxy
(f{p}) = the fraction of those stars that have planets
(n{e}) = the average number of planets that can potentially support life per star that has planets
(f{l}) = the fraction of the above that actually go on to develop life at some point
(f{i}) = the fraction of the above that actually go on to develop intelligent life
(f_{c}) = the fraction of civilizations that develop a technology that releases detectable signs of their existence into space
(L) = the length of time for which such civilizations release detectable signals into space
New York City population 2010: 8,175,133
percentage women: 52.62%
20-26 years old: 10.8%
bachelor’s degree: 15.8% http://www.city-data.com/city/New-York-New-York.html