Secretary Problem by Backward Induction

A detailed backward-induction derivation of the classical secretary problem, the finite-horizon optimal stopping recursion, and the optimal threshold.

The Classical Secretary Problem

A complete backward-induction solution

This page derives the optimal policy from first principles using the value equation

\[ V_n=\max\{U_n,W_n\}. \]

Here, \(U_n\) is the value of stopping at a record, \(W_n\) is the value of continuing, and \(V_n\) is the optimal value.

1. Model and objective

There are \(N\ge3\) candidates arriving in a uniformly random order. Their absolute ranks are

\[ 1,2,\ldots,N, \]

where rank \(1\) is best.

After interviewing a candidate, we observe only that candidate’s rank relative to those already seen. An accepted candidate ends the process, and a rejected candidate cannot be recalled.

Let \(X_k\) be the absolute rank of the candidate in position \(k\). We seek a stopping time \(\tau\) maximizing

\[ \mathbb P(X_\tau=1). \]

Thus, the reward is \(1\) if the selected candidate is the overall best and \(0\) otherwise.

2. Relative ranks and records

Define the relative rank of the candidate in position \(n\) by

\[ R_n = 1+\sum_{j=1}^{n-1} \mathbf 1_{\{X_j<X_n\}}. \]

The event \(R_n=1\) means that the candidate at time \(n\) is better than every candidate previously observed.

Such a candidate is called a record.

A non-record cannot be the overall best. It is therefore always optimal to continue at a non-record while further candidates remain. The only decisions that can offer a positive chance of success from stopping occur when \(R_n=1\).

3. Uniformity of relative ranks

NoteRelative-rank theorem

For a uniformly random permutation, the relative ranks

\[ R_1,R_2,\ldots,R_N \]

are independent. Moreover,

\[ \mathbb P(R_n=j)=\frac1n, \qquad j=1,\ldots,n. \]

In particular,

\[ \mathbb P(R_n=1)=\frac1n. \]

Proof

The transformation from the absolute-rank permutation

\[ (X_1,\ldots,X_N) \]

to the relative-rank sequence

\[ (R_1,\ldots,R_N) \]

is a bijection.

Every admissible relative-rank sequence satisfies

\[ R_n\in\{1,\ldots,n\}. \]

The number of such sequences is

\[ 1\cdot2\cdots N=N!, \]

which equals the number of absolute-rank permutations.

Because all absolute-rank permutations are equally likely, every admissible relative-rank sequence has probability \(1/N!\). Therefore,

\[ \begin{aligned} \mathbb P(R_1=r_1,\ldots,R_N=r_N) &=\frac1{N!}\\ &=\prod_{n=1}^{N}\frac1n. \end{aligned} \]

This factorization proves that the relative ranks are independent and that each \(R_n\) is uniform on \(\{1,\ldots,n\}\). \(\square\)

4. The value of stopping

Suppose the candidate at time \(n\) is a record.

Since the overall best candidate is necessarily a record,

\[ \mathbb P(X_n=1,\ R_n=1) = \mathbb P(X_n=1) = \frac1N. \]

By the relative-rank theorem,

\[ \mathbb P(R_n=1)=\frac1n. \]

Therefore, the probability of success from stopping at a record at time \(n\) is

\[ \begin{aligned} U_n &= \mathbb P(X_n=1\mid R_n=1)\\ &= \frac{\mathbb P(X_n=1,\ R_n=1)} {\mathbb P(R_n=1)}\\ &= \frac{1/N}{1/n}\\ &= \frac nN. \end{aligned} \]

Hence,

\[ \boxed{U_n=\frac nN}. \]

The stopping value is strictly increasing in \(n\).

5. The continuation value

Let \(W_n\) be the optimal conditional probability of eventual success after rejecting the candidate at time \(n\), given the relative-rank observations available at that time. By independence of the successive relative ranks, this value depends on \(n\) but not on the previously observed relative ranks.

At a record time, define

\[ \boxed{V_n=\max\{U_n,W_n\}}. \]

At time \(n+1\), the next candidate is a record with probability

\[ \frac1{n+1}. \]

If a new record appears, another stop-or-continue decision is available and the value is \(V_{n+1}\).

With probability

\[ \frac n{n+1}, \]

the candidate is not a record. Stopping cannot then produce success, so the process continues with value \(W_{n+1}\).

