A manager wants to hire $1$ secretary among $N$ candidates with the following rules:
- He interviews each candidate in a given order
- Each candidate after the interview is either irrevocably rejected or hired (thus preventing the necessity to interview the next candidates)
He decides to use the following method:
- He interviews the first $r$ candidates, ($r \in [1, N]$), rejecting all of them
- He hires the next candidate who performs better than all the first $r$ ones, or the last one ($N$ th)
What's the chance, relative to $r$, thi hire the $N$ th candidate?
What's the chance, relative to $r$, to hire the best candidate?
Which choice of $r$, relative to $N$, maximise his chances to hire the best candidate?
Given
Let
- $r \in [1, N]$
-
$\sigma$ a permutation of $I_N := [1, N]$
-
$\tau$ such that $\sigma\tau = id_{I_N}$
Let
$$
K = K_{N, r, \sigma} = { n \in I_N | n > r \land \sigma_n > \max (\sigma)_{I_r} }
$$
Let
$$
W = W(N, r, \sigma) =
\left{
\begin{array}{ll}
\min K & \text{ if } K \not= \emptyset \\
N & \text{ otherwise}
\end{array}
\right.
$$
Let
$$
\mathbb{P}( W = k ) = \mathbb{P}( W(N, r) = k ) = \frac{ #{ \sigma | W(N, r, \sigma) = k } }{N!}
$$
Find
$$
\mathbb{P}( W = N )
$$
$$
\mathbb{P}( W = \tau_N )
$$
$$
\max_r \mathbb{P}( W = \tau_N )
$$
$$
\mathbb{P}( W = N ) =
$$
$$
= \mathbb{P}(\max(\sigma){I_r} > \max(\sigma){[r+1, N-1]} ) =
$$
$$
= \mathbb{P}(\max(\sigma){I_r} > \max(\sigma){[r+1, N-1]}) =
$$
$$
= \frac{r}{N-1}
$$
$$
\mathbb{P}( W = \tau_N ) =
$$
$$
= \mathbb{P}\left(\bigcup_{n = 1}^{N}(W = n \land n = \tau_N)\right) = \sum_{n = 1}^{N}0 + \sum_{n = r + 1}^{N}\mathbb{P}(W = n \land n = \tau_N)
$$
$$
= \sum_{n = r +1}^{N}\mathbb{P}(W = n | n = \tau_N)\mathbb{P}(n = \tau_N) = \frac{1}{N} \sum_{n = r +1}^{N}\mathbb{P}(W = n | n = \tau_N) =
$$
$$
= \frac{1}{N} \sum_{n = r +1}^{N}\mathbb{P}(\max(\sigma){I_r} > \max(\sigma){[r+1, n - 1]} ) =
\frac{r}{N} \sum_{n = r +1}^{N}\frac{1}{n-1} =
$$
$$
= \frac{r}{N} \sum_{n = r}^{N - 1}\frac{1}{n} =
$$
$$
= \frac{r}{N}\left( \frac{1}{r} + \frac{1}{r + 1} + \dots + \frac{1}{N-1} \right)
$$
$$
\mathbb{P}( W = \tau_N ) = \frac{r}{N} \sum_{n = r}^{N - 1}\frac{1}{n}
$$
$$
= \frac{r}{N} \left( \sum_{n = 1}^{N - 1}\frac{1}{n} - \sum_{n = 1}^{r - 1}\frac{1}{n} \right) \sim
\frac{r}{N} \left( \ln(N-1) - \ln(r-1) \right) \sim \frac{r}{N} \ln\left(\frac{N}{r}\right)
$$
Let
$$
x = \frac{r}{N}
$$
thus
$$
\mathbb{P}( W = \tau_N ) \sim-x \ln(x)
$$
that has a $max$ in $x = \displaystyle{\frac{1}{e}}$
thus
$$
\max_r \mathbb{P}( W = \tau_N ) \sim \frac{N}{e}
$$
It's worth noting that, for such value,
$$
\mathbb{P}( W = \tau_N ) \sim \frac{1}{e}
$$
$$
\mathbb{P}( W = N ) \sim \frac{1}{e}
$$
