Secretary Problem

Why Secretary Problem Matters

You may inspect a sequence of opportunities, but can accept only one. Each opportunity disappears forever when rejected. Waiting gives a better comparison sample, yet risks discarding the best option; choosing early avoids that risk but uses little information. The secretary problem makes this tradeoff precise as a problem of optimal stopping.

In the classical model, the number of candidates is known, their qualities are distinct, and their order is a uniformly random permutation. You can compare the current candidate with those already seen, but cannot inspect unseen candidates or recall rejected ones. The objective is to maximize the probability of selecting the single best candidate overall—not the expected numerical quality or an approximately good candidate.

The optimal rule has a simple shape: reject an initial sample, then accept the first later candidate better than everyone seen so far. For large populations, both the optimal skipped fraction and the best achievable success probability approach $1/e\approx0.3679$. These are asymptotic statements. For a small known population, the exact integer cutoff and its exact probability matter.

This lesson derives those finite probabilities, explains why a cutoff rule is optimal, and implements a controller that receives only a current record flag. A separate driver supplies comparisons and audits the eventual outcome. We use opportunities and hiring as mathematical motivations; actual decision processes can have recall, ties, uncertain horizons, multiple choices or nonrandom order, all of which change the problem. The prerequisite algorithm-analysis material helps separate the number of observations from the probability of success.

Core Concepts and Terminology

Fix a known horizon $n\ge1$. There are n distinct candidates in a uniformly random order: each of the $n!$ permutations is equally likely. After each observation, choose irrevocably between accepting the current candidate and ending the process, or rejecting it and continuing. At most one selection is allowed, and rejected candidates cannot be recalled. The permitted information consists of n, the position, and the relative ranking of candidates already observed.

The payoff is 1 if the chosen candidate is the unique global best, and 0 otherwise. The optimality claim is over all stopping rules using that relative-rank information, with probability taken over the random arrival order. The standard optimal cutoff policy is deterministic; no private random coin is needed to obtain its random-order probability. One fixed permutation has outcome either 0 or 1.

Call position k a record when its candidate is better than every earlier candidate. The first candidate is necessarily a record. A nonrecord cannot be globally best. Although the model allows the full relative ranking of the observed prefix, the optimal rule needs only whether the current candidate is a record. The controller in our programs receives that Boolean and cannot read absolute quality values.

Define r to mean the number initially rejected, with $0\le r\lt n$. Reject positions 1 through r unconditionally. Starting at position r+1, select the first record. Thus r=3 means the first eligible position is 4; some references instead name that first eligible position as their threshold. Match definitions before comparing formulas.

Our implementation always makes one choice by accepting the final candidate if no eligible record has appeared. If that final candidate is a nonrecord, this fallback necessarily loses, because a better candidate was already rejected. A version that makes no choice in the same situation also loses; therefore the fallback changes the selected position in those cases but leaves the best-selection success probability unchanged. If the last candidate is a record, it is accepted by the ordinary record rule first.

For debugging, the driver represents hidden qualities by a permutation of 1 through n, with larger labels better and n globally best. It knows the full test input, computes record flags from the observed prefix, and reveals full labels only in the final audit. The policy never receives those labels: giving it known absolute rank n would expose information forbidden in the relative-rank model. The diagrams' numerical quality annotations are auditor views, not extra policy inputs.

For example, n=8 has optimal r=3. After observing labels $[4,1,6]$, the relative ordering by arrival position is 3 above 1 above 2. Only the record flags $[1,0,1]$ have entered the policy, and all three candidates were rejected. Future order is still unknown, including whether anyone will beat the current prefix maximum. The diagram shows this information boundary.

How Secretary Problem Works, Step by Step

Choose the cutoff before any observations. For every possible skip count, compute its exact random-order success probability. If r=0, accept the first candidate, so

$$P_n(0)=\frac1n.$$

For $1\le r\lt n$, consider the position k of the global best. It must arrive after the sample. Conditional on its position, it is selected exactly when the best among the first k−1 candidates occurred within the initial r positions; otherwise a later record would already have caused an acceptance. The global best's position is uniform, and that earlier maximum's position is uniform within its prefix. Therefore

$$P_n(r)=\sum_{k=r+1}^{n}\frac1n\frac{r}{k-1}=\frac rn\sum_{j=r}^{n-1}\frac1j.$$

This condition remains valid with the final fallback, because selecting a nonrecord cannot add a success. The r=0 formula is separate; substituting zero into a harmonic expression containing $1/r$ is invalid.

