Niveau exercices

Îles aux trésors

Posté par
matheux14 08-08-24 à 01:19

Bonjour,

Un pirate utilisant un détecteur se rend sur île de N trésors cachés. Il parcourt l'île et demande au Chef de l'île de lui montrer tous les trésors. Le chercheur attribue une note allant de 0 à 20 à chaque trésor selon ses propres critères. Le Chef de l'île lui impose une condition pour sa quête : parmi les n trésors proposés aléatoirement, chaque trésor sera présenté un par un. Si le chercheur refuse le i -ème trésor, il ne pourra plus y revenir.

Déterminer l'instant optimal $i_0$ où le chercheur doit faire son choix.

n est strictement inférieur à N.

Posté par re : Îles aux trésors

08-08-24 à 15:00

Bonjour, le problème peut être généralisé ainsi :

On cherche à choisir parmi $N$ objets distincts le meilleur avec la plus grande probabilité possible. Le principe est d'inspecter les objets un par un, et à chaque fois de décider si on choisit l'objet inspecté (dans ce cas le processus d'inspection s'arrête et on ne regardera pas les objets suivants) ou si on passe à l'inspection de l'objet suivant. On ne peut pas revenir en arrière. Si les $N-1$ premiers objets n'ont pas été choisis, on prend alors automatiquement le $N$ -ième objet.

L'objectif de cet exercice est de déterminer une stratégie d'arrêt nous permettant de maximiser la probabilité de choisir le meilleur objet parmi les $N$ à notre disposition.

Soit $(\Omega, \mathcal{F}, \mathbb{P})$ un espace probabilisé et $S_N$ l'ensemble des permutations de $N$ éléments. Soit $\Sigma : \Omega \longrightarrow S_N$ une variable aléatoire uniforme à valeurs dans $S_N$ . Pour $1 \leq n \leq N$ , la valeur $\Sigma_n$ représente le rang absolu du $n$ -ième objet inspecté (on suppose que les objets ont tous une valeur différente). Par exemple, si $\Sigma_n(\omega) = 1$ , le meilleur objet est dans la position $n$ . On remarque qu'on ne peut pas observer directement $\Sigma(\omega)$ (on ne connaît le classement absolu des $N$ objets qu'une fois qu'on les a tous inspectés).

À chaque étape $n$ , on observe une variable aléatoire $X_n$ qui donne le rang relatif du $n$ -ième objet inspecté par rapport aux $n-1$ objets inspectés auparavant. Donc $X_1 = 1 , X_2 \in \{1, 2\}, ... , X_n \in \{1, \dots, n\}$ et $X_N = \Sigma_N$ : une fois qu'on a inspecté tous les objets, on connaît leur classement absolu. À chaque instant $n$ , on connaît $\mathcal{F}_n = \sigma(X_1, \dots, X_n)$ , la tribu engendrée par les rangs relatifs des $n$ premiers objets. Par exemple : si $N = 4$ et $\Sigma(\omega) = (3, 4, 1, 2)$ alors $X_1(\omega) = 1$ , $X_2(\omega) = 2$ , $X_3(\omega) = 1$ , $X_4(\omega) = 2$ .

Soit $\Xi = \{(x_1, \dots, x_n) \in \mathbb{N}^* : 1 \leq x_k \leq k, k = 1, \dots, N \}$ l'ensemble des valeurs possibles pour le vecteur aléatoire $X = (X_1, \dots, X_N)$ . Remarquons que $X$ est une fonction mesurable de $\Sigma$ . Plus précisément, l'application $\Psi : S_N \rightarrow \Xi$ qui associe à une permutation la suite correspondante des rangs relatifs est bijective, donc $X = \Psi \circ \Sigma$ et $\Sigma = \Psi^{-1} \circ X$ : étant donnée la suite de rangs relatifs $X_1(\omega), X_2(\omega), \dots$ , on peut reconstruire $\Sigma(\omega)$ .

Notre objectif est de trouver un temps d'arrêt $T$ (pour la filtration $(\mathcal{F}_n)_{1 \leq n \leq N}$ borné par $N$ , qui maximise la quantité

