Skip to content

Instantly share code, notes, and snippets.

@francescogior
Last active June 16, 2022 07:15
Show Gist options
  • Save francescogior/7db774a09bea658d7d12fc6124975d56 to your computer and use it in GitHub Desktop.
Save francescogior/7db774a09bea658d7d12fc6124975d56 to your computer and use it in GitHub Desktop.

Secretary Problem

Riddle

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?

Mathematical formulation

Given

  • $N \in \mathbb{N}$

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 ) $$

Solution

$$ \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} $$

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment