A prendre ou à laisser! Trouver la stratégie optimale!
Vous avez participé à un jeu télévisé et vous avez gagné! Vient le moment du gain. Le présentateur arrive avec 24 enveloppes. Dans chaque enveloppe, une somme d'argent, jamais la même et dont vous n'avez aucune idée du montant. Le présentateur va ouvrir l'une après l'autre chaque enveloppe dans un ordre complètement aléatoire. Lorsqu'il ouvre une enveloppe, vous avez le choix de prendre la somme contenue, ou de passer à l'enveloppe suivante. Ce choix est irréversible! Si on garde la somme de l'enveloppe, on n'ouvre plus les enveloppes suivantes. Si on décide de passer à l'enveloppe suivante, on ne peut plus revenir en arrière et on ne pourra plus recevoir la somme contenue dans l'enveloppe rejetée.
Quelle est la meilleure stratégie pour essayer d'obtenir la plus grande somme d'argent contenue dans les enveloppes? Et avec cette stratégie, quelle est la probabilité de recevoir cette plus grande somme d'argent?
On pourrait imaginer que si le nombre d'enveloppes devient très grand, alors la probabilité de gagner la plus grosse somme d'argent devient très petite. Il n'en est rien! Il existe une stratégie optimale qui permet d'avoir plus d'une chance sur trois de remporter le plus gros gain, et ceci quelque soit le nombre d'enveloppes!
Cette stratégie est la suivante : on commence par rejeter une certaine proportion des enveloppes. Cette proportion dépend du nombre $n$ d'enveloppes, mais pour $n$ grand, elle vaut à peu près $37\%$ (plus précisément, $1/e$). Ensuite, on choisit la première enveloppe qui contient un montant supérieur au montant des enveloppes précédentes. Et dans ce cas, la probabilité de gagner le plus gros gain est d'environ...$37\%$ (plus précisément, $1/e$).
Étonnant, non? Mathématique!
Étudions plus précisément le problème avec 4 enveloppes. On suppose donc que le présentateur a mélangé les 4 enveloppes complètement aléatoirement et qu'elles sont numérotées de 1 à 4. Il va ouvrir successivement les enveloppes de la numéro 1 à la numéro 4 jusqu'à ce qu'on l'arrête. Comparons 4 stratégies!
Stratégie 1 : on choisit toujours la première enveloppe. Comme il y a une chance sur quatre que la plus grande somme d'argent soit dans cette enveloppe, il y a une probabilité égale à $1/4$ qu'avec cette stratégie, on gagne le plus gros gain possible.
Stratégie 2 : on rejette la première enveloppe puis dans les enveloppes qui suivent, on choisit la première enveloppe qui contient une somme d'argent supérieure à celle de la première. On doit alors distinguer 4 cas :
- la plus grande somme d'argent est dans la première enveloppe. Comme on la rejette, on a perdu! La probabilité d'obtenir le gain maximal dans ce cas est égale à $0.$
- la plus grande somme d'argent est dans la deuxième enveloppe. Ainsi, la somme contenue dans cette enveloppe est supérieure à la somme contenue dans la première, donc on va garder l'enveloppe et obtenir le gain maximal. La probabilité d'obtenir le gain maximal dans ce cas est donc égale à $1.$
- la plus grande somme d'argent est dans la troisième enveloppe.
Dans ce cas, on gagne la somme maximale si on ouvre cette troisième enveloppe, donc si la somme contenue dans la deuxième enveloppe est inférieure à la somme contenue dans la première. Comme les éventualités sont équiprobables, ceci arrive avec une probabilité égale à $1/2$.
- la plus grande somme d'argent est dans la quatrième enveloppe.
Dans ce cas, on gagne la somme maximale si on ouvre cette quatrième enveloppe, donc si la somme contenue dans la deuxième enveloppe et la somme contenue dans la troisième enveloppe sont inférieures à la somme contenue dans la première. Comme les éventualités sont équiprobables, ceci arrive avec une probabilité égale à $1/3$.
Pour calculer la probabilité d'obtenir le gain maximal avec cette stratégie, on va utiliser la formule des probabilités totales. On note GM l'événement "obtenir le gain maximal". On a pour le moment calculé les probabilités conditionnelles : $P(\textrm{GM}|\textrm{Cas 1}) = 0$, $P(\textrm{GM}|\textrm{Cas 2})= 1$, $P(\textrm{GM}|\textrm{Cas 3})= 1/2$, $P(\textrm{GM}|\textrm{Cas 4}) = 1/3$. Remarquons aussi que les différents choix de l'ordre des enveloppes sont équiprobables, et donc on a $$P(\textrm{Cas 1})=P(\textrm{Cas 2})=P(\textrm{Cas 3})=P(\textrm{Cas 4})=\frac 14.$$ Par la formule des probabilités totales, \begin{eqnarray*} P(\textrm{GM})&=&P(\textrm{GM}|\textrm{Cas 1}) P(\textrm{Cas 1})+P(\textrm{GM}|\textrm{Cas 2})P(\textrm{Cas 2}) +\\ &&\quad P(\textrm{GM}|\textrm{Cas 3}) P(\textrm{Cas 3})+P(\textrm{GM}|\textrm{Cas 4}) P(\textrm{Cas 4})\\ &=&0\times \frac 14+1\times\frac 14+\frac 12\times\frac 14+\frac 13\times\frac 14\\ &=&\frac 14\left(1+\frac 12+\frac 13\right)\\ &\simeq & 0,\!46. \end{eqnarray*} C'est beaucoup mieux!
Stratégie 3 : on rejette les deux premières enveloppes puis on choisit la première enveloppe qui suit et qui contient une somme d'argent supérieure à celle des précédentes. Alors :
- si la somme maximale est contenue dans une des deux premières enveloppes, alors on a perdu! On obtient donc le gain maximal avec une probabilité égale à $0.$
- si la somme maximale est contenue dans la troisième enveloppe, alors on a gagné! On obtient donc le gain maximal avec une probabilité égale à $1.$
- si la somme maximale est contenue dans la quatrième enveloppe, alors on a gagné si la troisième enveloppe contient une somme inférieure à l'une des deux premières enveloppes. Ceci arrive avec une probabilité de $2/3$.
Finalement, avec cette stratégie, on trouve\begin{eqnarray*} P(GM)&=&\frac 14\times 1+\frac 14\times \frac23\\ &=&\frac{1}4\left(1+\frac 23\right)\\ %&=&\frac{2}4\left(\frac 12+\frac 13\right) \\ &\simeq&0,\!42. \end{eqnarray*} C'est légèrement moins bien!
Stratégie 4 : on rejette les trois premières enveloppes et on choisit toujours la quatrième. Dans ce cas, la probabilité de gagner est toujours égale à $1/4$.
Finalement, c'est la stratégie 2 qui est la meilleure, et avec une différence qui est notable!
Supposons maintenant qu'on cherche une stratégie pour $n$ enveloppes. Fixons $k$ un entier dans $\{1,\dots,n\}$. On considère la stratégie suivante : on observe le contenu des $k$ premières enveloppes sans rien décider puis on choisit la première enveloppe qui contient une somme supérieure à celle des enveloppes précédentes. On note $p_{n,k}$ la probabilité d'obtenir le gain maximal pour cette stratégie.
On peut calculer $p_{n,k}$ avec le même raisonnement que précédemment. Si la meilleure enveloppe est la $j$-ème enveloppe, alors :
- si $j\leq k$, on a perdu.
- si $j>k,$ on gagne lorsque dans les enveloppes de $1$ à $j-1,$ la plus grande somme d'argent est dans les $k$ premières. Ceci signifie qu'on va également rejeter les enveloppes de $k+1$ à $j-1,$ et qu'on va ouvrir et choisir l'enveloppe $j$ qui contient la plus grande somme d'argent. On gagne donc avec une probabilité $\displaystyle \frac{k}{j-1}.$
Finalement, en appliquant la formule des probabilités totales, on trouve que \begin{eqnarray*} p_{n,k}&=&\frac1n\times0+\cdots+\frac 1n\times 0+\frac 1n\times \frac kk+\frac 1n\times \frac k{k+1}+\cdots+\frac 1n\times \frac{k}{n-1}\\ &=&\frac kn\left(\frac 1k+\frac 1{k+1}+\cdots+\frac 1{n-1}\right). \end{eqnarray*}
On s'intéresse maintenant à la valeur de $k$ optimale. Pour une valeur de $n$ fixée, on peut programmer un algorithme sous Python pour déterminer cette valeur optimale. La fonction $\verb+probabilite(n,k)+$ suivante renvoie la valeur de $p_{n,k}$ tandis que $\verb+strategie(n)+$ renvoie pour une valeur de $n$ fixée la valeur de $k$ optimale, ainsi que la probabilité $p_{n,k}$ correspondante.
Essayez dans la console $\verb+probabilite(4,1)+$ puis $\verb+strategie(4)+$ pour vérifier qu'on obtient bien les résultats démontrés auparavant. Essayez ensuite $\verb+strategie(10)+$ puis $\verb+strategie(100)+$, puis encore avec d'autres valeurs. Il devrait être apparent que quand $n$ devient grand, la valeur optimale de $k$ est telle que $k/n\simeq 0,\!368$ et est associée à une probabilité d'environ $0,\!368$.
C'est bien de constater, mais maintenant, ce serait beaucoup mieux de prouver cette règle des $37\%$. Pour cela, on a besoin d'un peu plus de maths! On repart de la formule $$p_{n,k}=\frac kn\left(\frac 1k+\frac 1{k+1}+\cdots+\frac 1{n-1}\right)$$ et on cherche pour quelle proportion $k/n$ la valeur de $p_{k,n}$ est la plus grande possible.
L'idée est de voir dans la somme précédente une somme d'aires de rectangles. Pour cela, écrivons $\frac 1k$ sous la forme $$\frac 1k=\frac{1}{n}\times \frac{n}k=\frac{1}n\times\frac{1}{\frac kn}.$$ Ainsi, $1/k$ est l'aire du rectangle suivant, construit à partir de la courbe $y=1/t$ :
On peut faire pareil avec $\frac 1{k+1}$ en l'écrivant $$\frac1{k+1}=\frac 1n\times\frac{n}{k+1}=\frac 1n\times\frac1{\frac{k+1}n}.$$ On trouve alors l'aire d'un deuxième rectangle :
En continuant ainsi, on trouve l'aire de $n-k$ rectangles construits à partir de la courbe $y=1/t,$ entre l'abscisse $k/n$ et l'abscisse 1.
Que se produit-t-il maintenant si on augmente $n$ tout en maintenant fixe la proportion $k/n$ d'enveloppes que l'on laisse passer? L'animation Geogebra suivante où on peut changer la valeur de $n$ et où $k/n$ reste fixé à $0,\!4$ permet de le simuler.
Comme on le constate, la somme des aires des rectangles approche de plus en plus l'aire sous la courbe $y=1/t$, entre les droites $t=k/n$ et $t=1.$ Mais ceci n'est rien d'autre que l'intégrale de $1/t$ entre $k/n$ et $1$. Ainsi, si on pose $x=k/n,$ alors on a $$\lim_{n\to+\infty} \left(\frac 1k+\frac 1{k+1}+\cdots+\frac 1{n-1}\right)=\int_x^1 \frac{dt}t.$$ Ceci peut se démontrer rigoureusement par le théorème dit des sommes de Riemann.
L'intégrale qu'on a obtenue se calcule et vaut $$\int_x^1 \frac{dt}t=\ln(1)-\ln(x)=-\ln(x),$$ et finalement, en n'oubliant pas de multiplier par $\frac kn,$ on trouve que, si $k/n=x$ est fixé et si $n$ tend vers $+\infty,$ alors $$p_{n,k}\to -x\ln(x).$$ La valeur optimale de la proportion, pour de grandes valeurs de $n,$ sera donnée par le maximum de la fonction $f$ définie sur $]0,1]$ par $f(x)=-x\ln(x),$ dont la courbe représentative est la suivante :
On étudie cette fonction, dérivable sur $]0,1]$, et qui vérifie pour $x\in]0,1],$ $$f'(x)=-\ln(x)-1.$$ On étudie son signe et on trouve $$f'(x)\geq 0\iff -\ln(x)-1\geq 0 \iff \ln(x)\leq -1\iff x\leq \exp(-1)=1/e.$$ $f$ est donc croissante sur $]0,1/e]$, décroissante sur $[1/e,1]$ et $$f(1/e)=-\frac 1e\ln\left(\frac 1e\right)=\frac 1e\simeq 0,\!368.$$ Ainsi, $f$ atteint son maximum en $1/e$ et ce maximum vaut $f(1/e)=1/e$.
Conclusion : Quand $n$ est grand, il faut laisser passer une proportion $\simeq 1/e\simeq 0,\!368$ d'enveloppes. On gagnera la somme maximale avec une probabilité $\simeq 1/e\simeq 0,\!368$.