Trouver le meilleur emplacement pour camper (le problème du secrétaire)

Solution en vidéo : https://youtu.be/m3NhcguvMK4

1. Modélisation.
   Commençons par ordonner par préférences de l’alpiniste les différents emplacements. Cela nous donne un vecteur $(\sigma(1),\sigma(2),\sigma(3))$ avec $\sigma\in\mathfrak{S}_3$ avec $1$ qui désigne le pire emplacement et $3$ le meilleur. Ceci nous permet de modéliser la répartition des emplacements selon la préférence comme suivant une loi uniforme sur $\mathfrak{S}_3.$ Si l’alpiniste choisit arbitrairement de s’arrêter à un des trois emplacements alors sa probabilité d’avoir le meilleur sera $\dfrac{1}{3}$.
   Stratégie optimale.
   Si elle ne s’arrête pas au premier alors elle arrive au second et peut alors adopter la stratégie suivante : si le second emplacement était meilleur que le premier alors elle s’arrête au second sinon elle s’arrête au dernier. Avec cette stratégie regardons quelles permutations aboutissent en effet au choix du meilleur emplacement

• $(1,\boxed{2},3)$ perdu.
• $(1,\boxed{3},2)$ gagné.
• $(2,1,\boxed{3})$ gagné.
• $(2,\boxed{3},1)$ gagné.
• $(3,1,\boxed{2})$ perdu.
• $(3,2,\boxed{1})$ perdu.
  L’alpiniste a alors une probabilité de $\dfrac{3}{6}=\dfrac{1}{2}$ de s’arrêter au meilleur emplacement.
  Preuve d’optimalité.
  On a vu que le fait de s’arrêter au premier emplacement systématiquement est une stratégie moins bonne, de même que de s’arrêter au dernier. Elle est donc forcée d’abandonner le premier emplacement quoi qu’il arrive et d’arriver au second. Maintenant, lorsqu’on est au second emplacement et qu’on analyse les situations où elle a perdu on remarque que deux situations sur les trois étaient inévitables car le meilleur emplacement était en premier. L’autre situation est $(1,2,3)$ que l’alpiniste ne peut différencier de $(2,3,1)$ ni de $(1,3,2)$. Dans cette situation, le choix de s’arrêter est alors le meilleur car gagnant dans deux cas sur trois.

2. On continue de modéliser la situation par une permutation aléatoire $X$ suivant une loi uniforme sur $\mathfrak{S}_n.$ On commence par justifier que $\forall k,i\in\llbracket 1,n\rrbracket,\mathbb{P}(X(k)=i)=\dfrac{1}{n}$. En effet, pour $j\neq i,$ puisque $X$ est uniforme sur $\mathfrak{S}_n$ et que $\sigma\mapsto (i ~j)\circ\sigma$ est une bijection de $\mathfrak{S}_n,$ on a
   $$\mathbb{P}(X(k)=j)=\mathbb{P}((i~j)X(k)=(i~j)(i))=\mathbb{P}(X(k)=j).$$Ainsi, pour tout $k$ la variable aléatoire $X(k)$ est uniforme sur $\llbracket 1,n\rrbracket.$ De même $X^{-1}(k)$ est aussi uniforme sur $\llbracket 1,n\rrbracket.$
   Notons $M$ la position du meilleur emplacement et $E$ l’emplacement que l’alpiniste choisira en appliquant la stratégie proposée dans l’énoncé. D’après ce qui précède $M$ suit une loi uniforme sur $\llbracket 1,n\rrbracket.$ Déterminons la probabilité d’obtenir le meilleur emplacement conditionnellement à $M=m$ pour $m\in\llbracket 1,n\rrbracket$ fixé. On doit pour cela vérifier les deux conditions ci-dessous

