Utilisateur:Kuxu/3

Le problème de Monty Hall est un casse-tête probabiliste librement inspiré du jeu télévisé américain Let's Make a Deal ^[1]. Il est simple dans son énoncé mais non intuitif dans sa résolution et c'est pourquoi on parle parfois à son sujet de paradoxe de Monty Hall. Le nom de ce problème mathématique vient du nom de celui qui a presenté ce jeu aux États-Unis pendant treize ans, l'animateur d'origine canadienne Monty Hall.

Dans ce casse-tête, le joueur se trouve devant trois portes fermées. Derrière l'un d'elles se trouve une voiture (ou tout autre prix magnifique) et derrière chacune des deux autres se trouvent une chèvre (ou tout autre prix sans importance). Le candidat est invité à ouvrir une porte et à gagner ce qui se trouve derrière, peut importe ce que ce soit. Théoriquement, si le candidat choisit une porte au hasard, il a une chance sur trois de découvrir la voiture directement. Mais, la porte une fois choisie par le candidat ne doit pas être ouverte avant que le présentateur n'ouvre lui-même une autre porte. Sachant très bien ce qu'il y a derrière chaque porte, il n'ouvrira jamais la porte cachant la voiture mais au contraire toujours une de celles cachant une chèvre. A ce stade du jeu, le présentateur offre deux alternatives au candidat : soit conserver son choix initial, soit changer pour la dernière porte qui n'a pas encore été ouverte par lui-même ou par le présentateur.

La question qui se pose alors au candidat est de savoir si il augmente ses chances de gagner la voiture en changeant son choix initial ?

La réponse est oui. Un changement systèmatique de son choix initial lui fera statistiquement grimper ses chances de gagner la voiture de 1/3 à 2/3.

Problème et solution

Le problème

Historique et évolution de l'énoncé du problème

Ci-dessous est reproduit la traduction d'un énoncé célèbre du problème, issu d'une lettre que Craig F. Whitaker avait fait paraître dans la rubrique Ask Marylin de Marilyn vos Savant du Parade Magazine en septembre 1990 :

Supposez que vous êtes sur le plateau d'un jeu télévisé, face à trois portes et que vous devez choisir d'en ouvrir une seule, en sachant que derrière l'une d'elle se trouve une voiture et derrière les deux autres des chèvres. Vous choisissez une porte, disons la numéro 1, et le présentateur, qui lui sait ce qu'il y a derrière chaque porte, ouvre une autre porte, disons la numéro 3, porte qui une fois ouverte découvre une chèvre. Il vous demande alors : "désirez-vous ouvrir la porte numéro 2?". A votre avis, est-ce à votre avantage de changer de choix et d'ouvrir la porte 2 plutôt que la porte 1 initiallement choisie ? ^[2]

La publication de cet article dans le Parade Magazine a eu un impact immédiat sur le lectorat et a engendré de très nombreuses discussions parmi les mathématiciens, célèbres ou non, et les amateurs anonymes. Marilyn vos Savant, reputée pour figurer au Guinness Book of Records comme étant la personne au quotient intellectuel le plus élevé au monde (QI de 228), a ainsi reçu plus de 10 000 lettres (estimation faite par elle-même) traitant du problème, dont plusieurs d'universitaires lui reprochant la pertinence de la démonstration reproduite dans sa rubrique. En 1991, pour une édition dominicale, la Une du New York Times ouvre sur ce sujet. Jerry Pournell le célèbre chroniqueur du Chaos Manor de Byte, a également discuté le problème longuement en tant qu'adversaire de la solution de Marilyn, pour se ranger finalement de son côté. Enfin, une discussion controversée a eu lieu à propos de l'article du Parade Magazine dans la rubrique The Straight Dope tenue par Cecil Adams dans l'hebdomadaire The Chicago Reader.

La pertinence des résultats statistiques étaient parfois contestés, mais ce qui posait le plus souvent problème était que l'article n'insistait pas sur les "contraintes" du présentateur. Les résultats donnés impliquaient nécessairement les posulats suivants :

Que le présentateur ouvre toujours une porte derrière se cache une chèvre.
Que le présentateur donne systèmatiquement la possibilité au candidat de revenir sur son choix initial.

