A sultan has granted a commoner a chance to marry one of his $N$ daughters. The commoner will be presented with the daughters one at a time and, when each daughter is presented, the commoner will be told the daughter’s dowry (which is fixed in advance). Upon being presented with a daughter, the commoner must immediately decide whether to accept or reject her (he is not allowed to return to a previously rejected daughter). However, the sultan will allow the marriage to take place only if the commoner picks the daughter with the overall highest dowry. Then what is the commoner’s best strategy, assuming he knows nothing about the distribution of dowries (Mosteller 1987)?
From MathWorld. For those who are bland, this question is also known as the “secretary problem” where the idea is that you’re looking to hire the best candidate.
If our commoner decides to blindly choose the first daughter presented to him, perhaps wanting to get the heck away from this eccentric sultan, he only gets the girl with probability $1/N$. Similarly, if he waits until the very last one, he also only wins with probability $1/N$. On the other hand, every daughter he declines gives him some information, because every subsequent daughter with a smaller dowry than one he has already skipped certainly can’t be the one with the largest. So the commoner has a trade-off between gaining information (by skipping more daughters) and increasing the risk of losing the game (by skipping over the top pick). So between the two extremes there must be an optimum number $S^*$ of daughters to skip, after which the commoner should pick the first daughter whose dowry is larger than that of any those skipped. What is $S^*$, and what is his probability of winning with this strategy?
Method 1: The Ham-Fisted Approach
The probability that the highest-ranking daughter among the $S$ skipped has the $k$-th highest dowry of them all is:
$$\displaystyle P(k = \text{minimum rank among first }S) = \frac{\binom{k-1}{0} \binom{1}{1} \binom{N-k}{S-1}}{\binom{N}{S}} $$
because we want to choose none of the $k-1$ higher-ranking daughters, and the only $k$-ranked one, and the other $S-1$ have to come from the $N-k$ of lower rank (note that the first two factors in the numerator are both $1$). Now the probability that the first unskipped daughter who outranks all the skipped ones is also the top-ranked among them all is just $1/(k-1)$, because there are $k-1$ higher-ranked daughters and they can come up in any order. So we can write the probability of winning as:
$$\displaystyle P_1 = P(\text{win after skipping }S) = \sum_{k=2}^N \frac{1}{k-1} \frac{\binom{N-k}{S-1}}{\binom{N}{S}} $$
which adds up the probabilities that the best of the skipped $S$ is actually rank $k$, for all possible values of $k$. This expression is rather cumbersome, and after some “simplifications” it doesn’t get much better:
$$\displaystyle P_1 = \frac{1}{\binom{N}{S}} \sum_{k=1}^{N-S} \frac{1}{k}\frac{S}{N-k} \binom{N-k}{S} $$
Good luck trying to get an optimal $S$ out of that.
Method 2: Reasoning by Probabilities
The complexity of that expression ultimately comes from inquiring about the minimum rank of the first $S$ daughters, which led to introducing all the binomial coefficients. But we don’t need to solve the problem that way. Instead, we can obtain the answer by asking about the probability that the $k$-th daughter is chosen and that she is the best one, then continually rewriting that probability in convenient ways:
$$\displaystyle \begin{aligned} P_2 &= P(\text{win after skipping }S) \\ &= \sum_{k=1}^N P(k\text{ is chosen and is best}) \\ &= \sum_{k=S+1}^N P(k\text{ is chosen} | k\text{ is best})P(k\text{ is best}) \\ &= \sum_{k=S+1}^N P\left( \substack{\text{best of the first } k-1 \\ \text{is in the first }S} \right) P(k\text{ is best}) \end{aligned} $$
The fourth line follows from the third because if the $k$-th daughter presented is actually the top-ranked one, the commoner will choose her only if he hasn’t already chosen another (since she is by definition also the best he has seen so far). That happens if and only if the best that he has seen so far was in the skipped set. This happens with probability $S/(k-1)$, and the probability that the $k$-th daughter is actually the top one is of course $1/N$. So we have a much simpler expression for the probability we want:
$$\displaystyle P_2(S) = \frac{1}{N}\sum_{k=S+1}^N \frac{S}{k-1} = \frac{S}{N}\sum_{k=S}^{N-1} \frac{1}{k}$$
$$\displaystyle P_2(S) = \frac{S}{N}\left( H_{N-1} – H_{S-1} \right)$$
where $H_r$ is a harmonic number:
$$\displaystyle H_{r} = 1 + \frac12 + \frac13 + \cdots + \frac{1}{r} $$
In fact, since $P_1$ must equal $P_2$ we have a rather non-obvious identity:
$$\displaystyle \sum_{k=2}^N \frac{1}{k-1} \frac{\binom{N-k}{S-1}}{\binom{N}{S}} = \frac{S}{N}\sum_{k=S}^{N-1} \frac{1}{k} $$
And these sums are not even just adding up the same fractions in the same order, as can be confirmed by plugging in some values.
Obtaining $S$
We want to find the $S$ for which $P_2$ is maximized. As mentioned at the beginning, if the commoner skips $S=0$ then $P_2 = 1/N$, as it is when $S=N-1$. So $P_2$ must start increasing, then at some point turn to decreasing back to $1/N$ at some point. Put another way, we’re looking for the $S$ for which any larger $S$ does more harm than good. This $S$ must be the smallest S for which:
$$\displaystyle \begin{aligned} P_2(S+1) &< P_2(S) \\ \frac{S+1}{N}\left( H_{N-1} – H_{S} \right) &< \frac{S}{N}\left( H_{N-1} – H_{S-1} \right) \\ \left(1 + \frac{1}{S}\right)\left( H_{N-1} – H_S \right) &< H_{N-1} – H_{S-1} \\ \frac{1}{S}\left( H_{N-1} – H_S\right) &< H_S – H_{S-1} = \frac{1}{S} \\ H_{N-1} – H_S &< 1 \end{aligned}$$
Put another way, the $S$ for which:
$$\displaystyle \frac{1}{S+1} + \frac{1}{S+2} + \cdots + \frac{1}{N-1} < 1 $$
and also:
$$\displaystyle \frac{1}{S} + \frac{1}{S+1} + \frac{1}{S+2} + \cdots + \frac{1}{N-1} > 1 $$
Let $S = S^*$ be this optimum value of $S$. One could figure it out by trial-and-error, but an interesting relationship emerges as $N$ becomes large. Using the fact that:
$$\displaystyle \int_{S}^N \frac{1}{x}\,dx = \ln\left(\frac{N}{S}\right) = H_{N-1} – H_{S} + \mathcal{O}\left(\frac{1}{N},\frac{1}{S}\right)$$
and since, from the foregoing discussion, at the optimum $S=S^*$:
$$\displaystyle H_{N-1} – H_{S^*} = 1 + \mathcal{O}\left(\frac{1}{S^*}\right) $$
we have that:
$$\displaystyle \lim_{S^*\to\infty} \ln\left(\frac{N}{S^*}\right) = 1$$
so
$$\displaystyle \lim_{S^*\to\infty} \frac{N}{S^*} = e$$
So the commoner’s optimal strategy is to skip the first $1/e$ of the total number of daughters, then pick the best one he sees after that. Coincidentally, the probability of success following this strategy is also $1/e$, as seen from plugging the limiting value of $S^*/N$ back into the expression for $P_2(S^*)$ and using the fact established above that the sum in $P_2(S^*)$ approaches $1$. Interestingly, the chance of success depends only very slightly on the total number of daughters if their number is large enough.
All things considered, a chance of success of $1/e = 36.788\%$ is pretty good!