The programs compare all finite cutoffs with integer scores. Let D be the least common multiple of 1 through n−1, with D=1 when that range is empty. Every probability can use denominator nD. The score for r=0 is D; for positive r it is $r\sum_{j=r}^{n-1}D/j$. An initial suffix sum and a one-term subtraction per candidate cutoff compute all scores in a linear number of arithmetic steps. Compare with strict greater-than so an equal probability retains the smallest skip count. In particular, n=2 has a tie between r=0 and r=1, and the automatic rule chooses r=0.

Separate comparison from stopping. A comparison adapter remembers the best candidate observed so far. On each actual observation it emits a Boolean indicating whether the new candidate is better, then updates its own prefix maximum. In a real comparison-only setting this can use a retained reference to the best seen candidate; the numerical labels here are only a test convenience. The stopping controller needs no numeric score or distribution of scores.

Process one observation. Validate that the flag is Boolean, the process is still open, and the first flag is true. Increment the seen count. If the position is at most r, return a sample-phase rejection even when the candidate is a record. Otherwise enter search: accept a record immediately; if it is not a record but the position is n, accept it as the final fallback; otherwise reject. A selection stores the chosen position permanently and closes the process.

Stop producing observations. As soon as the controller accepts, the driver breaks its observation loop. It does not call the policy on later positions. An attempted call after selection raises an exception without changing state. The final audit may inspect the full stored test input to identify the global best and report whether the chosen position won, but that result cannot alter the earlier choice.

For n=8, the exact scorer selects r=3. In the worked stream, positions 4 and 5 are nonrecords and are rejected. Position 6 is a record, so the policy accepts and stops. It does not ask whether positions 7 or 8 would be better. No parallel worker scheduling is needed here: each arrival is a sequential information event and a possible stopping point.

flowchart TD
    A["Known horizon: choose exact skip count before observations"] --> B["Initialize seen zero and no selection"]
    B --> C["Comparator reveals current record flag only"]
    C --> D{"Valid flag and open state?"}
    D -->|No| E["Reject call without changing state"]
    D -->|Yes| F["Increment observed position"]
    F --> G{"Position within initial sample?"}
    G -->|Yes| H["Reject current candidate"]
    G -->|No| I{"Current candidate is a record?"}
    I -->|Yes| J["Accept record and close selection"]
    I -->|No| K{"Final position?"}
    K -->|Yes| L["Accept last candidate and close selection"]
    K -->|No| H
    H --> C
    J --> M["Driver stops observing; evaluate outcome separately"]
    L --> M

Worked Example with a Full Trace

Use n=8 and hidden quality order $[4,1,6,2,5,8,3,7]$, with larger labels better. These labels describe the test input to the reader; the policy sees only record flags. Its initial state is seen=0, chosen=NONE. The exact scoring procedure selects r=3 before reading any candidate.

For the selected cutoff,

$$P_8(3)=\frac38\left(\frac13+\frac14+\frac15+\frac16+\frac17\right)=\frac38\cdot\frac{153}{140}=\frac{459}{1120}.$$

For comparison, r=2 gives $223/560=446/1120$, which is smaller. In this small case, simply taking $\lfloor8/e\rfloor=2$ misses the exact best cutoff. The large-n guide is useful intuition, not the implementation's finite optimizer.

1. Position 1, hidden quality 4. No earlier candidate exists, so the comparator sends record=true and remembers prefix maximum 4. The policy increments seen to 1. Since $1\le3$, sample phase rejects. Chosen remains NONE.
2. Position 2, quality 1. The adapter compares with 4, sends false and keeps maximum 4. Position 2 remains in the sample, so reject; seen=2, chosen=NONE.
3. Position 3, quality 6. The adapter sends true because $6\gt4$ and updates maximum to 6. The policy still rejects: position 3 is the last sampled candidate, not the first eligible one. Seen=3, chosen=NONE.
4. Position 4, quality 2. The adapter sends false because $2\lt6$. Position 4 is in search, but it is neither a record nor the last position. Reject; seen=4, chosen=NONE; comparator maximum remains 6.
5. Position 5, quality 5. Again false because $5\lt6$. Search rejects; seen=5, chosen=NONE; maximum remains 6.
6. Position 6, quality 8. The adapter sends true because $8\gt6$ and updates its maximum to 8. The policy sees search-phase record=true, accepts immediately and stores chosen=6. The returned action is ACCEPT_RECORD. Selection is now closed.
7. Position 7, hidden quality 3. Unobserved by the stopped policy. No flag is sent and no controller state changes. This value appears only when the driver later audits the complete input.
8. Position 8, hidden quality 7. Also unobserved; seen remains 6 and chosen remains 6.

