Deeder.fr

Tribulations d'un geek...

Aller au contenu | Aller au menu | Aller à la recherche

Keyword - mathématiques

Fil des billets - Fil des commentaires

2 septembre 2014

Prouvons le paradoxe de Monty Hall

Il y a très exactement 5 ans, sur ce blog, je vous parlais du paradoxe de Monty Hall que je vous prouvais avec les mains. Comme tout paradoxe mathématique, il parait au premier abord quelque peu contrintuitif jusqu'à ce qu'on se penche vraiment sur le problème. Je vous propose de revenir sur ce problème et de le prouver de deux façons : une approche pratique à l'aide d'une simulation informatique pour vérifier ou infirmer notre intuition, et une approche mathématique un peu plus formelle à l'aide du théorème de Bayes.

Chèvre

L'énoncé

Le problème énoncé pour la première fois en 1975 est le suivant : un jeu télévisé met en scène 3 portes. Derrière deux d'entre elles se cachent une chèvre et derrière la troisième se cache une voiture, réparties au hasard. Le candidat (sauf s'il s'agit d'un véritable ami des bêtes) va donc tenter de deviner derrière quelle porte se cache la voiture pour tenter de la gagner. Le présentateur sait ce qui se trouve derrière chacune des portes et le jeu se déroule en plusieurs temps :

  • Le joueur choisit tout d'abord une porte au hasard
  • Sur les deux portes restantes, le présentateur en dévoile une derrière laquelle se trouve une des chèvres
  • Puis on demande alors au candidat s'il souhaite conserver son choix ou changer pour sélectionner l'autre porte

La question est alors la suivante : le joueur a-t-il intérêt à changer de porte ?

La première idée qui vient à l'esprit est que le choix est équiprobable et que, peu importe son choix, le joueur a 50% de chances de gagner. Mais est-ce aussi simple que ça ?

Simulation

Pour vérifier notre intuition, créons une simulation simple à l'aide d'un petit script simple en python. Ce script assez simple se déroule en 4 étapes principales :

  • On simule le placement de la voiture grace à \(repartirVoiture()\). Le choix est fait au hasard entre les 3 portes, avec une probabilité identique pour toutes les portes.
  • On simule le choix du candidat avec \(simulerChoixCandidat()\). Là, on peut faire un peu ce qu'on veut : rendre le choix aléatoire, choisir toujours la même porte ou s'en remettre aux astres si vous le voulez, ça ne changera pas le résultat.
  • On simule l'ouverture d'une porte derrière laquelle se trouve une chèvre avec \(ouvrirPorte()\). On considère que le présentateur sait ce qui se cache derrière chacune des portes, il ouvre donc la première porte derrière laquelle se trouve une chèvre. Mais on pourrait très bien choisir une des deux portes restantes aléatoirement également si on le voulait.
  • On simule le changement d'avis du candidat par \(changerChoix()\) le cas échéant

Ensuite, on compare tout simplement les résultats pour un grand nombre de candidats entre le choix initial et le changement de choix et on regarde les résultats. Voici donc les détails du code de la simulation :

import numpy as np

def repartirVoiture(n):
    '''Repartition aleatoire des voitures pour n emissions'''
    voitures = np.random.randint(0, 3, n)
    return voitures

def simulerChoixCandidat(n, mode='random'):
    '''Simulation des choix des candidats pour n emissions (soit aleatoire, soit toujours le meme)'''
    if mode is not 'random':
        choix = np.array([1]*n)
    else:
        choix = np.random.randint(0, 3, n)
    return choix

def ouvrirPorte(prix, choix):
    '''Ouverture d'une porte par le presentateur en fonction de la position de la voiture et du choix du candidat'''
    portesOuvertes = np.zeros(choix.shape)
    for i, x in enumerate(prix):
        for k in [0, 1, 2]:
            if k != x and k != choix[i]:
                portesOuvertes[i] = k
    return portesOuvertes

def changerChoix(choix, portesOuvertes):
    '''Le candidat decide de changer de choix apres l'ouverture de la porte par le presentateur'''
    secondChoix = np.zeros(choix.shape)
    for i, x in enumerate(portesOuvertes):
        for k in [0, 1, 2]:
            if k != x and k != choix[i]:
                secondChoix[i] = k
    return secondChoix

def afficherResultats(choixFinal, prix):
    '''Afficher les taux de gain en pourcentages'''
    mask = choixFinal == prix
    pc = mask.sum() / float(len(mask)) * 100
    return pc

