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 threshold turns out to be around $n/e \approx 0.368n$, 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).

Suppose the optimal strategy says "reject" at position $k$ when the current candidate is a record (best so far). A record at position $k$ is the global best with conditional probability $k/n$ (it beats the first $k-1$ candidates by assumption, and it is the overall best iff it also beats the remaining $n-k$, which happens with probability $k/n$). So the *value of stopping* on a record, $k/n$, is increasing in $k$, while the *value of continuing* (the chance of catching the global best later) decreases as $k$ grows. Hence once it becomes optimal to accept a record at some position, it stays optimal at every later position: the set of positions where you accept records must be an up-set of the form $\{r, r+1, \ldots, n\}$ for some threshold $r$. 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}$$

Asymptotic optimization. Let $x = r/n$ with $n \to \infty$. The sum becomes a Riemann integral:

$$P(r, n) \approx 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$.

The optimal threshold is $r^{*} \approx n/e$, and 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}$. The asymptotically optimal threshold is $r^{*} = \lfloor n/e \rfloor$, giving a limiting success probability of $1/e \approx 0.3679$.