$\mathbb{P}(\Sigma_T = 1) = \mathbb{E}[1_{\Sigma_T=1}]$ .

1) Montrer que

$\forall (x_1, \dots, x_N) \in \Xi, \quad \mathbb{P}(X_1 = x_1, X_2 = x_2, \dots, X_N = x_N) = \dfrac{1}{N!}$ .

2) Montrer que les variables $(X_n)_{1 \leq n \leq N}$ sont indépendantes et que pour tout $1 \leq j \leq n$ ,

$\mathbb{P}(X_n = j) = \dfrac{1}{n}$ .

3) On définit le processus adapté $(Y_n){1 \leq n \leq N}$ , par $Y_n = \mathbb{E}[1{\Sigma_n=1} \mid \mathcal{F}_n]$ . Montrer que pour tout temps d'arrêt $T$ borné par $N$ ,

$\mathbb{P}(\Sigma_T = 1) = \mathbb{E}[Y_T]$ .

4) Montrer que, pour tout $1 \leq n \leq N$ ,

$Y_n = \dfrac{n}{N} 1_{(X_n = 1)}$ ,

(en particulier $Y_n$ est mesurable par rapport à $\sigma(X_n)$ .

5) Montrer que la fonction valeur $(Z_n)_{1 \leq n \leq N}$ est bien définie et que, pour tout $1 \leq n \leq N, Z_n$ est mesurable par rapport à $\sigma(X_n)$ . En déduire qu'un temps d'arrêt optimal est donné par

$T^* = \inf \left\{ 1 \leq k \leq N - 1 : \mathbb{E}[Z_{k+1}] \leq \dfrac{k}{N}, X_k = 1 \right\} \quad \text{si cet infimum existe, sinon $ N $}.$

6) Montrer que $\mathbb{E}[Z_n]$ décroît quand $n$ croît. En déduire qu'il existe un entier $1 \leq r \leq N - 1$ tel que $T^* = T_r$ où

     $T_r = \inf \left\{ r \leq k \leq N - 1 : X_k = 1 \right\} \quad \text{si cet infimum existe, sinon $ N $}$ .

7) Montrer que pour $1 < r \leq N$ ,

$\mathbb{E}[Y_{T_r}] = \dfrac{r-1}{N} \sum_{k=r}^{N} \dfrac{1}{k-1} := G_N(r)$ .

8) Montrer que $G_N\left(\left\lfloor \dfrac{N}{e} \right\rfloor\right) \longrightarrow -x \log x$ quand $N \rightarrow \infty$ et que cette fonction limite admet un maximum en $x = 1/e \approx 0,37$ . On en déduit que lorsque le nombre d'objets $N$ tend vers l'infini, la stratégie optimale consiste à laisser défiler une proportion d'environ 37% d'objets sans en sélectionner, puis à choisir le premier objet meilleur que tous ceux qui l'ont précédé.

Réponses

1) La variable aléatoire $X$ st uniformément distribuée sur toutes les permutations possibles de $\{1, 2, \dots, N\}$ . Il y a $N!$ permutations possibles, donc la probabilité que $X$ prenne une certaine permutation spécifique est $\dfrac{1}{N!}$ .

2) Chaque $X_n$ représente le rang relatif du $n$ -ième objet parmi les $n$ premiers inspectés.

Comme $X_n$ est uniformément distribué sur $\{1, 2, \dots, n\}$ , la probabilité que $X_n$ soit égal à $j$ est $\dfrac{1}{n}$ .

Et puisque les objets sont inspectés de manière séquentielle et que chaque $X_n$ dépend uniquement des inspections précédentes mais pas des inspections futures, les variables $(X_n)_{1 \le n \le N}$ sont indépendantes.

3) Le processus $(Y_n)_{1 \le n \le N}$ est adapté à la filtration $(\mathcal{F}_n)_{1 \le n \le N}$ . Etant donné que $Y_n$ est l'espérance conditionnelle de l'indicateur de l'événement $\{\Sigm_n = 1\}$ par rapport à $\mathcal{F}_n, \mathbb{E}[Y_T] = \mathbb{P}(\Sigma_T = 1)$ pour tout temps d'arrêt $T$ borné par $N$ . Cela découle de la propriété de martingale du processus $(Y_n)$ , où $Y_n$ est une martingale avec $Y_N = 1_{\Sigma_{N = 1}}$ et $\mathbb{E}[Y_n] = \mathbb{P}(\Sigma_N = 1) = \mathbb{P}(\Sigma_T = 1)$ pour tout $T \le N$

