Modèles d’urnes de Condorcet, Ehrenfest et Polya

Tirages avec remise et sans remise, et autres
samedi 17 novembre 2012
par  Alain BUSSER

L’idée originale semble remonter à Jean Bernoulli avec des cailloux (calculi en latin) dans un vase (urna en latin). Voici un exemple célèbre de boules tirées au hasard dans une urne :

Or ce genre de jeu existait déjà à l’époque de Bernoulli et c’est clairement ce à quoi il faisait allusion avec ses cailloux dans un vase.

Chez Pierre-Simon de Laplace, les cailloux sont devenus des billets et le vase, une urne :

Chez Nicolas de Condorcet par contre, les billets sont redevenus des cailloux [1] et l’urne est devenue un sac :

MathsOntologie est donc fidèle à Condorcet, avec son objet sac qui permet de stocker des objets éventuellement en plusieurs exemplaires [2]. On peut ajouter un élément à un sac, enlever des éléments satisfaisant un critère, ou choisir un élément au hasard dans le sac.

Voici donc comment ce sac permet de modéliser divers problèmes d’urne avec MathsOntologie :

Avec remise

Pour composer l’urne décrite par Condorcet ci-dessus, on commence par créer un sac vide (en fait, une liste vide transformée en sac) puis on y ajoute 90 fois de suite une boule blanche, et 10 fois de suite une boule noire :

Ensuite, une main innocente est modélisée par auHasard ; ici sollicitée 8 fois :

Pour répéter 1000 fois le tirage (avec remise) d’une boule dans l’urne, le plus simple est de créer un autre sac initialement vide et d’y stocker, au fur et à mesure, les résultats des tirages ; après ça on peut faire des statistiques sur ce sac, par exemple afficher ses effectifs :

Cette simulation de tirages avec remises permet de découvrir expérimentalement les variables binomiales : Par exemple, le nombre de boules blanches dans l’expérience avec 8 répétitions ci-dessus suit une loi binomiale de paramètres 8 et 0,9.

Sans remise

On peut enrichir l’exemple des billets de Laplace, avec des billets sur lesquels quelque chose est imprimé : Des cartes à jouer. Pour construire un jeu de 32 cartes, on choisit une liste de valeurs (as, 7, 8, 9, 10 et les figures) et une liste de couleurs (carreau etc.). Puis on boucle sur les valeurs, et sur les couleurs, en concaténant (par une virgule en MathsOntologie) la valeur, le mot « de », puis la couleur, et en ajoutant la carte ainsi construite dans le jeu de cartes (un sac évidemment) :

Pour simuler une main au poker, on pense à répéter 5 fois le tirage d’une carte :

Las ! Le 7 de pique est sorti deux fois dans l’exemple ci-dessus. Cela est dû à ce que le tirage est fait avec remise, ce qui permet d’avoir deux fois (voire plus même si c’est rare) la même carte. En stockant ladite carte dans une variable carte avant de la placer dans la main (encore un sac !) on ne résout certes pas le problème :

(c’est le valet de pique qui est sorti deux fois).

Cependant, il suffit d’enlever cette carte (plus précisément toutes les cartes qui lui sont égales) du jeu pour avoir un tirage sans remise, comme le prouve le nombre de cartes restantes dans le jeu :

Les tirages sans remises permettent de constituer des échantillons, sur lesquels des activités intéressantes peuvent être menées en classe.

Ehrenfest

Le modèle d’Ehrenfest complète les tirages sans remises : Non seulement on ne remet pas la boule dans l’urne, mais on la met dans une autre urne. Il faut donc

  • numéroter les boules pour savoir dans quelle urne se trouve la boule choisie ;
  • avoir deux urnes : L’une initialement pleine, l’autre initialement vide ;
  • choisir une boule au hasard, et stocker son numéro dans une variable éponyme ;
  • Si cette boule est dans l’urne 1, l’en enlever, et la placer dans l’urne 2 ; sinon faire le contraire :

Évidemment, il est rare après 8 répétitions que l’urne 2 contienne moins de 8 boules, parce que la probabilité de tirer une boule d’une urne presque vide, est très faible. Après 100 tirages, la situation est différente :

Ci-dessus, il ne reste plus que 48 boules dans l’urne 2, parce que plusieurs d’entre elles sont retournées à l’urne 1.