Consequently,

\[ \boxed{ W_n = \frac{1}{n+1}V_{n+1} + \frac{n}{n+1}W_{n+1} }. \]

The Bellman equations are therefore

\[ \boxed{ \begin{aligned} U_n&=\frac nN,\\ V_n&=\max\{U_n,W_n\},\\ W_n&= \frac{1}{n+1}V_{n+1} + \frac{n}{n+1}W_{n+1}. \end{aligned} } \]

6. Terminal condition

At time \(N\), accepting a record wins with certainty. There is no remaining opportunity to succeed after rejection. If a selection at time \(N\) is mandatory, selecting a non-record yields reward zero and does not affect the value.

Therefore,

\[ U_N=1, \qquad V_N=1, \qquad W_N=0. \]

Starting with these terminal values, all preceding values are determined by backward induction.

7. Why the optimal policy has one threshold

From the continuation recurrence,

\[ W_n = \frac{1}{n+1}V_{n+1} + \frac{n}{n+1}W_{n+1}. \]

Subtracting \(W_{n+1}\) gives

\[ W_n-W_{n+1} = \frac{V_{n+1}-W_{n+1}}{n+1}. \]

Since

\[ V_{n+1} = \max\{U_{n+1},W_{n+1}\} \ge W_{n+1}, \]

we obtain

\[ W_n-W_{n+1}\ge0. \]

Thus,

\[ W_1\ge W_2\ge\cdots\ge W_N. \]

The continuation value \(W_n\) is nonincreasing, while the stopping value

\[ U_n=\frac nN \]

is strictly increasing.

Thus \(U_n-W_n\) is strictly increasing in \(n\). Once accepting a record is optimal, it remains optimal at every later record time. This proves that an optimal policy has a threshold form.

There is an integer \(r^*\) such that the optimal policy is:

  1. Reject the first \(r^*\) candidates.
  2. Beginning at position \(r^*+1\), accept the first record.
  3. If no later record appears, the selection fails.

At a record time \(n\), stopping is optimal whenever

\[ U_n\ge W_n. \]

If equality holds, either stopping or continuing is optimal. We break ties in favor of stopping.

8. Complete example: (N=10)

We now solve the problem for \(N=10\) without assuming the threshold in advance.

Begin with

\[ U_{10}=1, \qquad V_{10}=1, \qquad W_{10}=0. \]

Then work backward using

\[ W_n = \frac{1}{n+1}V_{n+1} + \frac{n}{n+1}W_{n+1}. \]

The resulting values are:

\(n\) \(U_n\) \(W_n\) \(V_n\) Optimal action
10 \(1\) \(0\) \(1\) Stop
9 \(9/10\) \(1/10\) \(9/10\) Stop
8 \(4/5\) \(17/90\) \(4/5\) Stop
7 \(7/10\) \(191/720\) \(7/10\) Stop
6 \(3/5\) \(55/168\) \(3/5\) Stop
5 \(1/2\) \(1879/5040\) \(1/2\) Stop
4 \(2/5\) \(2509/6300\) \(2/5\) Stop
3 \(3/10\) \(3349/8400\) \(3349/8400\) Continue
2 \(1/5\) \(3349/8400\) \(3349/8400\) Continue
1 \(1/10\) \(3349/8400\) \(3349/8400\) Continue

At time \(3\),

\[ U_3=\frac3{10} < \frac{3349}{8400} = W_3, \]

so continuing is optimal.

At time \(4\),

\[ U_4=\frac25 > \frac{2509}{6300} = W_4, \]

so stopping at a record is optimal.

The crossing occurs between times \(3\) and \(4\). Therefore, the optimal strategy rejects the first three candidates and accepts the next record:

\[ \boxed{r^*=3}. \]

The optimal success probability is

\[ \boxed{ V_1 = \frac{3349}{8400} \approx0.398690 }. \]

9. Success probability of a fixed threshold

Fix

\[ r\in\{1,\ldots,N-1\}. \]

Consider the policy that rejects the first \(r\) candidates and accepts the first subsequent record.

Suppose the overall best candidate occurs at position \(k>r\). The strategy selects that candidate precisely when the best among the first \(k-1\) candidates occurs during the initial rejection period.

The overall best is equally likely to occupy any position, so