• $M\geq k+1$ sinon le meilleur emplacement est dans les $k$ premiers que l’on passe systématiquement donc, en suivant la stratégie, l’alpiniste campera obligatoirement au dernier qui ne sera pas le meilleur.
• Le meilleur emplacement parmi les $m-1$ premiers se trouve parmi les $k$ premier. Autrement on s’arrête au meilleur après les $k$ premier et ce ne sera pas le $m-$ème.
  Ainsi on obtient
  $$\text{Si }m\leq k,\mathbb{P}(E=m\mid M=m)=0\text{ sinon }\mathbb{P}(E=m\mid M=m)=\dfrac{k}{m-1}.$$

Via la formule des probabilités totales appliquée au système complet d’évènements $(X=m)_{1\leq m\leq n}$, tous de probabilité non nulle, on a donc
$$p_{n,k}=\mathbb{P}(E=m)=\sum_{m=1}^{n}\mathbb{P}(E=m\mid M=m)\mathbb{P}(M=m)=\dfrac{1}{n}\sum_{m=k+1}^n\dfrac{k}{m-1}=\dfrac{k}{n}\sum_{m=k}^{n-1}\dfrac{1}{m}=\dfrac{k}{n}\left(H_{n-1}-H_{k-1}\right)$$ où $\displaystyle H_n=\sum_{m=1}^n\dfrac{1}{n}$ la suite des sommes partielles de la série harmonique avec la convention $H_0=0.$

3. Soit $n\geq 3$ et $0\leq k\leq n-2.$ On a

        $$p_{n,k+1}-p_{n,k}=\dfrac{k+1}{n}\left(H_{n-1}-H_{k}\right)-\dfrac{k}{n}\left(H_{n-1}-H_{k-1}\right)$$
   

   donc
   $$p_{n,k+1}-p_{n,k}=\dfrac{k}{n}\left(H_{n-1}-H_k-H_{n-1}+H_{k-1}\right)+\dfrac{1}{n}\left(H_{n-1}-H_{k}\right)$$

$$p_{n,k+1}-p_{n,k}=-\dfrac{1}{n}+\dfrac{1}{n}\left(H_{n-1}-H_{k}\right) =\dfrac{1}{n}\left(H_{n-1}-H_k-1\right)$$Remarquons que $(p_{n,k+1}-p_{n,k})_k$ est décroissante de $\dfrac{H_{n-1}-1}{n}>0$ à $\dfrac{\frac{1}{n-1}-1}{n}<0$. Ainsi, l’entier $k_n=\min\left\{k\in\llbracket 0,n-2\rrbracket\mid p_{n,k+1}-p_{n,k}\leq 0\right\}$ existe. La suite $(p_{n,k})_{0\leq k\leq n-1}$ est donc croissante jusqu’à $p_{n,k_n}$ puis décroissante ce qui signifie que $p_{n,k_n}$ est le maximum. Puisque $p_{n,k_n+1}-p_{n,k_n}\leq 0$ et que $p_{n,k_n}-p_{n,k_n-1}\geq 0$ on a l’encadrement
$$H_{k_n-1}+1\leq H_n\leq H_{k_n}+1.$$La seconde inégalité prouve que $(H_{k_n})$ donc $(k_n)$ tend vers $+\infty.$ On peut donc appliquer le développement asymptotique $H_N=\ln(N)+\gamma+o(1)$ ce qui donne
$$\ln(k_n-1)+\gamma+1+o(1)\leq \ln(n)+\gamma+o(1)\leq \ln(k_n)+\gamma+1+O(1)$$puis, en composant par l’exponentielle,
$$(k_n-1) e^{1+o(1)} \leq n e^{o(1)}\leq k_n e^{1+o(1)}$$ce qui prouve que $\dfrac{n}{ek_n}\longrightarrow 1$, i.e. $k_n\sim \dfrac{n}{e}.$ En bonus, en écrivant $k_n=\dfrac{n}{e}+o{\dfrac{n}{e}}$ dans l’expression de $p_{n,k}$ on a $p_{n,k_n}\longrightarrow \dfrac{1}{e}\simeq 0,37$. Ainsi notre alpiniste à asymptotiquement environ $37\%$ de chance d’avoir le meilleur emplacement en adoptant cette stratégie.