Imagine you want to hire exactly one secretary. There is a fixed number, say, \(N\) persons available for this job and you may invite each of them for an interview. However, you have to tell each one right after the interview if you will hire her. Now, what is your strategy?
Keep in mind that you have to hire the last candidate if you didn't hire one before.
To make things more precise, here are a few, somewhat natural, assumptions. The \(n\)-th candidate has a qualification \(X_n\) which is uniformly distributed with values between 0 (the worst secretary to hire) and 1 (this is the secretary you are dreaming of). You learn about the qualification of each candidate when you interview her. The qualifications are independent.
You may wish to pause for a second to test your intuition: If you have, say, 10 candidates, how good a secretary do you think you can expect?
The threshold strategy
In the language of probability theory, a strategy is a stopping time \(T\) and your task is to maximize the expected score \(E(X_T)\).
A possible strategy \(T_q\) would be to make up a threshold \(q\) and then to pick the first candidate that is better than this. We compute $$ \begin{aligned} E (X_{T_q}) & = \sum_{n=1}^N E(X_n; X_n \geqslant q, (\forall k < n) X_k < q) + E (X_N ; (\forall k \leqslant N) X_k < q)\\ & = \sum_{n=1}^N q^{n-1} E(X_n; X_n \geqslant q) + q^{N-1} E(X_N; X_N < q)\\ & = \frac{1}{2} \left( (1-q^2) \sum_{n=0}^{N-1} q^n + q^{N + 1} \right)\\ & = \frac{1}{2} (1+q-q^N) . \end{aligned} $$ This is the qualification we can expect when hiring a secretary using the strategy \(T_q\). It is maximized if we choose $$ q_0 = \left( \frac{1}{N} \right)^{\frac{1}{N - 1}}. $$ In particular, for \(N=10\) we find \(q_0 \approx .774\) and \(E(X_{T_{q_0}}) \approx 0.848\). This is a, possibly, surprisingly high expected qualification. In fact, we can't do much better.
Just hiring the best
What if you didn't have to make a decision right after each interview? That is, you could meet with all of them, determine their qualification and then retrospectively choose the best. The expected highest qualification is $$ E \left( \max_{1 \leqslant n \leqslant N} X_n \right) = \int_0^{\infty} 1-P \left( \max_{1 \leqslant n \leqslant N} X_n \leqslant x \right) d x = \int_0^1 1-x^N d x = \frac{N-1}{N}. $$ For \(N=10\) candidates the expected qualification is \(10/11 \approx 0.909\).
The optimal strategy
Now, let's get back to the original problem where you have to decide about a candidate right after the interview. To find the optimal strategy \(T^{(N)}\) we proceed inductively. Clearly, \(T^{(1)} = 1\) since we have to hire the one available candidate. Suppose we know \(T^{(N-1)}\). When interviewing the first out of \(N\) candidates we keep in mind that the strategy \(T^{(N-1)}\) applied to the \(N-1\) upcoming candidates yields an expected capability score of, say, \(q_{N-1}\). We therefore accept the first candidate if and only if she is better than this. Hence, $$ T^{(N)} = \left\{ \begin{array}{ll} 1 & \text{if \(X_1 > q_{N-1}\)},\\ 1 + T^{(N-1)} & \text{otherwise} \end{array} \right. $$ and $$ q_N = E(X_{T_N}) = E(X_1; X_1 \geqslant q_{N-1}) + E(X_{1+T_{N-1}}; X_1 < q_{N-1}) = \frac{1}{2}(1+q_{N-1}^2). $$ Together with \(q_1=1/2\), this defines the \(q_n\) recursively. Note that the recurrence for \(q_n\) ensures that \(q_n \rightarrow 1\) as \(n \rightarrow \infty\). In particular, \(q_{10} \approx 0.861\), that is, having ten candidates we can expect a score of \(0.861\).
Throwing in some mathematical finance
The previous strategy is, if you think about it, by construction optimal. Interestingly, we can, somewhat mechanically, also find this strategy using machinery from mathematical finance which is usually used when it comes to finding fair values for American options (which in contrast to European options can be executed any time).
Definition: The Snell envelope of a stochastic process \((X_n)\) is the smallest supermartingale (with respect to the filtration \(\mathcal{F}_n = \sigma(X_1, \ldots, X_n)\)) dominating \((X_n)\).
For a discrete process \((X_n)_{1 \leqslant n \leqslant N}\) the Snell envelope \((Y_n)_{1 \leqslant n \leqslant N}\) can be recursively constructed as follows: $$ Y_N = X_N, \hspace{1em} Y_n = X_n \vee E(Y_{n+1}| \mathcal{F}_n), $$ where we first define \(Y_N\), then \(Y_{N-1}\) and so on by enforcing that the two conditions \(Y_n \geqslant X_n\) and \(Y_n \geqslant E(Y_{n+1}| \mathcal{F}_n)\) hold. The utility of the Snell envelope is that it provides a solution to the general problem of finding a stopping time \(T\) which maximizes \(E(X_T)\).
Theorem: Let \((X_n)_{1 \leqslant n \leqslant N}\) be a process, and \((Y_n)_{1 \leqslant n \leqslant N}\) its Snell envelope. Then \(T = \min \{n : X_n = Y_n \}\) maximizes \(E(X_S)\) among all stopping times \(S\).
Consider again the problem of hiring a secretary. In this setting, the Snell envelope is constructed as follows $$ \begin{aligned} Y_N & = X_N,\\ Y_{N-1} & = X_{N-1} \vee E(Y_N| \mathcal{F}_{N-1}) = X_{N-1} \vee 1/2,\\ Y_{N-2} & = X_{N-2} \vee E(Y_{N-1}| \mathcal{F}_{N-2}) = X_{N-2} \vee E (X_{N-1} \vee 1/2),\\ & \vdots \end{aligned} $$ and we see that \(Y_n = X_n \vee q_{N-n}\), where $$ q_1 = 1 / 2, \hspace{1em} q_n = E(X_1 \vee q_{n-1}) = \frac{1}{2}(1+q_{n-1}^2). $$ The resulting (optimal) strategy indeed nicely coincides with the strategy we considered previously.
Further reading
This problem is an instance of what is considered in the theory of optimal stopping. A variation of the secretary problem is to rank the candidates instead of assigning a qualification to each of them. During the interview, you then don't learn the absolute qualification of the candidate but only how she performed in comparison to the previous ones.