4) $Y_n$ est défini comme $Y_n = \mathbb{E}[1_{\Sigma_n=1} \mid \mathcal{F}_n]$ , c'est-à-dire l'espérance conditionnelle de l'événement $\Sigma_n = 1$ sachant la tribu $\mathcal{F}_n$ . Cela signifie que $Y_n$ est la probabilité que l'objet observé en position $n$ soit le meilleur parmi les $N$ objets, sachant les informations jusqu'à $n$ .

On remarque que pour que $\Sigma_n = 1$ , l'objet inspecté à la position $n$ doit être le meilleur parmi les $n$ premiers objets. De plus, parmi les $N$ objets, l'objet en position $n$ a une probabilité $\dfrac{1}{N}$ d'être le meilleur globalement. Si $X_n = 1$ (c'est-à-dire si l'objet $n$ est le meilleur parmi les $n$ premiers), alors $Y_n = \dfrac{n}{N}$ , car parmi les $N$ objets, l'uniformité implique que la probabilité que cet objet soit également le meilleur parmi les $N$ est $\dfrac{n}{N}$ . Sinon, si $X_n \neq 1, Y_n = 0$ .

Donc,

$Y_n = \dfrac{n}{N} 1_{(X_n = 1)}$ ,

et $Y_n$ est clairement mesurable par rapport à $\sigma(X_n)$ .

5) Pour tout $n, Z_n$ dépend du maximum des valeurs futures de $Y_k$ pour $k \geq n$ , donc $Z_n$ est mesurable par rapport à $\sigma(X_n)$ car $Y_k$ pour $k \geq n$ est également mesurable par rapport à $\sigma(X_k)$ (question précédente).

Pour le temps d'arrêt optimal $T^*$ , la stratégie consiste à choisir le premier instant où la condition $\mathbb{E}[Z_{k+1}] \leq \dfrac{k}{N}$ est satisfaite et $X_k = 1$ , sinon on choisit le dernier objet, soit $N$ .

Formellement,

$T^* = \inf \left\{ 1 \leq k \leq N - 1 : \mathbb{E}[Z_{k+1}] \leq \dfrac{k}{N}, X_k = 1 \right\},$

si cet infimum existe, sinon $T^* = N$ .

6) $Z_n = \sup_{n \leq k \leq N} \dfrac{k}{N} 1_{(X_k = 1)}$ est une fonction décroissante en $n$ car, à mesure que $n$ augmente, le nombre d'indices $k$ pour lesquels $Z_n$ est défini diminue.

Par conséquent, l'espérance $\mathbb{E}[Z_n]$ est aussi décroissante.

Cela implique qu'il existe un entier $1 \leq r \leq N - 1$ tel que :

$T^* = T_r = \inf \left\{ r \leq k \leq N - 1 : X_k = 1 \right\},$

si cet infimum existe, sinon $T^* = N$ .

7) $Y_{T_r}$ est la valeur de $Y_n$ au temps d'arrêt $T_r$ . La probabilité que $X_k = 1$ pour un $k \geq r$ est $\dfrac{1}{k}$ , et $T_r$ est le premier temps après $r$ où $X_k = 1$ . Donc, la contribution de $T_r$ est proportionnelle à $\dfrac{k}{N}$ pour chaque $k$ où $X_k = 1$ .

En prenant l'espérance de $Y_{T_r}$ , on obtient :

$\mathbb{E}[Y_{T_r}] = \sum_{k=r}^{N} \dfrac{k}{N} \cdot \dfrac{1}{k} \cdot \dfrac{r-1}{k-1} = \dfrac{r-1}{N} \sum_{k=r}^{N} \dfrac{1}{k-1} := G_N(r)$ .

8) Je sèche complètement