Secretary Problem

Explores optimal stopping in the classic Secretary Problem where N applicants are evaluated one by one.

Concept Overview

The Secretary Problem explores the mathematics of optimal stopping. Imagine evaluating a sequence of N applicants for a position. You observe them one by one in uniformly random rank order, with rank N being the absolute best. You can only choose to accept or reject an applicant immediately after their interview. Once rejected, an applicant cannot be recalled. The strategy is to reject the first r applicants to set a baseline record, and then hire the next applicant who is strictly better than all previous applicants.

Worked Example

Let N = 4 applicants be evaluated, and we reject the first r = 1 applicant. The number of possible arriving orders is 4! = 24.

When we observe the first applicant, they become our current best record. For any remaining applicant, we select them if they are better than the rejected applicant. If no remaining applicant is better than the first, we fail to hire ("No hire").

The exact probability of selecting the best overall applicant (rank 4) is calculated by enumerating all 24 orders. It turns out that 11 of the 24 orders result in selecting the best applicant. Thus the success probability is exactly 11/24, which is approximately 0.458333.

Start with N=4, r=1. Total permutations: 24.
For each sequence, reject the first applicant. This applicant sets the threshold.
Select the first subsequent applicant that strictly exceeds the threshold.
In exactly 11 out of 24 possible orderings, the applicant selected this way has the absolute maximum rank (4).
Success probability = 11 / 24.

Formula for success probability:
For r = 0: P(Success) = 1/N
For r > 0: P(Success) = (r/N) * Σ_j=r^N-1 (1/j)

Experiment

To see this in action using the interactive Secretary Problem module:

Set the Applicants N slider to 4.
Set the Rejected prefix r slider to 1.
Set the Displayed order dropdown to Ascending. Notice that you select the 2nd applicant (rank 2), which is not the best.
With N=4 and r=1, change Displayed order to Middle peak. The order is [1,2,4,3], so rank 2 is still hired at position 2. The rule stops before seeing the later peak.
The aggregate remains 11/24 when only the displayed order changes. Set Applicants N to 3, keep r=1 and Middle peak: the order [1,3,2] selects rank 3 at position 2, with aggregate success probability 1/2.

Limitations

Small N Constraints: The visualizer bounds N to a maximum of 8, enabling deterministic enumeration of up to 40,320 permutations. In reality, large N requires asymptotic approximations (like setting r ≈ N/e).
Fixed Relative Rankings: The classic problem assumes only relative ranks are observed. If applicant "scores" from a known distribution are visible, different optimal stopping strategies exist (e.g., full-information secretary problem).
Rounding: Exact probabilities are calculated internally using precise integer fractions, but the displayed decimal is rounded to 6 decimal places.

These probabilities assume a known N, distinct ranks, uniform random order, no recall and at most one hire. If no later record occurs, this specified policy reports No hire. Some textbooks index the first eligible stage r+1 instead of the number r rejected. Displayed absolute ranks help explain the trace; the policy needs only comparisons with previously observed ranks.

References

Thomas S. Ferguson, "Optimal Stopping and Applications" (UCLA) - A detailed mathematical treatise on optimal stopping rules, specifically covering the relative rank assumptions and calculations of the classic Secretary Problem.

This primary source outlines the problem statement, proofs of optimal thresholds, and expected payoffs for generalizations of the problem.

Secretary Problem