\[ \mathbb P(X_k=1)=\frac1N. \]

Conditional on \(X_k=1\), the best candidate among the first \(k-1\) positions is equally likely to occupy any of those positions. Therefore, the probability that it occurs among the first \(r\) positions is

\[ \frac{r}{k-1}. \]

Summing over the possible positions of the overall best gives

\[ \begin{aligned} P_N(r) &= \sum_{k=r+1}^{N} \frac1N\frac{r}{k-1}\\ &= \frac rN \sum_{k=r+1}^{N}\frac1{k-1}. \end{aligned} \]

Changing the summation index yields

\[ \boxed{ P_N(r) = \frac rN \sum_{j=r}^{N-1}\frac1j }. \]

If \(r=0\), the first candidate is accepted immediately, and

\[ P_N(0)=\frac1N. \]

WarningDistinguishing (W_r) from (P_N(r))

The quantities \(W_r\) and \(P_N(r)\) have different meanings.

The value \(W_r\) is the probability of eventual success when all future decisions are made optimally after time \(r\).

In contrast, \(P_N(r)\) is the success probability of the fixed threshold-\(r\) strategy.

They are not necessarily equal.

For example, when \(N=10\),

\[ P_{10}(1) = \frac1{10}\sum_{j=1}^{9}\frac1j \approx0.2829, \]

whereas

\[ W_1 = \frac{3349}{8400} \approx0.3987. \]

At the optimal threshold,

\[ \boxed{ W_{r^*}=P_N(r^*)=V_1 }. \]

10. Exact characterization of the threshold

For \(r=1,\ldots,N-2\),

\[ P_N(r) = \frac rN \sum_{j=r}^{N-1}\frac1j \]

and

\[ P_N(r+1) = \frac{r+1}{N} \sum_{j=r+1}^{N-1}\frac1j. \]

Since

\[ P_N(r) = \frac rN \left( \frac1r+ \sum_{j=r+1}^{N-1}\frac1j \right), \]

subtraction gives

\[ \boxed{ P_N(r+1)-P_N(r) = \frac1N \left( \sum_{j=r+1}^{N-1}\frac1j-1 \right) }. \]

It follows that \(P_N(r)\) increases while

\[ \sum_{j=r+1}^{N-1}\frac1j>1 \]

and decreases after this sum becomes smaller than \(1\).

The smallest optimal threshold is

\[ \boxed{ r^* = \min \left\{ r\in\{1,\ldots,N-1\}: \sum_{j=r+1}^{N-1}\frac1j\le1 \right\}. } \]

Equivalently,

\[ \boxed{ \sum_{j=r^*+1}^{N-1}\frac1j \le1 \le \sum_{j=r^*}^{N-1}\frac1j. } \]

If the left-hand sum in the displayed characterization equals \(1\), two adjacent thresholds are optimal: \(r^*\) and \(r^*+1\). The definition above selects the smaller rejection threshold, consistent with breaking a decision tie in favor of stopping. The boundary case \(r=0\) is excluded for \(N\ge3\), because \(P_N(1)=H_{N-1}/N>1/N=P_N(0)\).

11. The asymptotic (1/e) rule

For large \(N\), the harmonic sum can be approximated by an integral:

\[ \sum_{j=r+1}^{N-1}\frac1j \approx \int_r^N\frac{dx}{x} = \log\frac Nr. \]

The threshold condition is therefore approximately

\[ \log\frac N{r^*}=1. \]

Solving for \(r^*\) gives

\[ \boxed{ \frac{r^*}{N}\longrightarrow\frac1e }. \]

Using the exact probability formula,

\[ P_N(r^*) = \frac{r^*}{N} \sum_{j=r^*}^{N-1}\frac1j. \]

The first factor approaches \(1/e\), while the harmonic sum approaches \(1\). Therefore,

\[ \boxed{ P_N(r^*)\longrightarrow\frac1e }. \]

Numerically,

\[ \frac1e\approx0.367879. \]

ImportantFinal result

For a large number of candidates:

  1. Reject approximately the first \(N/e\) candidates.
  2. Record the best candidate observed during that period.
  3. Accept the first later candidate who is better than every previously observed candidate.

Both the optimal rejection fraction and the optimal success probability approach approximately \(37\%\).

12. General backward-induction theorem

The preceding calculation is a finite-horizon instance of the Snell-envelope theorem.