Or, comme ses élèments n'étaient pas mis en avant dans l'énoncé du problème, et ce même s'ils étaient implicites, d'autres résultats statistiques que ceux donnés dans l'article devenaient possibles. Rien n'indiquait que l'énoncé de départ doive nécessairement inclure ces postulats, on devrait pouvoir généraliser le problème à d'autres cas.

Finalement, en considérant que ces postulats étaient une condition sine qua non de l'énoncé du problème, il s'est averé que les résulats de l'article étaient effectivement justifiés.

Cependant il manquait au moins un élèment de taille : la question de savoir si le candidat devait ou non changer sa décision initiale pour avoir plus de chances de gagner la voiture n'avait de sens que si l'énoncé précisait bien que le présentateur savait précisément ce qui se cachait derrière chaque porte, élèment justement omis dans l'article du Parade Magazine. Si le présentateur ne le savais pas, alors la question daurait été dénuée de sens.

Ceci dit, cet énoncé ne fait que s'inscrire dans la lignée de ceux consacrés à ce type de paradoxe.

En effet, une des premières apparitions de ce problème date de 1898 dans Probabilités de Calcul de Joseph Bertrand où il est décrit comme le paradoxe de la boîte de Bertrand .

Ce problème est ensuite réapparu sous diverses versions dont l'un des plus connue est celle du "dilemme du prisonnier".

This is a restatement of the problem as given by Steve Selvin in a letter to the American Statistician (February, 1975). As stated, the problem is an extrapolation from the game show; Monty Hall did open a wrong door to build excitement, but did not allow players to change their choice. As Monty Hall wrote to Selvin:

   And if you ever get on my show, the rules hold fast for you—no trading boxes after the selection.
   —(letsmakeadeal.com)

Selvin's subsequent letter to the American Statistician (August, 1975) appears to be the first use of the term "Monty Hall problem".

An essentially identical problem appeared as the "three prisoners problem" in Martin Gardner's Mathematical Games column in 1959. Gardner's version makes the selection procedure explicit, avoiding the unstated assumptions in the Parade Magazine version.

Un énoncé actuel exempt d'ambiguïté

Il est donc préférable de se baser sur un énoncé non équivoque du problème, incluant donc expressement les contraintes du présentateur, décrit par Mueser et Granberg comme suit :

Derrière chacune des trois portes se trouve soit une chèvre, soit une voiture, mais une seule porte donne sur une voiture alors que deux portes donnent sur une chèvre.
Le joueur choisit une des portes, sans que toutefois ce qui se cache derrière (chèvre ou voiture) ne soit révélé à ce stade.
Le présentateur sait ce qu'il y a derrière chaque porte.
Le présentateur doit ouvrir l'une des deux portes restantes et doit proposer au candidat la possibilité de changer de choix quant à la porte à ouvrir définitivement.
Le présentateur ouvrira toujours une porte derrière laquelle se cache une chèvre, en effet :
- Si le joueur choisit une porte derrière laquelle se trouve une chèvre, le présentateur ouvrira l'autre porte où il sait que se trouve également une chèvre.
- Et si le joueur choisit la porte cachant la voiture, le présentateur pourra choisir n'importe laquelle des deux portes cachant une chèvre.
Le présentateur doit offrir la possibilité au candidat de rester sur son choix initial ou bien de revenir dessus et d'ouvrir la porte qui n'a été choisie ni par lui-même, ni par le candidat.

La question qui se pose alors est de savoir si :

Le joueur augmente ses chances de gagner la voiture en changeant son choix initial ?

Ou formulé autrement, cela revient à dire :

Est-ce que la probabilité de gagner en changeant de porte est plus grande que la probabilité de gagner sans changer de porte ?

Ou encore :

Quelle est la meilleure stratégie à ce stade du jeu : Faire un nouveau choix ou rester avec le choix initial ? Les chances de gain vont-elles augmenter, diminuer ou bien resteront-elles les mêmes ?

La solution

La réponse est oui; la chance de gagner la voiture double quand le joueur modifie systématiquement son choix initial.

Il existe trois scenarii possibles, chacun étant statistiquement équiprobable (1/3):