The final audit finds quality 8 at the chosen position and confirms it is globally best, so this fixed permutation's outcome is 1. That is distinct from the exact success probability $459/1120\approx0.4098$ over uniform permutations. Even a perfectly implemented optimal rule loses on many valid input orders.

At every observed rejection in search, no record has appeared since the sample; otherwise the process would have closed already. Thus the adapter's maximum remains the sample maximum until the accepting record. This explains why “first later record” and “first later candidate exceeding the sample maximum” describe the same policy before selection, even though records are formally defined relative to all observed candidates.

Implementation in Python, C++, and Java

Each panel is standalone: run Python 3, compile C++17, or save the Java panel as Main.java and run Main after compiling. The common sample has eight candidates and selects its cutoff automatically. The three programs print byte-identical output below, using exact reduced fractions rather than floating-point cutoff comparisons.

The policy constructor receives only n and r. Its next-candidate method receives only a record flag. The full hidden quality array belongs to run_case/runCase, which validates a permutation of 1 through n, computes flags from the prefix, breaks immediately on selection, and evaluates the full-input outcome afterward. This deliberately gives the test driver more information than the decision-maker. No full-array maximum or quality label enters a policy call.

The supported exact-arithmetic range is $1\le n\le20$. Request −1 selects the best finite cutoff; an explicit request from 0 through n−1 uses that particular cutoff and reports its own success probability. The standalone sample requests the automatic mode. The policy itself requires a concrete legal r. Empty input, duplicate/missing audit labels, an illegal cutoff, a false first flag and calls after acceptance are errors. Python also checks integer/Boolean types explicitly; C++ and Java use their typed parameters. Validation precedes policy mutation.

For n≤20, D is at most 232,792,560 and nD is at most 4,655,851,200. C++ and Java use signed 64-bit integers for all common-denominator, score and probability arithmetic. A simple conservative bound on any intermediate score is $19\cdot19D$, still below 85 billion; this fits comfortably. Do not enlarge n without reviewing LCM growth and integer widths. Python integers are unbounded, but the shared limit deliberately keeps all three versions equivalent.

The output before AUDIT contains only information returned by the record-only controller. chosen=NONE means no acceptance yet; chosen positions are one-based. The first audit line lists positions never observed by the policy. The second exposes the hidden input, selected quality, global best and binary success. The displayed P(best) is a model probability computed before observations; success is the result of one completed test. Treat controller fields as read-only outside the supplied methods.

from dataclasses import dataclass
from math import gcd


def valid_n(n):
    if type(n) is not int or not 1 <= n <= 20:
        raise ValueError("n must be an integer from 1 through 20")