To distinguish the general theory from the secretary-specific notation, let \(G_n\) denote a general reward process and let \(Z_n\) denote its value process.

NoteTheorem: finite-horizon optimal stopping

Let

\[ G_1,G_2,\ldots,G_N \]

be an integrable process adapted to a filtration

\[ \mathcal F_1,\mathcal F_2,\ldots,\mathcal F_N. \]

Define

\[ Z_N=G_N \]

and, for \(n=N-1,\ldots,1\), define

\[ \boxed{ Z_n = \max \left\{ G_n, \mathbb E[Z_{n+1}\mid\mathcal F_n] \right\}. } \]

Then

\[ Z_n = \mathop{\mathrm{ess\,sup}}_{\tau\in\mathcal T_{n,N}} \mathbb E[G_\tau\mid\mathcal F_n], \]

where \(\mathcal T_{n,N}\) is the collection of stopping times taking values in

\[ \{n,\ldots,N\}. \]

An optimal stopping time beginning at time \(n\) is

\[ \boxed{ \tau_n^* = \inf \{k\ge n:G_k=Z_k\}. } \]

Proof

At time \(N\), stopping is compulsory. Therefore,

\[ Z_N=G_N. \]

Assume that \(Z_{n+1}\) is the optimal value beginning at time \(n+1\).

At time \(n\), there are two alternatives.

If we stop, the reward is \(G_n\).

If we continue, the best attainable conditional value is

\[ \mathbb E[Z_{n+1}\mid\mathcal F_n]. \]

The optimal value is therefore

\[ Z_n = \max \left\{ G_n, \mathbb E[Z_{n+1}\mid\mathcal F_n] \right\}. \]

Backward induction proves the value formula at every time. Stopping at the first time when the immediate reward equals the value process attains this value. \(\square\)

Connection with the secretary problem

For the secretary problem, let \(\mathcal F_n=\sigma(R_1,\ldots,R_n)\) be the information available after the first \(n\) interviews. Define the \(\mathcal F_n\)-measurable reward for selecting the candidate at time \(n\) by

\[ G_n=\mathbb P(X_n=1\mid\mathcal F_n) =\frac nN\,\mathbf 1_{\{R_n=1\}}. \]

Indeed, a non-record cannot be the overall best; when \(R_n=1\), the conditional winning probability is \(n/N\). The independence of the relative ranks ensures that the previous observations do not alter this conditional probability.

Maximizing the expected conditional reward \(G_\tau\) is equivalent to maximizing \(\mathbb P(X_\tau=1)\), by the tower property. In particular, the compulsory-stopping formulation at \(N\) has the same optimal success probability as the formulation permitting no selection when no later record appears.

At a record time \(n\), the conditional reward of stopping is \(U_n=n/N\) and the value of continuing is \(W_n\). The Snell-envelope recursion therefore reduces to

\[ \boxed{V_n=\max\{U_n,W_n\}} \]

at record times. At non-record times, stopping gives zero, so continuing is optimal whenever additional candidates remain. These are exactly the decisions used in the backward induction above.

References

The general theory of backward induction and optimal stopping is developed by Chow, Robbins, and Siegmund (1971), Shiryaev (2007), and Ferguson (2010).

Historical and foundational treatments of the secretary problem include Ferguson (1989) and Gilbert and Mosteller (1966).


Leer en español

References

Chow, Yuan Shih, Herbert Robbins, and David Siegmund. 1971. Great Expectations: The Theory of Optimal Stopping. Boston: Houghton Mifflin.
Ferguson, Thomas S. 1989. “Who Solved the Secretary Problem?” Statistical Science 4 (3): 282–89. https://doi.org/10.1214/ss/1177012493.
———. 2010. “Optimal Stopping and Applications.” https://www.math.ucla.edu/~tom/Stopping/Contents.html.
Gilbert, John P., and Frederick Mosteller. 1966. “Recognizing the Maximum of a Sequence.” Journal of the American Statistical Association 61 (313): 35–73. https://doi.org/10.1080/01621459.1966.10502008.
Shiryaev, Albert N. 2007. Optimal Stopping Rules. Vol. 8. Stochastic Modelling and Applied Probability. Berlin; Heidelberg: Springer. https://doi.org/10.1007/978-3-540-74011-7.