Population Estimation and Secretary Problem

Tank Problem (German Tank Problem)

Suppose we observe $n$ serial numbers from a population numbered $1, 2, \ldots, N$ (unknown $N$). Estimate $N$.

Model

Serial numbers drawn uniformly without replacement from $\{1, \ldots, N\}$.

MLE

$\hat{N}_{MLE} = \max(X_1, \ldots, X_n)$

This maximises likelihood, but is biased downward.

Unbiased Estimator

$\hat{N} = \frac{n+1}{n} \max_i X_i - 1$

Example

Observed serial numbers: $7, 3, 10, 46, 14$.

$\max = 46$, $n = 5$.

$\hat{N} = \frac{6}{5} \times 46 - 1 = 54.2$

Estimate: $N \approx 54$ or $55$.

Secretary Problem

We interview $n$ candidates sequentially. After each interview, must accept or reject. Cannot recall rejected candidates. Goal: maximise chance of hiring the best.

Optimal Strategy

Reject the first $r^* = \lfloor n/e \rfloor$ candidates, then choose the first one better than all seen so far.

For large $n$: $r^* \approx n/e \approx 0.368n$.

Probability of Success

With optimal strategy: $\approx 1/e \approx 0.368$ (surprisingly high).

Proof Idea

The optimal $r$ balances:

• Seeing enough candidates to know what “good” looks like
• Not waiting so long that the best is already rejected

Computer simulations verify the $1/e$ rule.

Example

100 candidates. Reject first 37, then hire the first better than all previous.

Dice Game Problem

Roll a fair die $n$ times. Stop at the last 6 rolled to win.

Optimal Strategy

Stop as soon as we see a 6 after some threshold $k$.

Threshold: $k =$ smallest integer satisfying $P_k(\text{win}) > 0.5$.

For $n = 10$: threshold around throw 5.

Summary

Problem	Key Idea
Tank estimation	Use max + correction
Secretary problem	Reject first $n/e$, then choose best yet
Dice game	Threshold-based stopping