def fraction(a, b):
    divisor = gcd(a, b)
    return str(a // divisor) + "/" + str(b // divisor)


def strategy(n, requested=-1):
    valid_n(n)
    if type(requested) is not int or not -1 <= requested < n:
        raise ValueError("skip must be -1 for automatic, or from 0 through n-1")
    common = 1
    for j in range(1, n):
        common = common // gcd(common, j) * j
    tail = sum(common // j for j in range(1, n))
    best_skip, best_score = 0, common
    requested_score = common
    for skip in range(1, n):
        score = skip * tail
        if score > best_score:
            best_skip, best_score = skip, score
        if skip == requested:
            requested_score = score
        tail -= common // skip
    if requested == -1:
        return best_skip, best_score, n * common
    return requested, requested_score, n * common


@dataclass(frozen=True)
class Step:
    position: int
    record: bool
    phase: str
    action: str
    chosen: int


class SecretaryPolicy:
    def __init__(self, n, skip):
        valid_n(n)
        if type(skip) is not int or not 0 <= skip < n:
            raise ValueError("skip must be from 0 through n-1")
        self.n, self.skip = n, skip
        self.seen, self.chosen = 0, -1

    def next_candidate(self, record):
        if type(record) is not bool:
            raise ValueError("record flag must be boolean")
        if self.chosen != -1:
            raise ValueError("selection already closed")
        if self.seen == 0 and not record:
            raise ValueError("the first candidate must be a record")
        self.seen += 1
        phase = "SAMPLE" if self.seen <= self.skip else "SEARCH"
        action = "REJECT"
        if phase == "SEARCH":
            if record:
                action = "ACCEPT_RECORD"
                self.chosen = self.seen
            elif self.seen == self.n:
                action = "ACCEPT_LAST"
                self.chosen = self.seen
        return Step(self.seen, record, phase, action, self.chosen)


def shown(position):
    return "NONE" if position == -1 else str(position)


def numbers(values):
    return "[" + ",".join(map(str, values)) + "]"


def show_step(step):
    return ("i=" + str(step.position) + " record=" + str(int(step.record)) +
            " phase=" + step.phase + " action=" + step.action + " chosen=" + shown(step.chosen))


def run_case(qualities, requested=-1):
    n = len(qualities)
    skip, numerator, denominator = strategy(n, requested)
    if any(type(x) is not int for x in qualities) or sorted(qualities) != list(range(1, n + 1)):
        raise ValueError("audit input must be a permutation of 1 through n")
    policy = SecretaryPolicy(n, skip)
    lines = ["RULE n=" + str(n) + " skip=" + str(skip) + " P(best)=" + fraction(numerator, denominator)]
    best_seen = 0
    for value in qualities:
        record = value > best_seen
        best_seen = max(best_seen, value)
        step = policy.next_candidate(record)
        lines.append(show_step(step))
        if policy.chosen != -1:
            break
    selected = qualities[policy.chosen - 1]
    lines.append("AUDIT unobserved_positions=" + numbers(range(policy.seen + 1, n + 1)))
    lines.append("AUDIT order=" + numbers(qualities) + " choice=" + str(policy.chosen) +
                 " value=" + str(selected) + " best=" + str(n) + " success=" + str(int(selected == n)))
    return "\n".join(lines) + "\n"


def main():
    print(run_case([4, 1, 6, 2, 5, 8, 3, 7]), end="")


if __name__ == "__main__":
    main()

#include <algorithm>
#include <iostream>
#include <numeric>
#include <stdexcept>
#include <string>
#include <vector>

void valid_n(int n) {
    if (n < 1 || n > 20) throw std::invalid_argument("n must be from 1 through 20");
}
std::string fraction(long long a, long long b) {
    long long divisor = std::gcd(a, b);
    return std::to_string(a / divisor) + "/" + std::to_string(b / divisor);
}
struct Strategy { int skip; long long numerator, denominator; };
Strategy strategy(int n, int requested = -1) {
    valid_n(n);
    if (requested < -1 || requested >= n)
        throw std::invalid_argument("skip must be -1 for automatic, or from 0 through n-1");
    long long common = 1;
    for (int j = 1; j < n; ++j) common = common / std::gcd(common, 1LL*j) * j;
    long long tail = 0;
    for (int j = 1; j < n; ++j) tail += common / j;
    int best_skip = 0;
    long long best_score = common, requested_score = common;
    for (int skip = 1; skip < n; ++skip) {
        long long score = skip * tail;
        if (score > best_score) { best_skip = skip; best_score = score; }
        if (skip == requested) requested_score = score;
        tail -= common / skip;
    }
    if (requested == -1) return {best_skip, best_score, n * common};
    return {requested, requested_score, n * common};
}

struct Step {
    int position;
    bool record;
    std::string phase, action;
    int chosen;
};
class SecretaryPolicy {
public:
    int n, skip, seen = 0, chosen = -1;
    SecretaryPolicy(int count, int rejected) : n(count), skip(rejected) {
        valid_n(n);
        if (skip < 0 || skip >= n) throw std::invalid_argument("skip must be from 0 through n-1");
    }
    Step next_candidate(bool record) {
        if (chosen != -1) throw std::invalid_argument("selection already closed");
        if (seen == 0 && !record) throw std::invalid_argument("the first candidate must be a record");
        ++seen;
        std::string phase = seen <= skip ? "SAMPLE" : "SEARCH";
        std::string action = "REJECT";
        if (phase == "SEARCH") {
            if (record) { action = "ACCEPT_RECORD"; chosen = seen; }
            else if (seen == n) { action = "ACCEPT_LAST"; chosen = seen; }
        }
        return {seen, record, phase, action, chosen};
    }
};
std::string shown(int position) { return position == -1 ? "NONE" : std::to_string(position); }
std::string numbers(const std::vector<int>& values) {
    std::string out = "[";
    for (std::size_t i = 0; i < values.size(); ++i) {
        if (i) out += ",";
        out += std::to_string(values[i]);
    }
    return out + "]";
}
std::string show_step(const Step& step) {
    return "i=" + std::to_string(step.position) + " record=" + (step.record ? "1" : "0") +
           " phase=" + step.phase + " action=" + step.action + " chosen=" + shown(step.chosen);
}
std::string run_case(const std::vector<int>& qualities, int requested = -1) {
    int n = static_cast<int>(qualities.size());
    Strategy plan = strategy(n, requested);
    std::vector<int> sorted = qualities;
    std::sort(sorted.begin(), sorted.end());
    for (int i = 0; i < n; ++i)
        if (sorted[i] != i + 1) throw std::invalid_argument("audit input must be a permutation of 1 through n");
    SecretaryPolicy policy(n, plan.skip);
    std::string out = "RULE n=" + std::to_string(n) + " skip=" + std::to_string(plan.skip) +
                      " P(best)=" + fraction(plan.numerator, plan.denominator) + "\n";
    int best_seen = 0;
    for (int value : qualities) {
        bool record = value > best_seen;
        best_seen = std::max(best_seen, value);
        Step step = policy.next_candidate(record);
        out += show_step(step) + "\n";
        if (policy.chosen != -1) break;
    }
    std::vector<int> unobserved;
    for (int i = policy.seen + 1; i <= n; ++i) unobserved.push_back(i);
    int selected = qualities[policy.chosen - 1];
    out += "AUDIT unobserved_positions=" + numbers(unobserved) + "\n";
    out += "AUDIT order=" + numbers(qualities) + " choice=" + std::to_string(policy.chosen) +
           " value=" + std::to_string(selected) + " best=" + std::to_string(n) +
           " success=" + (selected == n ? "1" : "0") + "\n";
    return out;
}
int main() {
    std::cout << run_case({4, 1, 6, 2, 5, 8, 3, 7});
    return 0;
}

import java.util.Arrays;

public class Main {
    static void validN(int n) {
        if (n < 1 || n > 20) throw new IllegalArgumentException("n must be from 1 through 20");
    }
    static long gcd(long a, long b) {
        while (b != 0) { long remainder = a % b; a = b; b = remainder; }
        return a;
    }
    static String fraction(long a, long b) {
        long divisor = gcd(a, b);
        return (a / divisor) + "/" + (b / divisor);
    }
    static final class Strategy {
        final int skip;
        final long numerator, denominator;
        Strategy(int skip, long numerator, long denominator) {
            this.skip = skip; this.numerator = numerator; this.denominator = denominator;
        }
    }
    static Strategy strategy(int n, int requested) {
        validN(n);
        if (requested < -1 || requested >= n)
            throw new IllegalArgumentException("skip must be -1 for automatic, or from 0 through n-1");
        long common = 1;
        for (int j = 1; j < n; ++j) common = common / gcd(common, j) * j;
        long tail = 0;
        for (int j = 1; j < n; ++j) tail += common / j;
        int bestSkip = 0;
        long bestScore = common, requestedScore = common;
        for (int skip = 1; skip < n; ++skip) {
            long score = skip * tail;
            if (score > bestScore) { bestSkip = skip; bestScore = score; }
            if (skip == requested) requestedScore = score;
            tail -= common / skip;
        }
        if (requested == -1) return new Strategy(bestSkip, bestScore, n * common);
        return new Strategy(requested, requestedScore, n * common);
    }
    static final class Step {
        final int position, chosen;
        final boolean record;
        final String phase, action;
        Step(int position, boolean record, String phase, String action, int chosen) {
            this.position = position; this.record = record; this.phase = phase;
            this.action = action; this.chosen = chosen;
        }
    }
    static final class SecretaryPolicy {
        final int n, skip;
        int seen = 0, chosen = -1;
        SecretaryPolicy(int n, int skip) {
            validN(n);
            if (skip < 0 || skip >= n) throw new IllegalArgumentException("skip must be from 0 through n-1");
            this.n = n; this.skip = skip;
        }
        Step nextCandidate(boolean record) {
            if (chosen != -1) throw new IllegalArgumentException("selection already closed");
            if (seen == 0 && !record) throw new IllegalArgumentException("the first candidate must be a record");
            ++seen;
            String phase = seen <= skip ? "SAMPLE" : "SEARCH";
            String action = "REJECT";
            if (phase.equals("SEARCH")) {
                if (record) { action = "ACCEPT_RECORD"; chosen = seen; }
                else if (seen == n) { action = "ACCEPT_LAST"; chosen = seen; }
            }
            return new Step(seen, record, phase, action, chosen);
        }
    }
    static String shown(int position) { return position == -1 ? "NONE" : Integer.toString(position); }
    static String numbers(int[] values) {
        StringBuilder out = new StringBuilder("[");
        for (int i = 0; i < values.length; ++i) {
            if (i > 0) out.append(',');
            out.append(values[i]);
        }
        return out.append(']').toString();
    }
    static String showStep(Step step) {
        return "i=" + step.position + " record=" + (step.record ? "1" : "0") +
               " phase=" + step.phase + " action=" + step.action + " chosen=" + shown(step.chosen);
    }
    static String runCase(int[] qualities, int requested) {
        int n = qualities.length;
        Strategy plan = strategy(n, requested);
        int[] sorted = qualities.clone(); Arrays.sort(sorted);
        for (int i = 0; i < n; ++i)
            if (sorted[i] != i + 1) throw new IllegalArgumentException("audit input must be a permutation of 1 through n");
        SecretaryPolicy policy = new SecretaryPolicy(n, plan.skip);
        StringBuilder out = new StringBuilder("RULE n=" + n + " skip=" + plan.skip +
                                             " P(best)=" + fraction(plan.numerator, plan.denominator) + "\n");
        int bestSeen = 0;
        for (int value : qualities) {
            boolean record = value > bestSeen; bestSeen = Math.max(bestSeen, value);
            Step step = policy.nextCandidate(record);
            out.append(showStep(step)).append('\n');
            if (policy.chosen != -1) break;
        }
        int[] unobserved = new int[n - policy.seen];
        for (int i = 0; i < unobserved.length; ++i) unobserved[i] = policy.seen + 1 + i;
        int selected = qualities[policy.chosen - 1];
        out.append("AUDIT unobserved_positions=").append(numbers(unobserved)).append('\n');
        out.append("AUDIT order=").append(numbers(qualities)).append(" choice=").append(policy.chosen)
           .append(" value=").append(selected).append(" best=").append(n)
           .append(" success=").append(selected == n ? 1 : 0).append('\n');
        return out.toString();
    }
    public static void main(String[] args) {
        System.out.print(runCase(new int[] {4, 1, 6, 2, 5, 8, 3, 7}, -1));
    }
}

Identical expected output (each item below is one printed line):

• RULE n=8 skip=3 P(best)=459/1120
• i=1 record=1 phase=SAMPLE action=REJECT chosen=NONE
• i=2 record=0 phase=SAMPLE action=REJECT chosen=NONE
• i=3 record=1 phase=SAMPLE action=REJECT chosen=NONE
• i=4 record=0 phase=SEARCH action=REJECT chosen=NONE
• i=5 record=0 phase=SEARCH action=REJECT chosen=NONE
• i=6 record=1 phase=SEARCH action=ACCEPT_RECORD chosen=6
• AUDIT unobserved_positions=[7,8]
• AUDIT order=[4,1,6,2,5,8,3,7] choice=6 value=8 best=8 success=1

Complexity, Correctness, and Invariants

State correctness. Before selection, seen is exactly the number of flags processed and chosen is NONE. Sampling rejects every position at most r. In search, every rejected candidate was a nonrecord; the first record is accepted, otherwise the final candidate is accepted. After selection, chosen never changes, the driver stops requesting observations, and any extra policy call fails without mutation. Initialization establishes the invariant, and each branch either advances one position under these rules or closes the process once. The comparison adapter separately maintains the maximum of exactly the observed prefix, so its record flag is correct.

Why cutoff rules suffice. A nonrecord has zero chance of being global best, so accepting it early cannot improve the best-selection objective. At position k, conditional on a record, the chance it is globally best is $k/n$. Under a uniformly random permutation the successive relative ranks are independent and uniform on their respective prefix sizes. Hence the conditional continuation value depends on position, not on the detailed earlier relative ordering.

Let $V_k$ be the optimal success probability before observing position k, provided no selection has occurred, and set $V_{n+1}=0$. Backward induction gives

$$V_k=\frac1k\max\left(\frac kn,V_{k+1}\right)+\left(1-\frac1k\right)V_{k+1}.$$

A record occurs with probability $1/k$. At that record, stop if $k/n\ge V_{k+1}$; otherwise continue. At a nonrecord, continue unless the final forced choice is required, which has payoff zero when it is a nonrecord. The recurrence gives $V_k\ge V_{k+1}$, while $k/n$ increases with k. Once accepting a record is optimal, it remains optimal at all later positions. Thus an optimal rule is a cutoff followed by acceptance of records; enumerating all r includes an optimal rule among all admissible relative-rank policies. Randomizing between actions cannot beat the larger of the two conditional payoffs.

Finite cutoff optimization. The harmonic success formula follows from partitioning the winning event by the global best's position. For $0\le r\le n-2$, consecutive probabilities satisfy

$$P_n(r+1)-P_n(r)=\frac1n\left(\sum_{j=r+1}^{n-1}\frac1j-1\right).$$

At r=0 this identity follows directly from the separate first-candidate formula. The tail sum decreases with r, so the probability sequence rises, may tie at its peak, then falls. The smallest optimal skip count is the first r for which that tail is at most 1, with the empty-tail convention covering n=1. The code instead compares every exact common-denominator score, avoiding both harmonic floating-point rounding and threshold-index ambiguity. The smallest-r tie policy is part of its deterministic output, not a requirement that all optimal cutoffs be unique.

Asymptotic 1/e rule. If $r/n\to\alpha$ for $0\lt\alpha\lt1$, then

$$P_n(r)\to\alpha\int_{\alpha}^{1}\frac{dx}{x}=-\alpha\ln\alpha.$$

Its derivative is $-\ln\alpha-1$, so the maximum occurs at $\alpha=e^{-1}$ with value $e^{-1}$. Thus the optimal skipped fraction and optimal success probability both tend to 1/e, although they are different quantities at finite n. For n=8, the skipped fraction is $3/8$ while the success probability is $459/1120$. This guarantee is neither a per-permutation promise nor a competitive ratio on numerical quality values.

Running time and observations. Given a cutoff and a record flag, the policy uses $\Theta(1)$ work and O(1) scalar state per observation. A comparison adapter needs one prefix-best reference and one comparison per later observation. With r=0 it stops at the first candidate. For positive r, the earliest choice is r+1 and the latest is n. At the optimal asymptotic cutoff, both are $\Theta(n)$; in general report the actual stopping position T rather than assuming every run reads all n candidates.

Under uniform random order and our final-candidate fallback, for $r\ge1$,

$$\Pr(T\gt k)=\frac rk\quad(r\le k\lt n),\qquad \mathbb E[T]=r+r\sum_{k=r}^{n-1}\frac1k=r+nP_n(r).$$

The first equality says no post-sample record has occurred among the first k candidates, exactly when that prefix's maximum lies in the initial sample. Summing the tail probabilities includes the r certain initial observations. For r=0, T=1. At the large-n optimum the expected observed fraction tends to $2/e$, not $1/e$: the latter is the success probability and skipped fraction, not the average stopping fraction. For the sample's policy, $\mathbb E[T]=879/140$, while this particular permutation stops at T=6.

The exact cutoff scorer uses O(n) arithmetic/gcd operations and O(1) scalar accumulators; with the bounded machine integers here that gives linear preparation time. The LCM grows with n, so an unbounded exact-arithmetic implementation must account for larger-integer bit costs instead of claiming constant-cost arithmetic forever. The online policy does not store a history. Its counters require O(log n) bits when the horizon grows, despite using a constant number of scalars.

The demonstration driver stores the entire permutation, sorts a validation copy in $O(n\log n)$ comparison time and O(n) storage, formats observed receipts, and prints the full offline audit. Those costs are separate from the streaming policy. Keeping T receipts adds O(T) records; the returned textual trace/audit has $O((T+n)\log n)$ characters for these integer labels. Enumeration over all n! permutations is a test method, not the runtime of an online decision.

The programs were checked on every permutation and every cutoff through n=7, verifying 28 exact success probabilities against observed counts, plus mixed tests through n=20. An independent backward-induction calculation checks the optimal value for each supported n. The checks also cover end fallback, smallest-cutoff ties, identical observed prefixes with different futures, input errors, first-flag validity and state preservation after a closed-call rejection.

Variants, Pitfalls, and Optimizations

Do not confuse best so far with best overall. A record certifies only a relative prefix comparison. If a larger candidate arrives after acceptance, the policy has already closed. This is an allowed loss, not an implementation failure. A driver that computes the full-array maximum first and waits for it can report perfect performance only by supplying forbidden future information. The diagram contrasts indistinguishable relative prefixes whose eventual outcomes differ.

Keep the random-order assumption explicit. The probability is uniform over permutations of a fixed set of distinct qualities. It is not a guarantee for an adversarial order, and a fixed cutoff can be defeated by placing the best candidate in its rejected sample. With r=0, placing a non-best first also forces failure for n>1. Observed hiring or market order may be correlated with quality; a simulation should not assume it is uniform merely because its data arrived sequentially. A uniformly shuffled test permutation is a modeling choice, not evidence about real arrival processes.

The 37% rule has two limits and an indexing convention. Skip approximately n/e candidates for large n; the chance of selecting the best also tends to 1/e. Neither says to select exactly at position n/e, to choose any candidate above a fixed numerical score, or to expect to stop after 37% of the stream. The exact mean stopping fraction at the asymptotic optimum is 2/e under the fallback convention here. For small n, compare exact integer cutoffs; r=3 for n=8 is different from floor(8/e)=2. Some texts use r for the first selectable position, shifting the skip count by one.

Handle the final position deliberately. Our fallback always selects someone. Without it, a record-only version may end unselected. Both fail to select the best on the no-later-record event, but their selection counts and stopping-time conventions can differ. Report whether a test measures success probability, probability of any selection, expected rank, or observation cost. For n=1, select the only candidate; reject n=0 as outside this problem instead of inventing a probability.

Ties need a revised quality model. The classical proof assumes a unique total order. Treating equality as a record, randomly breaking ties, choosing any maximum, and selecting a particular unique winner define different success events. The audit driver rejects duplicate labels. A meaningful tied-score extension must state its tie-breaking and objective before changing the comparison operator.

Unknown horizons and additional information change optimal stopping. If n is unknown or random, the cutoff cannot be computed from the realized future length without leaking information. A known distribution over the horizon leads to a different dynamic program. Full-information models use actual observed values and a stated distribution, so magnitudes can matter. Recall, selection costs, multiple accepted candidates, top-k success, expected rank and expected value lead to other stopping rules; the classical best-choice proof does not establish their optimum.

Extensions have different benchmarks. Prophet inequalities typically compare expected selected value with a full-information benchmark under distributional assumptions. Matroid-secretary settings permit several selections subject to an independence constraint and optimize total weight. They are important next steps but do not inherit this scalar best-choice success formula. The existing queue prerequisite does not require buffering future candidates: putting unseen observations into a decision-visible queue would violate the intended information boundary.

Keep experiments reproducible and causal. Use exact enumeration only for tiny n. For larger n, sample uniformly shuffled permutations with a documented generator and seed, count wins across independent runs and report uncertainty. Never tune r after seeing the particular test permutation while evaluating a supposedly precommitted rule. Share the same permutation across policies to compare their outcomes, but do not expose it to their controllers. Preserve chosen positions after selection and keep any hindsight labels clearly within audit output.

Practice Problems and Real-World Use

Start with tiny populations. Enumerate all n! permutations for each cutoff and compare the fraction of wins with the harmonic formula. Check n=1, the n=2 tie, increasing and decreasing orders, best-in-sample failures, first-search-position successes, late records and nonrecord final fallback. Separately compute the finite optimum by backward induction and compare its value with the best cutoff probability.

Audit causality at the observation level. Two inputs with the same relative-rank history must produce the same actions until that history diverges. The policy should see no hidden quality array or global-best label. Once it chooses, no later candidate should be observed through its interface. Submit a false first record flag or a call after acceptance and confirm that the state remains unchanged. The small program's known rank labels are only for validating these tests.

For a simulation report, distinguish the skipped fraction r/n, empirical success rate, exact model probability and mean stopping position. They answer different questions. Exact enumeration has no sampling error but factorial cost; Monte Carlo has sampling uncertainty. For n=8, the exact probability 459/1120 gives 16,524 wins among all 40,320 permutations at r=3, an additional manageable exhaustive exercise.

The application rows below are modeling exercises, not claims that an abstract hiring rule should govern actual hiring or any named production system. Sequential offer selection can resemble optimal stopping only when the information, payoff, recall and arrival assumptions match. Before importing the cutoff, decide whether “best” is even the right objective and whether the horizon and random-order assumptions are justified.

Primary reading: Thomas Ferguson's finite-horizon stopping chapter states the classical assumptions and develops the relative-rank threshold argument. His historical article, Who Solved the Secretary Problem? provides context and variants. Watch the cutoff convention: this lesson's r counts rejected candidates. The record-only interface, final-fallback convention, exact integer scorer, audit format and cross-language tests above are specific to this lesson.