En imaginant qu'on soit dans le cas de figure suivant : porte 1=chèvre, porte 2=chèvre et porte 3=voiture;

Le candidat choisit la porte 1 avec une chèvre derrière. Le présentateur choisira la porte avec l'autre chèvre (la porte 2 dans cet exemple). Un changement permettra de gagner la voiture.
Le candidat choisit la porte 2 avec une chèvre derrière . Le présentateur choisira la porte avec l'autre chèvre (la porte 1 dans cet exemple). Un changement permettra de gagner la voiture.
Le candidat choisit la porte où il y a la voiture. Le présentateur choisira n'importe laquelle des deux autres portes (portes 1 et 2 dans cet exemple), puisqu'il est certain qu'elles cachent des chèvres. Un changement fera perdre le candidat.

In the first two scenarios, the player wins by switching. The third scenario is the only one where the player wins by staying. Since two out of three scenarios win by switching, the odds of winning by switching are 2/3.

The problem would be different if there were no initial choice, or if the game host picked a door to open at random, or if the game host were permitted to make the offer to switch more often (or only) depending on knowledge of the player's original choice. For example, if the game host always had two goats to choose from, and the player was only asked for a choice once a goat was revealed (with two doors remaining), the odds would be 1/2. In the original problem, it is because the player has a 2/3 chance of eliminating one of the goats that the game host's decision reveals the correct answer 2/3 of the time.

Another way of getting the solution is that assuming you will switch, the only way of winning would be picking a door that does not have a car, since the host will then open the other door with a goat, eliminating any chance of choosing a door with a goat. Since the total number of doors is 3 and the number of doors with goats 2, the probability of winning a car by switching is 2/3 because it's the probability of choosing a door with a goat in the first pick.

Clés pour comprendre le problème

Diagrammes

La probabilité que la voiture se trouve derrière la porte restante peut être calculé avec les diagrammes ci-dessous.

Après avoir choisit la porte numéro 3, par exemple, le candidat a une chance sur trois de tomber directement sur la voiture avec deux chances sur trois que le voiture soit parmi les deux portes restantes.

Note that since there is only one car, there is a 100% chance that there is a goat behind at least one of doors 1 or 2.

Le présentateur ouvre maintenant la porte 1. Bien sûr le présentateur n'ouvre jamais une porte donnant sur la voiture, donc sans surprise la porte 1 donne sur une chèvre ce qui a pour effet de transférer la probabilité de 2/3 de chances d'avoir une voiture non plus sur les portes 1 et 2 comme expliqué précédemment, mais uniquement sur la porte 2 (voir graphique ci-dessous).

De manière encore plus simple, on peut reformuler en disant que si après le choix initial du candidat il était envisageable que la voiture se trouve derrière les portes 1 et 2 (avec une probabilité de 2/3), ce n'est plus le cas après l'ouverture de la porte 1 par le présentateur : seule la porte 2 est encore susceptible de cacher la voiture (et par conséquent, toujours avec une probabilité de 2/3)

Le diagramme ci-dessous montre le même raisonnement d'une manière plus complète et plus formalisée :

Arbre des possibilités du problème de Monty Hall

Démonstration visuelle

Dans le cas où le présentateur sait ce qu'il y a derrière chaque porte

On se retrouve dans le cas classique du paradoxe de Monty Hall.

Il convient de lire le graphique ci-dessous comme suit :

Le cercle intérieur représente les chiffres de la porte où la voiture est réellement cachée.
Le cercle du milieu représente la porte initialement choisit par le candidat.
Le cercle extérieur représente les portes que le présentateur peut choisir, en sachant qu'il ne dévoilera jamais la voiture.
Les cases rouges indiquent que pour gagner le candidat devra changer son choix initial.
Les cases bleues indiquent que pour gagner le candidat devra conserver son choix initial.

Fichier:Monty Hall Cercle.jpg

Une première constatation saute aux yeux : les cases rouges sont bien plus nombreuses que les cases bleues. En y regardant de plus près il y a 18 cases sur le cercle extérieur, dont 12 sont rouges. On a donc bien la preuve qu'un changement de choix initial donne au candidat 2/3 de chances de gagner la voiture (12/18=2/3).