n = 10000
choix          = simulerChoixCandidat(n)
prix           = repartirVoiture(n)
portesOuvertes = ouvrirPorte(prix, choix)
secondChoix    = changerChoix(choix, portesOuvertes)
print 'Reussite sans changement : %0.2f%%' % afficherResultats(choix, prix)
print 'Reussite avec changement : %0.2f%%' % afficherResultats(secondChoix, prix)

Quand on lance le script, il nous retourne les résultats suivants:

Reussite sans changement : 32.90%
Reussite avec changement : 67.10%

Contrairement à nos premières intuitions, il semblerait que les candidats qui choisissent de changer de porte soient plus chanceux que les autres : 67% de gagnants contre 33% pour ceux qui campent sur leurs positions ! Je vous l'accorde, c'est un peu contre-intuitif, mais ça n'est pas complètement aberrant. Essayons de comprendre pourquoi avec quelques équations...

Mise en équations

En fait, généralement, on part du principe que la voiture a autant de chance de se trouver derrière n'importe quelle porte puisqu'elle est répartie de façon aléatoire. Du coup, si l'on note \(P(V_i)\) la probabilité que la voiture se trouve derrière la porte \(i\), on a \(P(V_1) = P(V_2) = P(V_3) = \frac{1}{3}\). Jusque là, le raisonnement est vrai, du moins au début, pour le premier choix !

Cependant, on néglige un point particulièrement important : la suite des évènements nous apporte des informations supplémentaires sur le jeu. En effet, le présentateur, qui sait ce qui se trouve derrière les portes, ouvre délibérément une des deux portes restantes. Du coup, il nous apporte une information supplémentaire sur la porte qu'il n'a pas ouverte : s'il ne l'a pas ouverte, c'est qu'il y a plus de chances que la voiture se cache derrière. Par contre, il n'apporte aucune information sur la première porte choisie puisque de toute façon il ne peut pas l'ouvrir.

Du coup, admettons que nous ayons choisi la porte 1 et que le présentateur ouvre la porte 2. Alors \(P(V_1) = \frac{1}{3}\) reste inchangée par rapport au choix initial. La porte 2 est ouverte par le présentateur, du coup \(P(V_2) = 0\). Et enfin \(P(V_3) = 1 - P(V_2) - P(V_3) = \frac{2}{3}\) augmente du même coup.

Essayons de valider notre nouveau raisonnement mathématiquement à l'aide du théorème de Bayes. Pour rappel, son énoncé est le suivant :

Soit \(P(A|B)\), la probabilité de A sachant B et \(P(A)\) la probabilité de A. Alors,

\[P(A|B) = \frac{P(B|A)P(A)}{P(B)}\]

Utilisons d'appliquer ce théorème de Bayes à la résolution de notre petit problème. Comme tout à l'heure, au hasard, choisissons la porte 1. Puis, considérons que le présentateur, lui, nous montre une chèvre derrière la porte 2. Soit \(V_1\) l'évènement "la voiture se trouve derrière la porte 1" et \(C_2\) "le présentateur montre la chèvre derrière la porte 2". Alors, en utilisant la formule ci-dessus, on peut calculer \(P(V_1|C_2)\) la probabilité que la voiture soit derrière la porte 1 sachant que le présentateur ouvre la porte 2 :

\[P(V_1|C_2) = \frac{P(C_2|V_1)P(V_1)}{P(C_2)}\]

A ce point, il y a plusieurs subtilités :

  • Le présentateur, sachant que la voiture est derrière la porte 1 choisie par le candidat, peut ouvrir indifféremment la porte 2 ou la porte 3. On a donc \(P(C_2|V_1) = P(C_3|V_1) = \frac{1}{2}\)
  • \(P(V_1) = \frac{1}{3}\) car à la base, la voiture est répartie de manière équiprobable derrière l'une des 3 portes.
  • Le plus compliqué reste de calculer le dernier terme, ce que je vais tâcher de vous expliquer juste après.

Une astuce consiste à se rappeler que l'on peut décomposer le dénominateur comme suit : \(P(C_2) = P(C_2|V_1)P(V_1) + P(C_2|V_2)P(V_2) + P(C_2|V_3)P(V_3)\). En effet, la probabilité \(P(C_2)\) est la somme de chacune des probabilités conditionnelles multipliée par la probabilité de cette condition.