On peut étudier l’évolution du nombre de boules de l’urne 2 par un procédé similaire à celui du premier onglet :

  • créer une « collection ordonnée » initialement vide (avec stats := #() commecollectionOrdonnée)
  • à chaque répétition, y stocker le nombre de boules dans l’urne 2 (avec stats ajoute: (urne2 taille))
  • observer le résultat après un millier de prélèvements (notamment, son écart-type).

Polya

L’urne de Polya quant à elle, enrichit la notion de tirage avec remise : Non seulement on remet la boule dans l’urne, mais on en ajoute une de même couleur. Pour mettre un peu de gaité, plutôt que les boules blanches et noires de Condorcet, on prend des boules rouges et bleues ; et on s’intéresse à l’évolution de la proportion de boules rouges. Il suffit pour cela, de rajouter au sac, un duplicata de la boule qu’on vient de tirer :

On constate une stabilité (nombre de boules bleus croissant) dans l’instabilité (du fait qu’il y a beaucoup de boules bleues, il y a peu de chance de tirer une boule rouge, et donc de modifier leur nombre). Comme on s’en doute, l’inverse peut aussi arriver, et d’autres situations intermédiaires :

Les proportions de boules rouges semblent équiprobables, comme on le vérifie en recommençant 100 fois une expérience de Polya à 9 boules :

Même avec 1000 répétitions, le tableau des effectifs montre que les répartitions sont équiprobables sur l’ensemble des nombres de 1 à 9 :

Les diagrammes en bâtons le confirment visuellement :

avec 81 boules

Le tableau des effectifs est peu utile à cause de sa longueur :

Aussi un regroupement par classes est-il préférable :

Lui aussi montre une équiprobabilité.

Ce micromonde n’est pas nécessaire pour étudier ce modèle, un algorithme numérique suffisant :

  1. En appelant r le nombre de boules rouges et b le nombre de boules bleues, on initialise r et b à 1 ;
  2. Dans une boucle,
    1. on commence par calculer un nombre pseudoaléatoire entre 0 et 1 (« random ») ;
    2. S’il est plus petit que r/(r+b) on incrémente r ;
    3. sinon on incrémente b
  3. on affiche la nouvelle valeur de a/(a+b).

Mais c’est quand moins intuitif que le modèle avec le sac.


Présentations animées des deux derniers modèles :

Les onglets consacrés à Paul Ehrenfest et à George Pólya ci-dessous sont illustrés par des graphiques interactifs en JavaScript qui nécessitent un navigateur Internet gérant html5 (Opera, Chromium ou Firefox par exemple).

Polya

Urne de Polya

Expérience

Comment ça marche

Au départ, l'urne contient deux boules, une bleue et une rouge. À chaque répétition, on extrait au hasard une boule de l'urne, et on rajoute dans l'urne une boule de même couleur.


L'urne contient 1 boules rouges et 1 boules bleues; soit un total de 2 boules actuellement.

Sur le long terme

À la longue, la proportion de boules rouges se stabilise mais sur quelle valeur ?


En recommençant plusieurs fois l'expérience, on constate qu'à peu près toutes les répartitions entre 0 et 100% sont atteintes asymptotiquement:

Statistiques sur 8 répétitions

On répète 1000 fois l'expérience de répéter 8 ajouts de boules:


Statistiques sur 50 répétitions

On répète 1000 fois l'expérience de répéter 50 fois l'ajout de boules:


Comme le diagramme en bâtons des effectifs est peu lisible, on lui préfère un histogramme :


Ehrenfest

Modèle des urnes d'Ehrenfest

Avec deux urnes, l'une initialement vide

Règle du jeu : On tire au hasard une boule, repérée par un numéro (non lisible ci-dessous) et on la change d'urne. Initialement, toutes les boules sont dans l'urne bleue (à droite).

On s'intéresse à l'évolution à long terme: Y a-t-il une configuration d'équilibre ?

Simulation avec 200 boules


La boule numéro a été tirée au sort.

Évolution à plus long terme






La théorie prévoit une distribution binomiale à l'équilibre:

Avec 4000 boules



Pour les 4000 derniers, on a cette distribution temporelle:

Ceci montre qu'autour de la distribution d'équilibre k=200, il y a des fluctuations.


Conclusion

Quand on a les boules il faut vider son sac !


[1en fait, des boules de billard, indiscernables au toucher

[2le vrai nom est multiensemble.


Commentaires

Annonces

Prochains rendez-vous de l’IREM

Séminaire EDIM-IREM

- Mercredi 8 mars 2017, 14h-18h, PTU, Saint-Denis, salle S23.6
- Mercredi 12 avril 2017, 14h-18h, campus du Tampon
- Mercredi 3 mai 2017, 14h-18h, PTU, Saint-Denis, salle S23.6
- Mardi 13 juin 2017, 14h-18h, campus du Tampon
- Mercredi 14 juin 2017, 14h-18h, PTU, Saint-Denis, salle S23.6

Semaine des mathématiques

Du 23 mars au 4 avril 2017 dans l’académie de la Réunion.


Brèves

À travers les labyrinthes : algorithmes et fourmis

dimanche 1er septembre 2013

Quand les chercheurs mettent au point des modèles d’optimisation et de recherche de plus court chemin qui s’inspirent du comportement de masse de colonies de fourmis...
À écouter : Sur les Épaules de Darwin, émission diffusée sur France Inter samedi 31 août 2013.

Rencontres Mondiales du Logiciel Libre à St-Joseph

mardi 20 août 2013

Les RMLLd se dérouleront pour la 2e fois à Saint-Joseph du 22 au 25 août.
C’est une opportunité pour les élèves qui suivent la spécialité ISN et les passionnés d’informatique.

Voici pour le samedi et le dimanche quelques interventions choisies :
- http://2013.d.rmll.info/Raspberry-votre-ordinateur-au-format-carte-de-credit?lang=fr
- http://2013.d.rmll.info/Materiel-libre-et-DIY?lang=fr
- http://2013.d.rmll.info/Arduino-de-l-electronique-libre?lang=fr

Noter aussi les conférences Art et Culture du dimanche, ainsi qu’une conférence plus engagée.

Le programme complet se trouve ici. Une radio sera ouverte pour l’occasion.
Des plaquettes à distribuer se trouvent ici.

Hyper-vidéos pour l’algorithmique au lycée

dimanche 19 août 2012

Olivier Roizès, à la demande de l’ADIREM, a réalisé une collection d’hyper-vidéos de présentation de logiciels et environnements de programmation. Ces hyper-vidéos, c’est-à-dire des vidéos contenant des éléments clicables, devraient être utiles aux enseignants désireux de se familiariser avec Python, CaRMetal, R, Rurple, Scilab ou Xcas.

Ouverture du SILO

mardi 1er novembre 2011

Le SILO (Science Informatique au Lycée : Oui !) est un espace collaboratif documentaire de partage et de formation collégiale, à destination des professeurs appelés à enseigner l’informatique au lycée.

Une initiative du CNDP, de l’INRIA et de Pasc@line, à laquelle se sont associés SPECIF, fuscia, EPI et ePrep.

Sur le Web : Site du SILO

Introduction à la science informatique

lundi 12 septembre 2011

Le CRDP de Paris publie le premier ouvrage destiné aux professeurs chargés d’enseigner la nouvelle spécialité « Informatique et sciences du numérique » en Terminale S à la rentrée 2012. Cet ouvrage a été coordonné par Gilles Dowek, directeur de recherche à l’INRIA.

Sur la création de la spécialité ISN, on pourra également consulter l’interview donnée au Café pédagogique par l’inspecteur général Robert Cabanne.

Sur le Web : CRDP de Paris

Deux publications sur l’algorithmique

samedi 17 octobre 2009

L’IREM d’Aix-Marseille publie une brochure de 73 pages, téléchargeable librement, intitulée Algorithmes et logique au lycée. Ces notions sont illustrées et déclinées sur des exercices du programme de spécialité mathématique en série L, mais sont adaptables aux programmes à venir.

Le hors série thématique n° 37 du magazine Tangente, disponible actuellement en kiosque, s’intitule « Les algorithmes. Au cœur du raisonnement structuré ». Extrait de l’éditorial : « La rédaction de Tangente a conçu la quasi-totalité de ce hors série thématique pour qu’il puisse être lu par des élèves de Seconde ».

Une carte mentale pour l’algorithmique

jeudi 10 septembre 2009

Sur son site, Jean-Jacques Dhénin a publié une carte mentale géante qui renvoie vers plus de 30 documents en ligne sur l’algorithmique. Tout ce qu’il faut — et même davantage — pour faire face au nouveau programme de Seconde !

Un catalogue libre d’algorithmes pour le lycée

dimanche 30 août 2009

Guillaume Connan, de l’IREM de Nantes, publie un catalogue libre de 119 pages d’algorithmes pour le lycée. Sur son site très riche, on trouvera d’autres documents en rapport avec l’algorithmique, notamment sur l’utilisation des langages fonctionnels au lycée et sur la comparaison programmation fonctionnelle/programmation impérative.

L’algorithmique à l’IREM de Lille

vendredi 26 juin 2009

Le groupe AMECMI de l’IREM de Lille vient de mettre en ligne des ressources importantes au service des professeurs de Seconde :

- Algorithmique et programmation (Emmanuel Ostenne)
- Bibliographie amoureuse de l’algorithmique (Alain Juhel)

Statistiques

Dernière mise à jour

samedi 18 mars 2017

Publication

735 Articles
Aucun album photo
128 Brèves
11 Sites Web
126 Auteurs

Visites

956 aujourd'hui
1169 hier
1961488 depuis le début
21 visiteurs actuellement connectés