Journal d'un Terrien
Web log de Serge Boisse
On line depuis 1992 !
Si cette page vous a plu, Copiez son adresse et partagez-la !
http://sboisse.free.fr/science/maths/faire-le-bon-choix.php
Faire le bon choix dans un environnement inconnu : stratégies probabilistes
Très souvent, sous sommes confrontés à des choix qui peuvent nous faire gagner, ou perdre, quelque chose, que ce soit de l'argent, de l'amour, ou même notre amour-propre. Existe-il des stratégies mathématiques qui permettent de maximiser la probabilité de faire le bon choix ? La théorie des jeux, qui étudie ces questions, est bien connue et ce n'est pas d'elle que je vais vous parler. Je vais vous exposer une incroyable stratégie, qui fonctionne, même si intellectuellement on se dit que cela tiens du miracle !
Changer de main ou pas ?
Vous participez à un jeu télévisé. L'animateur tient dans chacune de ses mains deux chèques, que vous ne pouvez pas voir, et vous dit que sur chaque chèque est inscrite une certaine somme, que vous pouvez gagner, si vous choisissez la main correspondante. Au moment où vous allez choisir, il vous interrompt et, "pour vous aider", il vous dévoile le montant du chèque qui est dans sa main gauche : mille euros ! Devez-vous prendre ce chèque, ou choisir la main droite, et le chèque dont vous ignorez le montant ?
Aussi incroyable que cela puisse paraître, il existe une stratégie qui fait bien mieux que le hasard, puisque elle vous permet de choisir le plus gros chèque avec une probabilité bien supérieure à 1/2 !
Le programme ci-dessous implémente cette stratégie. Essayez !
Mon conseil
Garder les 1000 € Choisir l'autre mainComment fonctionne cette stratégie, et pourquoi ?
ALGORITHME 1 :
Choisir au hasard un nombre décimal x entre entre 0 et 1, puis calculer le nombre u = x/(1-x)
Choisir un second nombre x' au hasard entre 0 et 1, puis calculer v = x'/(1-x')
calculer enfin le nombre y = (1000 u)/v ``
y représente un seuil, une somme que je pense pouvoir gagner en changeant de main.
Si y est inférieur à 1000, je garde donc les 1000 euros, sinon je choisis l'autre main.
(En fait on peut utiliser d'autres formules, l'essentiel est que si je me donne à l'avance un intervalle [a,b] de nombres réels positifs, la probabilité que y soit dans cet intervalle ne soit jamais nulle.)
Pourquoi est-ce que ça marche (pas toujours, mais plus souvent qu'une fois sur 2) ?
Appelons a le montant du plus petit chèque et b le montant du plus grand. Nous savons que l'on a soit a=1000, soit b=1000, mais nous ignorons dans quelle main se trouve le plus gros chèque. On a donc : p(a=1000) = p(b=1000) = 1/2.
(La notation p(n=m) signifie "probabilité que n=m")
Essayons de calculer la probabilité de faire le bon choix en suivant la stratégie. Nous générons donc un nombre y avec notre algorithme. A priori, y peut être inférieur à a, ou être compris entre a et b, ou bien être supérieur à b.
Soit p,q,r les probabilité respectives de ces trois possibilités.
Elles sont exclusives, donc p+q+r = 1 et de plus q > 0 par définition de l'algorithme.
Comme on ne sait pas lequel des deux nombres a ou b est le plus petit, il y a six cas possibles :
| y < a (probabilité : p) |
a<y<b (probabilité : q) |
y > b (probabilité : r) |
|
| a=1000 donc b > 1000 (probabilité : 1/2) |
vous choisissez de garder les 1000€ vous perdez probabilité : p/2 |
vous choisssez de changer vous gagnez probabilité : q/2 |
vous choisssez de changer vous gagnez probabilité : r/2 |
| b=1000 donc a < 1000 (probabilité : 1/2) |
vous choisissez de garder les 1000€ vous gagnez probabilité : p/2 |
vous choisissez de garder les 1000€ vous gagnez probabilité : q/2 |
vous choisssez de changer vous perdez probabilité : r/2 |
Au final, la probabilité de gagner est égal à la somme des probabilités des quatre cas gagnants, soit p/2+q/2+q/2+r/2 = (1+q)/2. Et comme q > 0, elle est supérieure à 1/2.
Le bouton ci-dessous vous permet de faire tourner un million de fois l'algorithme. Le résultat, sidérant, est que dans à peu prés 2/3 des cas, l'algorithme vous indique le bon choix ! Essayez !
Appuyez sur le bouton pour itérer un million de fois
Oui, mais...
Le problème exposé ci-dessus est une variante d'un problème presque identique, exposé par Jean-Paul Delahaye dans le numéro de Février 2017 de Pour la Science.
L'animateur choisit deux nombres positifs au hasard, écrit chacun sur un chèque, et cache les deux chèques dans ses deux mains. il vous demande de choisir quelle main (et quel chèque) vous allez gagner. Vous choisissez au hasard, disons la main gauche, vous en lisez le montant "M", mais l'animateur vous propose alors de : soit garder votre chèque, soit de prendre celui qui est dans son autre main (et dont le montant est inconnu). Que devez-vous faire ?
C'est presque le même problème... La seule différence est que le montant du chèque que vous connaissez est maintenant "M" et non plus 1000 euros. Qu'est-ce que cela change ?
En fait, c'est plus simple. L'algorithme devient :
ALGORITHME 2 :
Choisir au hasard un nombre décimal x entre entre 0 et 1,
puis calculer le nombre y = x/(1-x)
Si y est inférieur à M, je garde donc les M euros,
sinon je choisis l'autre main.
Cet algorithme semble plus simple, mais finalement c'est le même : dans le premier problème, comme la main gauche de l'animateur contenait 1000 euros et non "M", nous avons simplement "normalisé" en multipliant toutes les quantités par 1000/M... En supposant que M a été choisi par l'animateur selon la même procédure : choisir un nombre aléatoire x' entre 0 et 1, et calculer M = x'/(1-x')
Et effectivement, les probabilités de gain (choisir la bonne main) sont alors identiques dans les deux problèmes.
Plus précisément, dans le problème de Delahaye, tel que je l'ai programmé, l'animateur choisit deux nombres a et b selon la procédure "choisir un nombre aléatoire x entre 0 et 1, puis déterminer x/(1-x)". Ce seront les montant des deux chèques, qui ont donc un montant compris entre 0 et l'infini. Puis l'animateur montre au joueur le nombre a, et on choisit un troisième nombre y selon la même procédure ; et si y est supérieur à a on doit choisir l'autre main. La probabilité de faire le bon choix est supérieure à 1/2, et même égale à 2/3, comme nous l'avons montré avec notre simulation.
Dans le problème initial (celui des 1000 euros), tout se passe de la même façon, sauf que le nombre a a été remplacé par un montant fixé (1000 euros). On multiplie donc tous les nombres b, y et finalement a par 1000/a (a est donc remplacé par 1000), mais l'ordre entre ces trois nombres reste le même et donc aussi le résultat.
Mais que se passe-t-il si l'animateur choisit différemment le montant des deux chèques ?
Oui, que se passe-t-il ?
Supposons par exemple que l'animateur décide de déterminer le montant des deux chèques ainsi : choisir un montant au hasard, mais compris entre 0 et 2000 euros, selon un distribution uniforme. l'animateur peut par exemple choisir un nombre décimal au hasard entre 0 et 1, puis le multiplier par 2000. Que se passe-t-il alors ?
Comme précédemment, il vous montre le montant du chèque qui se trouve dans sa main gauche. Mais il se trouve que vous avez une petite idée de la manière dont il a choisi les montants, parce que vous vous doutez bien qu'il y a un plafond à la somme qu'il veut bien vous allouer, même si vous ne le connaissez pas précisément. Que devez-vous faire ?
La résultat intéressant de mes simulations, c'est qu'il faut modifier légèrement notre algorithme, ainsi :
ALGORITHME 3 :
Choisir au hasard un nombre décimal x entre entre 0 et 1,
puis calculer le nombre y = 550 x/(1-x)
Si y est inférieur à M, je garde donc les M euros,
sinon je choisis l'autre main.
D'où vient ce mystérieux facteur 550 ? Je n'en sais rien ! Mais c'est celui qui marche le mieux. En cliquant sur le bouton ci-dessous, vous réaliserez un million de tirages au sort de a et b (uniformément choisis entre 0 et 2000), et un million de lancement de l'algorithme 3, avec ou sans le facteur 550 :
Appuyez sur un bouton pour itérer un million de fois
Le résultat, sans appel, est que sans le facteur 550 votre probabilité de gain est certes plus grande que 1/2, mais à peine (50,3%) alors qu'avec le mystérieux facteur 550 elle bondit à 60,3 % !
Peux-on-faire encore mieux ? Oui, en tirant y au hasard de la même façon que a et b ! C'est ce que fait le bouton suivant : il tire a,b et y uniformément (entre 0 et 2000), puis si y < a il vous suggère de garder a, sinon il vous suggère de changer de main (et gagner b)
Cliquez le bouton...
Cette fois la probabilité de gain est clairement de 2/3 !
Peux-on faire encore mieux ? Oui ! Il suffit de choisir y=1000 €. Autrement dit, l'algorithme devient :
ALGORITHME 4 :
Si la somme que vous montre l'animateur dans la main gauche est supérieure à 1000 euros,
garder cette somme,
sinon choisir l'autre main.
Cliquez le bouton pour lancer un million de foix l'expérience...
Cliquez le bouton pour lancer un million de foix l'expérience...
Et cette fois la probabilité de faire le bon choix est de 75% (et le gain moyen est de 1250 euros) Et c'est logique puisqu'il y a quatre cas possibles équiprobables et que trois de ces cas sont gagnants :
| Main gauche > 1000 (probabilité : 1/2) | Main gauche < 1000 (pobabilité : 1/2) | ||
| Main droite < 1000 (probabilité : 1/2) | Main droite > 1000 (probabilité : 1/2) | Main droite < 1000 (probabilité : 1/2) | Main droite > 1000 (probabilité : 1/2) |
| on garde la somme gain : MG | on garde la somme gain : MG | on change et on perd ! on ne gagne que MD | on change et on gagne car MD > MG |
Nous pouvons généraliser cet algorithme, et cela nous servira par la suite :
Encore plus fort : deux chèques de montants choisis différemment
Généralisons un peu : Supposons que nous sachions que l'animateur a choisi le montant du premier chèque en tirant uniformément au hasard un nombre dans l'intervalle [0, a], et le montant du second chèque en tirant uniformément au hasard un nombre dans l'intervalle [0, b], et que nous connaissions à l'avance ces intervalles. (Mais hélas nous ignorons dans quelle main se trouve quel chèque).
Notons que si a=b, on est ramené au cas précédent. On procéde comme pour l'algorithme 4, en comparant la somme qu'on a découverte avec a/2, et on gagne dans 75% des cas
Mais dans le cas général, comment faire ? Supposons a < b.
Soit M le montant du chèque que vous montre l'animateur. M est dans l'intervalle [0,b]
Si M est supérieur à a, ne changez surtout pas et gardez M
Sinon, M a été tiré selon l'une des deux lois de probabilités. Donc on a une probabilité a/(a+b) s'avoir été tiré dans l'intervalle [0,a] et b/(a+b) d'avoir été tiré dans l'intervalle [0,b]. La somme de ces deux probabilités est bien 1. Dans le premier cas, on va changer si M < b/2, dans le second cas on va changer si M < a/2
Le programme ci-dessous tire un nombre a au hasard entre 0 et 1000, et un nombre b au hasard entre 0 et 1500. il place les deux nombres chacun dans une "main", Puis il tire à pile ou face et échange les deux nombres si le tirage tombe sur pile. Enfin, il applique la stratégie suivante : si le contenu de la main gauche est inférieur à 625, changer de main. Il répète cette procédure un million de fois.
Cliquez le bouton pour lancer un million de foix l'expérience...
Cliquez le bouton pour lancer un million de foix l'expérience...
Pourquoi ce mystérieux nombre 625 ? Je ne sais pas l'expliquer ! C'est celui qui marche le mieux. En fait, on a un taux de réussite de 76% avec cet algorithme ! Notons que 625 = (1000+1500)/4
Recommençons avec deux nombres, cette fois compris entre 0 et 1000 et 0 et 1900, et changeons de main si le montant vu est inférieur à (1000+1900)/4 = 725
Je me demande ce que va donner cette expérience...
Eh bien c'est un succès, le taux de réussite dépasse cette fois 77% !
Nous avons donc une explication: il faut comparer avec la moyenne des espérances des deux distributions. (Donc ici avec 725)
Résumons-nous :
- Lorsque on ne sait pas quelle est la somme maximale que l'animateur a inscrit sur les deux chèques, et que l'on ne sait pas non plus à l'avance quelle somme S sera sur le chèque dans la main qu'il va nous montrer, on applique l'agorithme "à la Delahaye" (algorithme 2) : déterminer un nombre aléatoire x, calculer y=x/(1-x), et si y > S, changer de main.
- Lorsque on ne sait pas du tout quelle est la somme maximale que l'animateur a inscrit sur les deux chèques, mais que l'on sait que l'animateur nous a montré une somme de 1000 euros dans l'une de ses mains, appliquer l'algorithme 1.
- Lorsque on sait que les deux chèques sont d'un montant a priori choisis uniformément au hasard mais compris entre M et X euros (par exemple entre 100 et 2000) alors si la somme inscrite sur le chèque que l'animateur nous montre est supérieure à (M+X)/2, (soit 1050 dans notre exemple) garder ce chèque, sinon changer de main.
- Lorsque on sait que les deux chèques sont d'un montant a priori choisis uniformément au hasard mais cette fois compris repectivement dans les intervalles [a,b] et [c,d], alors si la somme inscrite sur le chèque que l'animateur nous montre est supérieure à (a+b+c+d)/4, garder ce chèque, sinon changer de main.
Variante : le problème dit "des deux enveloppes"
Ce problème est très célèbre. Il ressemble beaucoup au problème précédent.
L'animateur vous présente deux enveloppes et vous annonce que l'une d'elle contient un chéque d'un montant inconnu, et l'autre un chèque d'un montant double. Naturellement il ne vous dit pas dans quelle enveloppe se trouve le plus gros montant ! Il vous demande de choisir une enveloppe. Vous choisissez au hasard, l'ouvrez et découvrez le montant M.
Puis l'animateur vous demande si vous gardez ce montant, ou si vous l'abandonnez au profit du contenu (inconnu) de la seconde enveloppe. Que devez-vous faire ?
Vous vous dites : soit l'autre enveloppe contient 2M, soit M/2. Donc si je change, mon gain moyen sera de (2M + M/2)/2 = 5M/4 et j'ai donc avantage à changer. Eh, minute, si je choisit maintenant l'autre main, je peux appliquer le même raisonnement à la première main, et je dois donc la garder ! Oui mais...
En fait ce raisonnement qui se mord la queue est faux, car vous supposez implicitement que les deux alternatives equiprobables sont (M, 2M) ou (M, M/2). Et que par consequent les espérances de gain de chaque enveloppe sont de M et 5M/4 respectivement. Mais c'est faux. En réalité, il faut considérer que l'animateur a d'abord choisi une somme X (equivalente au tiers du montant total des deux chèques), puis qu'il a signé un chèque de X et un chèque de 2X. Si bien que la véritable alernative est (X, 2X) ou (2X, X). Et donc l'espérance de chaque enveloppe est 3X/2, si bien qu'il n'y a pas de raison de préférer l'une au l'autre enveloppe.
Oui, mais ce nouveau raisonnement est lui aussi faux ! Tout dépend de la manière dont l'animateur a choisi la somme X. Supposons qu'il ait choisi au hasard dans l'ensemble (100,200,400) le contenu de la première enveloppe, puis qu'il ait placé le double dans la seconde enveloppe (dont le montant sera alors 200 ou 400 ou 800)
Supposons que nous trouvions "100" sur le premier chèque. Nous savons de façon certaine que nous devons changer de main. Supposons maintenant que nous trouvions "200". Alors cette fois il y a bien une chance sur 2 que l'autre main contienne 100 ou 400 et par conséquent il est préférable de changer de main. Mais si nous trouvons "800" sur l'enveloppe que nous ouvrons, alors nous savons qu'il ne faut PAS changer. Au final, la meilleure stratégie est "si le montant est diférent de 800, alors changer, sinon si on trouve 800, ne pas changer". Evidemment, là, nous connaissions la manière dont l'animateur avait choisi le montant X (en terme technique, nous connaissions la loi de probabilité de la variable aléatoire X), et nous nous en somme servi pour déterminer une stratégie. Mais quid si nous ne savons pas comment l'animateur a choisi le montant X ?
Le mieux, c'est de jouer !
montant dans l'enveloppe
Garder ce montant Choisir l'autre enveloppeAlors ? Vous avez gagné ? Pas facile ! Pourtant,il existe là aussi une stratégie permet de choisir avec une probabilité de gain supérieure à 1/2, en choisissant l'autre enveloppe lorsque l'enveloppe ouverte renferme une somme inférieure à x0, où x0 est un réel préalablement tiré au hasard.
Pas convaincu ? Le programme ci-dessous itère un million de fois cette stratégie, en choisissant x0 comme suit : on tire un réél x au hasard entre 0 et 1, et on calcule x0 = (150 x)/(1-x). D'où sors ce facteur 150 ? Je n'en ai aucune idée. Mais il marche ! Remarquons qu'il est assez proche du 1/4 du gain moyen...
Je me demande là aussi ce que va donner cette expérience...
Je me demande là aussi ce que va donner cette expérience...
Eh bien, il me semble que cela fait quand même bien mieux que le hasard !
Pour finir, une petite remarque : dans un jeu itéré comme celui-ci, où l'on répète le jeu un certain nombre de fois, il devient possible de "deviner" progressivement la distribution de probabilité des sommes contenue dans les enveloppes, et d'en tirer parti pour gagner encore plus. Je n'ai pas implémenté cette stratégie mais ce n'est pas très difficile. Amusez-vous bien !
Si vous voulez en savoir plus, je vous donne ici un lien vers une page (assez matheuse) qui traite de la décision dans un environnement incertain.
Sciences
**
Commentaires (1) :
Page : [1]Le 02/01/2018 à 21h55
Ajouter un commentaire (pas besoin de s'enregistrer)
En cliquant sur le bouton "Envoyer" vous acceptez les conditions suivantes : Ne pas poster de message injurieux, obscène ou contraire à la loi, ni de liens vers de tels sites. Respecter la "netiquette", ne pas usurper le pseudo d'une autre personne, respecter les posts faits par les autres. L'auteur du site se réserve le droit de supprimer un ou plusieurs posts à tout moment. Merci !Ah oui : le bbcode et le html genre <br>, <a href=...>, <b>b etc. ne fonctionnent pas dans les commentaires. C'est voulu.