The Secretary Problem

Worked Solution

How to Think About It: This is the classical secretary problem. The intuition is simple: you need to see some candidates first to calibrate your standard, then hire the first one who beats everyone you have seen. If you set your threshold too low, you waste your "hire" on a mediocre early candidate. Too high, and you have already passed the best one. The optimal threshold balances exploration vs. exploitation.

Quick Estimate: For large $n$, the optimal rule skips about $n/e \approx 0.368n$ candidates (for $n = 100$: skip $37$, so $r = 38$), giving a success probability of about $1/e \approx 0.368$. So even with an infinite pool, you can pick the best candidate about 37% of the time -- remarkably good given you are choosing blind.

Approach: First derive $P(r, n)$, then optimize over $r$.

Formal Solution:

Part (i): Optimality of threshold strategies.

Consider any optimal strategy. At each step $k$, the decision to accept or reject depends only on the relative ranks of candidates seen so far (since values are continuous i.i.d., absolute values carry no extra information beyond relative ranks).

First, never accept a non-record: it is already beaten by someone earlier, so it cannot be the global best. So the only decisions are which records to accept.

*Value of stopping.* A record at position $k$ is the best of the first $k$. It is the global best exactly when the global best sits among the first $k$ positions, which has probability $k/n$; and this event is independent of the relative-rank pattern of the first $k-1$ candidates. So accepting a record at $k$ wins with probability $\frac{k}{n}$, which is increasing in $k$, whatever you have seen.

*Value of continuing.* Let $C_k$ be the best win probability achievable using only positions $k+1, \ldots, n$ (having rejected everything up to $k$). By the same independence, $C_k$ depends only on $k$. Also $C_{k} \ge C_{k+1}$: from position $k+1$ on, the player at stage $k$ can copy any rule available at stage $k+1$. So $C_k$ is non-increasing in $k$.

*Single crossing.* Optimal play accepts a record at $k$ iff $\frac{k}{n} \ge C_k$. If this holds at some $k$, then for every $j > k$, $\frac{j}{n} > \frac{k}{n} \ge C_k \ge C_j$, so it holds at $j$ too. Hence the set of positions where records are accepted is $\{r, r+1, \ldots, n\}$ for some $r$: skip the first $r-1$, then take the first record. That is exactly the threshold strategy.

Part (ii): Exact success probability.

With the threshold strategy (skip first $r-1$, then take the next record):

The best candidate is at position $k$ (each position equally likely with probability $1/n$). The strategy selects her if and only if: - $k \geq r$ (she is not in the exploration phase), AND - No candidate in positions $r, r+1, \ldots, k-1$ is a record at the time she appears -- equivalently, the best of the first $k-1$ candidates is among the first $r-1$.

The probability that the best of the first $k-1$ is among the first $r-1$ is $(r-1)/(k-1)$ (by symmetry of random orderings).

Summing over all possible positions of the best candidate:

$$P(r, n) = \sum_{k=r}^{n} \frac{1}{n} \cdot \frac{r-1}{k-1} = \frac{r-1}{n} \sum_{k=r}^{n} \frac{1}{k-1} = \frac{r-1}{n} \sum_{j=r-1}^{n-1} \frac{1}{j}, \qquad 2 \le r \le n$$

(For $r = 1$ you take the first candidate, so $P(1, n) = \frac{1}{n}$.) Check: $P(3, 6) = \frac{2}{6}\left(\frac12 + \frac13 + \frac14 + \frac15\right) = \frac{77}{180} \approx 0.428$, matching brute-force enumeration of all $720$ orders.

Asymptotic optimization. Let $x = r/n$ with $n \to \infty$. Then $\frac{r-1}{n} \to x$ and $\sum_{j=r-1}^{n-1} \frac{1}{j} \approx \ln\frac{n}{r} \to \int_{x}^{1} \frac{1}{t}\, dt$, so

$$P(r, n) \to x \int_{x}^{1} \frac{1}{t}\, dt = -x \ln x$$

Maximize $f(x) = -x \ln x$: setting $f'(x) = -\ln x - 1 = 0$ gives $x^{*} = 1/e$.

So $r^{*}/n \to 1/e$: skip about $n/e$ candidates. (Exact optimum from $P(r,n)$: $n = 10$ gives $r^{*} = 4$, i.e. skip $3$, with $P = 0.3987$; $n = 100$ gives $r^{*} = 38$, skip $37$, $P = 0.3710$.) The limiting success probability is:

$$P^{*} = -\frac{1}{e} \ln \frac{1}{e} = \frac{1}{e} \approx 0.3679$$

Answer: The exact success probability is $P(r, n) = \frac{r-1}{n}\sum_{j=r-1}^{n-1}\frac{1}{j}$ for $r \ge 2$ (and $P(1,n) = 1/n$). The optimal cutoff satisfies $r^{*}/n \to 1/e$ (skip about $n/e$ candidates, e.g. skip $37$ of $100$), and the success probability falls to the limit $1/e \approx 0.3679$.