• 10 heures
  • Moyenne

Ce cours est visible gratuitement en ligne.

Ce cours est en vidéo.

Vous pouvez obtenir un certificat de réussite à l'issue de ce cours.

J'ai tout compris !

Mis à jour le 21/12/2018

Découvrez le problème de Monty Hall

Connectez-vous ou inscrivez-vous gratuitement pour bénéficier de toutes les fonctionnalités de ce cours !

Dans ce chapitre, nous allons nous rappeler les notions de base de la programmation en Python. Et plutôt que de faire une liste de tout ce que nous avons besoin de maîtriser, nous allons simuler un problème de probabilités.

Le problème de Monty Hall est connu pour sa solution contre-intuitive, même une fois qu’elle est expliquée. La première fois que j’ai entendu parler de ce problème, mon incrédulité m’a amené à simuler les conditions du jeu dans un programme pour me convaincre du bien-fondé de la solution. Aujourd’hui, c’est à votre tour.

Le problème de Monty Hall

L'exposé du problème est plutôt simple. Imaginez un jeu télévisé où il y a trois portes sur le plateau de jeu. Seule une de ces portes cache un trésor. Il n'y a rien derrière les deux autres portes. Rien ne permet de savoir quelle porte cache le trésor.

La tâche du joueur consiste à choisir parmi les trois portes celle qu'il veut ouvrir. Il aura droit au trésor s'il choisit la bonne porte, et rien sinon. Pour faire son choix, il n'a aucune information. Il doit donc simplement s'en remettre au hasard.

Jusqu'ici, le problème n'a rien de remarquable. Mais il y a un twist ! Une fois que le joueur a fait son choix, mais avant d'ouvrir la porte, le présentateur élimine, parmi les deux portes non choisies, une porte qui ne contient pas de trésor. Si les deux portes restantes ne contiennent rien, le présentateur élimine simplement une d'entre elles au hasard.

Le joueur doit alors faire un nouveau choix. Il peut soit choisir d'ouvrir la première porte qu'il avait choisie, soit changer pour la porte non éliminée par le présentateur. La question est, qu'a-t-il intérêt à faire ? Réfléchissez-y. Vous n'avez en principe pas besoin de connaissances poussées en probabilités pour résoudre ce problème. Que feriez-vous ?

Simulation

Génération d'une seule partie de jeu

Allons-y. Nous allons commencer par écrire une fonction qui génère une partie du jeu. Cette fonction choisit aléatoirement une porte parmi les trois pour y cacher le trésor. Elle choisit ensuite aléatoirement le premier choix du participant, et élimine une des deux portes restantes. Ensuite, une nouvelle porte est choisie selon la stratégie adoptée par le joueur :

  • Changer de porte

  • Ne pas changer de porte

Enfin, le gain du participant est calculé.

Tout d’abord, préparons notre environnement de travail dans un notebook :

# Pour afficher les graphiques dans la continuité du code, 
# et non pas dans une fenêtre à part:
%matplotlib inline

# Pour utiliser la fonction randint, qui génère des nombres
# entiers de façon aléatoire:
from random import randint, seed

# Un Enum est une structure de données qui consiste en un 
# ensemble d'éléments nommés. Une variable de ce type peut
# avoir comme valeur un de ces éléments.
from enum import Enum

# Pour pouvoir afficher des graphiques:
import matplotlib.pyplot as plt

Les stratégies du joueur

Maintenant nous allons définir les stratégies possibles pour le joueur. Il peut soit choisir de changer, soit de garder son choix initial. Pour cela, nous tirons profit de la classe  Enum  . Cette approche nous permet d'avoir des noms compréhensibles pour nos stratégies. Une autre approche consisterait à désigner chaque stratégie par un entier, par exemple 0 pour changer de porte, et 1 pour garder le choix initial. Mais cette approche a des défauts :

  • elle ne permet pas de contraindre le choix au moment où quelqu'un d'autre utilisera notre fonction. Un utilisateur final pourra appeler notre fonction de simulation en utilisant comme stratégie un entier non pris en charge, comme 2, et ne saura pas que cela posera problème à moins que nous implémentions des vérifications.

  • le code est moins lisible. Il faut se rappeler ce que chaque nombre signifie pour comprendre le programme.

# Ici nous définissons une sous-classe de Enum, qui contiendra 
# les stratégies possibles.
class Strategie(Enum):
    CHANGER = 1
    GARDER = 2

Enfin, nous pouvons définir notre fonction. Nous allons écrire une fonction très simple. Elle ne simule qu'une seule partie du jeu pour une stratégie donnée. Rappelez-vous comment on définit une fonction en Python.

# Utilise l'horloge système pour initialiser le générateur de 
# nombres pseudo-aléatoires.
seed()

def play_game(strategie):
    '''Simule une partie du jeu Monty Hall.
    
    Cette fonction simule le choix de la porte par le participant, 
    l'élimination d'une mauvaise porte par le présentateur, et le 
    choix final. Elle ne retourne que le résultat de la partie, parce 
    que nous n'aurons besoin que du résultat pour effectuer nos calculs.
    
    Args:
        strategie (Strategie): La stratégie du joueur
        
    Returns:
        bool: Le joueur a-t-il gagné?
    '''

    portes = [0, 1, 2]
    
    bonne_porte = randint(0,2)
    
    # Choix du joueur
    premier_choix = randint(0,2)
    
    # Il nous reste deux portes
    portes.remove(premier_choix)
    
    # Le présentateur élimine une porte
    if premier_choix == bonne_porte:
        portes.remove(portes[randint(0,1)])
    else:
        portes = [bonne_porte]
    
    deuxieme_choix = 0
    # Le deuxieme choix depend de la strategie
    if strategie == Strategie.CHANGER:
        deuxieme_choix = portes[0]
    elif strategie == Strategie.GARDER:
        deuxieme_choix = premier_choix
    else:
        raise ValueError("Stratégie non reconnue!")
    
    return deuxieme_choix == bonne_porte

Simulation de plusieurs parties

Maintenant nous allons essayer notre fonction. N'hésitez pas à lancer la ligne suivante plusieurs fois pour vous convaincre que le résultat est aléatoire.

play_game(Strategie.CHANGER)

Bien ! Nous pouvons simuler une partie du jeu. Mais pour pouvoir nous convaincre de la réponse à l'énigme, nous avons besoin de jouer beaucoup de fois, noter les résultats, et ensuite en tirer des conclusions. Heureusement, nous avons un ordinateur sous la main.

Nous allons définir une fonction qui lancera le jeu autant de fois que nous le souhaitons, et retournera le résultat de chaque partie dans une  list. Pour pouvoir exécuter des calculs sur ces résultats, nous allons aussi les stocker non plus comme des variables booléennes (Vrai ou Faux) mais en terme du gain du joueur (1 s'il a gagné, 0 s'il a perdu).

def play(strategie, nb_tours):
    '''Simule une suite de tours du jeu.
    
    Cette fonction renvoie les résultats de plusieurs parties
    du jeu Monty Hall sous forme d'une liste de gains par le 
    joueur.
    
    Args:
        strategie (Strategie): La strategie du joueur
        nb_tours (int): Nombre de tours
        
    Returns:
        list: Liste des gains du joueurs à chaque partie
    '''
    
    # Ceci est une liste en compréhension. Pour en savoir plus, consulter 
    # le cours "Apprenez à programmer en Python" sur OpenClassrooms
    return [1 if play_game(strategie) else 0 for i in range(nb_tours)]

Analyse des résultats

La première chose à faire est de savoir, pour un nombre de parties donné (disons, 10000), quelle stratégie rapporte le plus au joueur. Nous avons une liste contenant autant de 1 que de nombre de parties gagnées par le joueur. Il nous suffit de calculer la somme de tous les éléments de cette liste, avec la fonction  sum, pour connaître le nombre de 1.

print("En changeant de porte, le joueur a gagné {} sur 10000 parties."
      .format(sum(play(Strategie.CHANGER, 10000))))
      
print("En gardant son choix initial, le joueur a gagné {} sur 10000 parties."
      .format(sum(play(Strategie.GARDER, 10000))))
En changeant de porte, le joueur a gagné 6666 sur 10000 parties.
En gardant son choix initial, le joueur a gagné 3320 sur 10000 parties.

Le joueur qui a changé de porte a donc gagné approximativement deux fois plus souvent que le joueur qui a conservé son choix initial. Vous y attendiez-vous ? Et même après l'avoir simulé, n'avez-vous pas, comme moi, du mal à le croire ?

Visualisation

Regardons les résultats de la simulation de plus près. Nous n'allons pas pouvoir regarder les 10000 parties une par une, mais heureusement, nous pouvons créer des graphiques grâce à Matplotlib.

La fonction  plot

# plot renvoie un objet, que l'on pourra manipuler plus tard pour
# personnaliser le graphique
plot = plt.plot(play(Strategie.CHANGER, 10))
Premier graphique généré avec Matplotlib
Premier graphique généré avec Matplotlib

Voilà. C'est aussi simple que cela. La fonction  plot  place les points donnés en argument sur un graphique. Essayons de créer un graphique avec 10000 points.

plot = plt.plot(play(Strategie.CHANGER, 10000))
Le même graphique mais avec 10000 points
Le même graphique mais avec 10000 points

Avons-nous dessiné un carré ? Que se passe-t-il ? Le carré que vous voyez est dû au fait que  plot  relie les points que nous lui demandons de placer sur le graphe par des lignes. Ce sont ces lignes qui recouvrent toute la surface du graphe, et non pas les points que nous voudrions en fait voir. De manière générale, ces lignes peuvent être trompeuses, parce qu'elles peuvent aussi donner l'impression que nous avons des données entre deux points, alors que ce n'est pas le cas. Pour cette raison, nous allons placer les points sur le graphe sans les relier entre eux.

La fonction  scatter

plot = plt.scatter(range(10000), play(Strategie.CHANGER, 10000))
Scatter ne relie pas les points entre eux
Scatter ne relie pas les points entre eux

La fonction  scatter  se comporte comme  plot, mais ne relie pas les points entre eux. Ici nous voyons bien que nos points sont bien situés là où ils doivent être.

Une compétence essentielle pour tout data scientist est de savoir présenter les résultats dans le bon format. Dans notre cas, nous voulons montrer la différence entre les gains des deux stratégies. Que pensez-vous être le bon type de graphique pour communiquer ce résultat ?

La fonction  bar

plot = plt.bar([1,2],[sum(play(Strategie.CHANGER, 10000)), 
               sum(play(Strategie.GARDER, 10000))], 
        tick_label=["Changer","Garder"])
Les gains pour chaque joueur
Les gains pour chaque joueur

Si vous avez pensé à des colonnes, bravo. Vous êtes sur la bonne voie.  bar  est un peu différente des fonctions  plot  et  scatter. Elle requiert en entrée les coordonnées des colonnes, ici  [1,2]. Remarquez que vous pouvez définir vos propres titres pour chaque colonne grâce à l'argument optionnel  tick_label.

Visualisez une liste de nombres

Comment pourriez-vous suivre l'évolution des gains des joueurs en fonction du nombre de parties ? Nous pouvons vérifier que notre programme se comporte de manière raisonnable si nous détectons une relation linéaire entre les gains des joueurs et le nombre de parties qu'ils ont joué.

gains_changer = []
gains_garder = []
samples =  [1000, 10000, 20000, 50000, 80000, 100000]
for tours in samples:
    gains_changer.append(play(Strategie.CHANGER, tours))
    gains_garder.append(play(Strategie.GARDER, tours))

Nous avons maintenant deux listes. L'une contenant les gains d'un joueur qui change de porte systématiquement après 1000, 10000, 20000, 50000, 80000 et 100000 parties. L'autre contient la même chose, mais pour un joueur qui ne change jamais de porte. Nous allons maintenant afficher les deux courbes correspondant à ces listes sur le même graphique. Remarquez que nous donnons deux arguments à  scatter. Le premier est la liste des abscisses. Pourquoi pensez-vous que c'est nécessaire ?

figure = plt.figure()
plot = plt.scatter(samples, [sum(x) for x in gains_changer])
plot = plt.scatter(samples, [sum(x) for x in gains_garder])
L'évolution des gains des joueurs
L'évolution des gains des joueurs

Notez la fonction  figure. Elle crée un graphique. Les appels suivants aux fonctions telles que  scatter  et  plot  génèrent des courbes sur ce même graphique.

Nous remarquons que les gains des joueurs semblent avoir une relation linéaire avec le nombre de parties qu'ils ont jouées. C'est bon signe. Par la suite, vous allez apprendre à parcourir le chemin inverse, c'est-à-dire partir de données telles que celles présentées ici, pour arriver à la relation qui les lie à leurs paramètres.

Pour le moment, regardons une autre donnée, la moyenne de gains de chaque stratégie par partie. Il suffit pour cela de diviser la somme des gains par le nombre de parties. Je vous laisse créer ce graphique par vous même. Vous devriez voir que le moyennes se situent autour de 1/3 pour le joueur qui ne change pas de porte, et 2/3 pour celui qui change.

Explication théorique

L'explication de ce résultat est finalement assez simple. Quand le joueur choisit une porte au début du jeu, il a une chance sur trois de tomber sur la porte qui cache le trésor. La probabilité que le trésor se cache derrière une des deux portes restantes est donc de 2/3.

L'élimination par le présentateur d'une des deux portes restantes ne change pas ces probabilités. Il élimine forcément une porte qui ne cache pas de trésor. La probabilité que la porte qu'il n'élimine pas contienne le trésor devient égale à 2/3.

Ce résultat est assez contre-intuitif. Mais nous venons de le montrer de façon empirique. Si vous voulez en savoir plus, n'hésitez pas à consulter l'article Wikipédia qui y est dédié.

Petit exercice

Nous pouvons imaginer une autre stratégie, où le joueur choisit aléatoirement une porte entre la première et celle que le présentateur n'a pas éliminée. Implémentez cette stratégie et observez les résultats. Vous devriez trouver que le gain attendu se situe à mi-chemin des gains attendus avec les deux stratégies initiales.

Exemple de certificat de réussite
Exemple de certificat de réussite