Or, \(P(V_1) = P(V_2) = P(V_3) = \frac{1}{3}\) car la voiture est encore une fois positionnée au hasard selon une loi uniforme.

Enfin, nous avons déjà déterminé que \(P(C_2|V_1) = \frac{1}{2}\). De même \(P(C_2|V_2) = 0\) car le présentateur ne va pas ouvrir la porte si la voiture se trouve derrière ! \(P(C_2|V_3) = 1\) car si le candidat choisit la première porte et que la voiture est derrière la troisième, le présentateur n'a d'autre choix que d'ouvrir la porte du milieu.

Du coup, on obtient :

\[P(V_1|C_2) = \frac{\frac{1}{2} \times \frac{1}{3}}{\frac{1}{2} \times \frac{1}{3} + 0 \times \frac{1}{3} + 1 \times \frac{1}{3}} = \frac{1}{3}\]

On a donc 33% de chance de gagner en campant sur nos positions originelles. On peut faire un calcul analogue pour \(P(V_3|C_2)\) et sans surprise on obtient :

\[P(V_3|C_2) = \frac{P(C_2|V_3)P(V_3)}{P(C_2)} = \frac{1 \times \frac{1}{3}}{\frac{1}{2} \times \frac{1}{3} + 0 \times \frac{1}{3} + 1 \times \frac{1}{3}} = \frac{2}{3}\]

Et tout ça colle bien avec notre simulation ! On retombe donc sur nos pieds.

Conclusion

On vient donc de voir comment une simple information donnée par le présentateur change totalement la donne et permet d'établir une stratégie gagnante. Attention, ça ne veut pas dire qu'en adoptant la stratégie adaptée vous gagnerez, mais vous maximisez vos chances de gagner. Et ces probabilités de gain peuvent se calculer relativement facilement à l'aide du théorème de Bayes qui est finalement un outil assez simple tant qu'on comprend les probabilités que l'on manipule et que l'on calcule. Alors à vos équations... Prêts ? Partez !

7 avril 2010

Dans mon viseur #2 : Où l'on parle d'infos, d'intox et de merlans frits...

Tout dire et ne rien dire à la fois, mélanger les saveurs et les couleurs pour servir l’information aussi éclectique soit-elle : c’est le retour d’un genre inauguré il y quelques mois de cela et qui mérite encore d’être rodé. Peu importe le temps dont on dispose, peu importe l’intérêt qu’on porte à l’information, elle mérite avant tout d’être traitée; c’est donc le but de cette petite digression bloguesque.

Pour commencer ce petit tour d’horizon, tournons nos regards vers la technologie, qui mène peu à peu ses révolutions dont la plus flagrante reste celle du tout tactile. Certains détestent, d’autres adorent, mais toujours est-il qu’il va falloir s’y faire, les bonnes vielles touches sont peu à peu vouées à disparaître. Et ce n’est pas Apple qui risque de me contredire puisque la sortie de l’iPad (autrefois nommée iSlate par les fanboys) s’est accompagnée d’un bruit assourdissant dans la technosphère et partout ailleurs. L’occasion de faire le tour de la bête et de découvrir ce qu’elle nous réserve. Mais rassurez-vous, l’honneur est sauf car la réponse à la question que l’on attendait tous est affirmative : oui, tout comme l’iPhone, l’iPad se mixe aussi !

La probabilité que le nouveau bébé de Steve Jobs fasse un flop reste cependant non nulle, même pour un as du branding comme lui. Seul l’avenir nous dira si oui ou non les tablettes tactiles réussiront à se frayer un chemin vers nos salons. En parlant de probabilités d’ailleurs, il s’avèrerait (et c’est la meilleure !) que le jeu du pile ou face n’est pas si équitable que ça. Et dire que depuis des siècles, des hommes jouent leur argent, voire leur vie à un jeu qui n’est pas si hasardeux qu’il y parait… Désormais je vais me mettre à la roulette russe, ça me parait plus équitable… ;-)

Ca aurait pu être une blague du premier avril, mais non, le nouveau site de notre président, tout comme sa facture d’un montant de 100 000€, est bel et bien en ligne. Les critiques furent rudes et acerbes. Tandis que certains ne supportent pas qu’un écusson aux allures royalistes soit arboré en lieu et place des symboles traditionnels de la République, d’autres trouvent l’auteur de ce site drôlement inspiré par nos cousins d’outre-atlantique. Même les amoureux de la typographie y retrouvent à dire : c’est vrai quoi, écrire "ELYSEE" sans accents pour un site proclamé 100% français, c’est la honte ! Heureusement, certains tentent de rétablir la vérité et de souligner les qualités d’un site (peut être) un peu trop décrié. Mais bon on s’en fout parce que ce malgré tout, on aura eu le droit à un joli easter egg en ce premier avril. Mort de lol, tiens.

Parce qu’il ne faut pas oublier qu’en avril, c’est la fête des petits farceurs que les webmasters sont des grands gamins dans l’âme. Imaginez-les entrain de comploter en secret pendant 365 jours pour concourir à cette course aux poissons. Des gros, des fins, des salés, des laconiques, des sophistiqués, il y en a pour tous les goûts. Et les geeks sont prolifiques : la preuve ! Et puis on ne va pas s’en cacher, le plus marrant et de loin, c’est de voir certaines personnes relayer les intox comme des infos en y croyant dur comme fer. Nous, c’est pas pareil, on ne dit pas qu’on n’ose même plus relayer une info un 1er avril de peur qu’elle soit en carton. La léthargie de l’info drainée par la peur de l’intox, mais le relayage en masse de l’intox motivé par la crise de rire, y a pas à dire l’homme est un drôle de poisson, surtout au mois d’avril… ;-)

2 janvier 2010

Au nouvel an, tout ne tourne pas rond à cause d'une histoire de zéro...

Aviez-vous déjà remarqué que le calendrier chrétien que nous avons adopté comporte quelques illogismes ? L’un des plus flagrands est celui ayant à trait au comptage des années. Si nous déclarons être actuellement en l’an 2010, il ne s’agit pas moins de la 2009ème année suivant la naissance de Jésus. Oui, vous ne rêvez pas, le calendrier actuel est fait de telle sorte que Jésus à eu un an en l’an deux. Et tout ça à cause d’une histoire de zéro…

En y regardant d’un peu plus près, l’année précédant la naissance de Jésus est numérotée -1. Ainsi on passe de l’an -1 av. J.-C. à l’an 1 apr. J.-C. et ce, sans transition : l’an zéro n’existe pas. Pourtant, le calendrier grégorien fut adopté en 1582, bien après l’apparition du zéro dans notre système numéraire actuel. En fait, bien que les Mayas et les Chinois aient (entre autres) perçu le besoin d’introduire le zéro, ce n’est qu’il y a environ 1800 ans que les indiens ont inventé la notion de "rien", de "vide" via le mot "śūnya".

La première trace écrite du zéro a été rédigée en 628 av. J.-C. par un mathématicien indien répondant au nom de Brahmagupta dans un livre intitulé Le commencement de l’univers, ou Brahmasphutasiddhanta, traitant du mouvement des planètes et du calcul de leur trajectoire précise. Il définit alors le nombre "zéro" comme suit : "C’est le résultat de la soustraction d’un nombre de lui-même". Une révolution était amorcée.

Non seulement introduit-il le zéro, mais il définit le résultat de plupart des opérations algébriques avec ce nouveau nombre (à savoir l’addition, la soustraction et la multiplication). Le seul écueil qui s’offrit à lui consistant en la division d’un nombre par zéro et en celle de zéro par lui-même. Il décréta que 0/0=0. et que le résultat de la division d’un nombre n par zéro était la fraction n/0. Ces règles ont été suivies pendant très longtemps par la plupart des mathématiciens.

Ce n’est qu’environ 500 ans plus tard qu’un autre mathématicien indien répondant au nom de Bhaskara a déclaré que n/0=∞. Bien entendu, ce résultat est faux, mais il permit la remise en question de la propriété de Brahmagupta, permettant ainsi, après de moult débats, de conclure à l’indétermination de ce résultat.

Quant à la division de zéro par lui-même, le résultat est là également indéterminé. Mais il est intéressant de remarquer que l’étude du quotient de deux valeurs tendant chacune vers 0, n’est rien d’autre que la base du calcul différentiel (dx/dy). En gros, c’est ce que vous cherchez à calculer lorsque vous voulez déterminer une vitesse instantanée par exemple. :-)

Depuis, l’usage du zéro s’est bien évidemment généralisé. C’est d’ailleurs ainsi qu’en informatique, on compte la plupart du temps à partir de 0. C’en est même devenu la base de notre système numéraire à 10 chiffres structuré à partir de la position de ces chiffres au sein même du nombre (ainsi, il est facile de déterminer le chiffre des centaines, des dizaines ou des unités par exemple), par opposition au système numéraire romain par exemple ou chaque symbole correspond à une valeur propre.

Pour en revenir à notre calendrier grégorien, l’année évoquée est en fait une sorte de mesure approchée par excès de l’espace temps écoulé depuis la date supposée (nous ne sommes plus à une inexactitude près) de la naissance de Jésus, par opposition à un système numéraire de comptage classique. Ce qui expliquerait que l’an zéro n’existe pas. Mais il faut avouer que tout serait bien plus logique s’il existait.

Bref, excusez ce petit écart mathématique uniquement destiné, au départ, à vous souhaiter mes meilleurs voeux pour cette année 2010 qui, si vous m’avez suivi jusqu’ici, est la dernière de cette décennie et qui, qui plus est, est composée de deux zéros : décidément, ils sont partout ! Bonne année à tous. ;-)

28 avril 2008

Les mathématiques ne donnent pas que de l'urticaire...

Aujourd'hui je voulais rompre ce long silence bloguesque qui sévit depuis dix jours maintenant. Aucun sujet ne m'a inspiré plus que les mathématiques, science exacte par excellence si il en est, qui, parait-il, hérisserait les cheveux de beaucoup d'entre nous, mais qui reste pourtant si magnifique. Quoi de plus bizarre qu'une ode aux mathématiques ? Pourtant, il y a bien des aspects de cette matière qui peuvent être attracteurs. Ce sont ces derniers que je vous propose de découvrir ensemble...

Il est commun de dire que l'on a jamais vraiment fait de mathématiques avant la prépa et c'est dans ce sens que j'irai également dans ces lignes. Oserais-je donc renier Thalès, Pythagore et autres Euclide dont les théorème sont plus qu'usités dans les études primaires et secondaires ? Il ne s'agit pas de les renier mais plutôt de rétablir la vérité : loin d'être des mathématiques, ce ne sont que des théorèmes et élever leur énoncé au rang de la matière tient plutôt de la synecdoque.

La noblesse de cette science provient de sa rigueur qui n'est que trop peu (si ce n'est pas) enseignée dans le secondaire. Cette rigueur est capitale dans l'assemblage des théorèmes, propriétés et définitions qui, brique par brique, permettent de construire un mur solide dont la cohérence et la rigueur sont le mortier. En mathématiques, tout se démontre, de la propriété la plus insignifiante au théorème le plus complexe. Cette ensemble comporte de nombreux liens qui pourraient être assimilés aux nombreuses poutrelles de la tour Eiffel, permettant ainsi de rejoindre le même boulon par de nombreux chemins, tous plus intéressants les uns que les autres.

Je parie que si je me mets à parler d'isomorphisme ou d'inégalité de Taylor-Lagrange, je vais perdre plus d'un de mes lecteurs en route, alors tentons d'aborder les choses différemment. Si je vous parle de Lego, il y a de fortes chances que cela vous remémore de longs moments à assembler des briques ensemble de manière à construire ce que vous dictait votre imaginaire... Si vous aimiez les légos, vous aimerez les mathématiques. Matérialisons les théorèmes par des sets de légos et les propriétés par les assemblages de briques qui les composent. Quant à la rigueur, il s'agit des dimensions des briques fournies que vous ne pouvez modifier sans aucun prétexte puisqu'elles ont été moulées de cette manière par des définitions.

Si longtemps vous avez appris à souffler lorsque vous trouviez les dimensions en centimètre du côté de ce triangle si singulier et à en éprouver une entière satisfaction, imaginez celle qui est associé à la démonstration réussie d'un théorème beaucoup plus général qui permet, cette fois ci, non pas de ne caractériser qu'un unique côté d'un triangle spécifique, mais tous les côtés de triangles quelconques. C'est la magie de la théorie qui ne peut s'appliquer qu'à l'aide de cette rigueur dont je parle tant.

Les applications ne deviennent que des détails, l'abstraction devient reine et devant vous, tout s'éclaire au fur et à mesure de l'assimilation de ce nouveau langage. Oui, les mathématiques sont un langage qui permet de formaliser des idées et concepts, tels les mots qui formalisent une pensée ou une opinion. La capacité d'atteindre un niveau d'abstraction de ce type ne peut s'expliquer que part la présence d'un grand génie en l'homme qui est capable du pire comme du meilleur. Les mathématiques font partie de ce que l'homme a fait de mieux dans son règne animal...