Dans le cas où le présentateur ignore ce qu'il y a derrière chaque porte

On se retrouve dans une version alternative du paradoxe de Monty Hall. Ce sont ces résultats qui ont notamment amené à contester le conseil donné dans la rubrique de Marylin vos Savant.

La lecture du graphique est la même que précedemment, mais dans ce cas de figure il faut savoir ce qu'il se passe si le présentateur tombe par hasard sur la voiture (cas représentés par les cases noircies) :

Soit on considère que le jeu s'arrête là et que le candidat gagne la voiture. Il y a donc 1/3 de chances que ce cas de figure se présente.
Soit on considère que ce cas de figure ne se présente jamais ou bien est annulé. Il reste cette fois-ci 1/2 chance de découvrir la voiture en changeant son choix initial et 1/2 chance en ne changeant rien. Autrement dit, la question de savoir si le candidat doit changer ou non son choix initial n'a plus de raison d'être et il n'existe pas de stratégie permettant d'optimiser les chances de gagner la voiture.

Fichier:Monty Hall Cercle2.jpg

Simulation

Comme démontré précedemment, les valeurs théoriques données par les lois des probabilités sont donc :

- 1/3 de chances de gagner la voiture sans changer son choix initial, soit environ 33,3%. - /3 de chances de gagner la voiture sans changer son choix initial, soit environ 66,6%.

Mais on peut également pratiquer une simulation à l'aide d'un programme informatique reproduisant des parties ficitves et voir si, sur un grand nombre de parties, le résultat simulé tend vers le résultat donné par les probabilités et les confirment. Pour cela deux cas sont à distinguer :

Le cas où il y a un changement du choix initial
Le cas où le choix initial est conservé

Dans chaque cas, il convient de réaliser un grand nombre de situation pour réduire la marge d'erreur et de noter le pourcentage où la candidat gagne la voiture.

Un exemple de programme en JavaScript (en anglais) :

<script type="text/javascript">
var games = 25000;
var winsWithSwitch = 0;
var winsWithoutSwitch = 0;
            
document.writeln("<pre>Playing " + games + " games...");

for(var i = 0; i < games; i++) {
    // Place the prize behind a door, and then let the contestant choose.
    var prizeDoor = Math.floor(Math.random()*3);
    var choice = Math.floor(Math.random()*3);
    // Open a door that does not have the prize behind it.
    var openedDoor;
    if (choice == prizeDoor)
        openedDoor = (prizeDoor + 1 + Math.floor(Math.random()*2)) % 3;
    else
        openedDoor = (0 + 1 + 2) - choice - prizeDoor;
    // Let the contestant switch to the door that was NOT opened.
    var switchDoor = (0 + 1 + 2) - choice - openedDoor;
    if (choice == prizeDoor)
        winsWithoutSwitch++;
    if (switchDoor == prizeDoor)
        winsWithSwitch++;   
}

document.write("Win rate with a \"don't switch\" strategy: ");
document.writeln(winsWithoutSwitch / games);
document.write("Win rate with a \"switch\" strategy: ");
document.writeln(winsWithSwitch / games);
document.write("</pre>");
</script>

Voici le résultat du programme pour 25 000 simulations consécutives de parties :

Playing 25000 games...
Win rate with a "don't switch" strategy: 0.333
Win rate with a "switch" strategy: 0.667

Qui pourrait être traduit en français comme suit :

Après 25 000 parties...
Le taux de réussite (le candidat remporte la voiture) sans effectuer de changement (du choix  initial) 
est de 0.333 (soit 33,3%)    
Le taux de réussite en effectuant un changement est de 0.667 (66,7%)

Outre ce programme en JavaScript, d'autres programmes équivalents en langages C, C++, Java et Perl sont disponibles sur Wikisource : Programmes de simulation du problème de Monty Hall (en anglais)

Voici des exemples de résultats donnés par chacun de ces programmes :

En langage C (30 000 simulations de parties) :

En changeant $\simeq 66,7067\,\%$
Sans changer $\simeq 32,8733\,\%$

En langage C++ (1 000 000 de simulations) :

En changeant $\simeq 66,7494\,\%$
Sans changer $\simeq 33,2762\,\%$

En langage Java (1 000 000 de simulations) :

En changeant $\simeq 66,7032\,\%$
Sans changer $\simeq 33,2968\,\%$

En langage Perl (3 000 simulations) :

En changeant $\simeq 66,2333\,\%$
Sans changer $\simeq 33,7667\,\%$

Les simulations ci-dessus, comme d'autres sur internet (Université de Rouen (200 itérations), (pour versions Internet explrer 4 ou +, en anglais) confirment (avec une marge d'erreur) les résultats théoriques d'1/3 et de 2/3 et ce d'autant plus que le nombre d'itérations est important.

Démonstration sur un nombre élevé de portes

Il est peut-être plus facile d'appréhender le résultat décrit ci-dessus en considérant 100 portes et non plus trois comme précédemment. Lorsque le candidat choisit une porte, il a 99% de chances d'en choisir une avec une chèvre derrière. Inversement, la probabilité de tomber directement sur la porte cachant le prix de valeur est très faible (1%). Imaginons maintenant que le présentateur n'ouvre plus qu'une seule porte, mais 98 d'un seul coup, révelant bien évidemment 98 chèvres, tout en proposant toujours au candidat de changer son choix initial et de choisir la dernière porte restée close. A 99% cette porte contiendra le prix de valeur, tout comme au début le candidat avait 99% de chances de choisir une porte avec une chèvre. Le candidat aura donc tout intérêt a changer son choix initial.

La résolution par le théorème de Bayes

L'énoncé renvoie en définitive à un problème de probabilité conditionnelle et selon la formulation générale du théorème de Bayes :

Soit $A$ un évènement quelconque,
Soit ${B_{1},B_{2},...,B_{n}}$ est un ensemble d'évènements à la fois exhaustifs et mutuellement exclusifs,

Alors pour tout $i$ , on a :

P(B_{i}|A)={\frac {P(A|B_{i})P(B_{i})}{\sum _{j=1}^{n}P(A|B_{j})P(B_{j})}}\,,

Une application du théorème de Bayes au problème de Monty Hall pourrait être formulée ainsi :

Considérons le cas où la porte 3 a été choisie et aucune porte n'est encore ouverte. La probabilité que la voiture soit derrière la porte 2 p(F2) est de 1/3, probabilité qui serait en outre exactement la même pour chaque porte.

La probabilité que le présentateur ouvre la porte 1 p(O1) est alors de 1/2. En effet le candidat ayant choisit la porte 3 et le présentateur sachant ce que cache chaque porte :

Soit la voiture est derrière la porte 1 : le présentateur ouvrira la porte 2.
Soit la voiture est derrière la porte 2 : le présentateur ouvrira la porte 1.
Soit la voiture est derrière la porte 3 : le présentateur ouvrira la porte 1 ou le présentateur ouvrira la porte 2

La probabilité que le présentateur ouvre la porte 1 sachant que la voiture est derrière la porte 2 est donc p(O1|F2) = 1 La possibilté que la voiture soit derrière la porte 2 sachant que le présentateur ouvre la porte 1 est donc :

P(F2|O1)={\frac {P(O1|F2)P(F2)}{P(O1)}}={\frac {1\times {\frac {1}{3}}}{\frac {1}{2}}}={\frac {2}{3}}

Notes

1. ↑ Aux États-Unis, le jeu télévisé Let's Make a Deal était présenté par le canadien Monty Hall (de son vrai nom Monte Halparin) de 1963 à 1977, diffusé sur NBC jusqu'en 1968 puis sur ABC. En France, le jeu a été adapté sous le nom de Le Bigdil (le nom étant issu de la dernère phase du jeu américain nommée "Big Deal of the Day"). Il était présenté par Vincent Lagaf', et a été diffusé sur TF1 de février 1998 à 2004.
2. ↑ Le texte original était :

Suppose you're on a game show, and you're given the choice of three doors: Behind one door is a car; behind the others, goats. You pick a door, say No. 1, and the host, who knows what's behind the doors, opens another door, say No. 3, which has a goat. He then says to you, "Do you want to pick door No. 2?" Is it to your advantage to switch your choice?

Liens externes

[1]

[2]