« Le problème des anniversaires »

Enoncé :

Dans un groupe de n=30 personnes quelle est la probabilité qu’il y en ait au moins deux ayant le même jour d’anniversaire ?

Le calcul de cette probabilité ne présente pas de difficulté, si on note p cette probabilité, on a :

$P=1-(\dfrac{A^{30}_{365}}{365^{30}})$ où $A^{30}_{365}$ désigne le nombre d’arrangements de 30 jours parmi les 365 jours de l’année ; $\dfrac{A^{30}_{365}}{365^{30}}$ est la probabilité que les 30 jours soient différents deux à deux, c’est-à-dire la probabilité de l’évènement contraire de celui qui nous intéresse.

La machine (TI84) se charge du calcul dans l’écran suivant :

Sans l’aide de la machine, le calcul aurait été fastidieux.

Je traite maintenant le même problème pour n=50 personnes :

Dans les deux écrans précédents, le deuxième a exécuté l’instruction du premier. La calculatrice signale que le calcul dépasse les capacités de la machine ; faire le calcul « à la main » est fastidieux et c’est là qu’une simulation de l’expérience aléatoire prend tout son sens.

Simulation de l’expérience aléatoire « Tirer au hasard 50 jours parmi les 365 jours de l’année »

Sur « la TI84 » l’instruction qui va simuler le tirage d’un jour, au hasard, parmi les 365 de l’année est « Int(365Rand)+1 », c’est-à-dire « (Partie entière de 365Rand)+1 », qui envoie un entier « au hasard » de 1 à 365.

On exécute plusieurs fois cette instruction dans l’écran suivant :

L’instruction « Seq(Int(365Rand)+1,X,1,50) » envoie une liste de 50 entiers « au hasard » entre 1 et 365, entiers qui ne sont pas nécessairement distincts ; elle simule donc des tirages successifs de 50 entiers entre 1 et 365, tirages avec remise. Une liste du type précédent simule donc les jours d’anniversaires de 50 personnes et, si les 50 entiers de la liste sont distincts 2 à 2, il n’y a pas 2 personnes qui ont le même jour d’anniversaire.

Sur des modèles de calculatrice plus récents comme les TI 82 +, TI 83 + ou TI 82 Stats, on peut utiliser une autre syntaxe : entAléat(1,365). On peut obtenir la liste de 50 entiers grâce à l’instruction : entAléat(1,365,50).

Comment tester si les entiers de la liste sont tous distincts ou pas ?

Je propose l’algorithme suivant :
– On ordonne la liste dans l’ordre croissant ;
– un compteur F est initialisé à 0 ;
– on « balaye » la liste du premier au dernier et si on trouve deux entiers égaux le compteur F augmente de 1 ;
– si F = 0, ils sont tous distincts.

Je propose maintenant un algorithme qui, pour deux entiers donnés N (positif) et p (1≤p≤365), génère un échantillon de N listes de p entiers tirés au hasard entre 1 et 365 et qui calcule la fréquence des listes n’ayant pas tous leurs éléments distincts dans l’échantillon.
– On saisit N et p
– On initialise un compte G à 0, compteur chargé de dénombrer les listes dont les éléments sont tous distincts
– On génère un échantillon de N listes de p entiers au hasard entre 1 et 365, pour chacune de ces listes on applique l’algorithme précédent et si F=0 le compteur G augmente de 1
– 1-G/N est la fréquence des listes n’ayant pas tous leurs éléments distincts dans l’échantillon.

Le programme « ANNIV » va exécuter cet algorithme :

Attention les trois premières instructions du dernier écran sont sorties deux fois.

On exécute trois fois ce programme, la première pour N=100 et p=30, et les deux autres pour N=500 et p=30 ; ce qui est fait dans les écrans suivants :

Comme on veut que la fréquence avoisine la probabilité, N=100 n’est pas assez grand ; pour rappel, la probabilité a été calculée plus haut et vaut 0.7063…..

Je suis satisfait, le programme fonctionne ! C’est ce que je voulais vérifier avant de l’appliquer à p=50.

Selon cette simulation, la probabilité que dans un groupe de 50 personnes choisies au hasard il y ait deux personnes, au moins, dont l’anniversaire est le même jour est 0.974.

Je crois que la TI89 ou la « voyage 200 » de chez Texas Instrument acceptent le calcul de cette probabilité sans saturer. Il reste alors à vérifier et à faire la comparaison.

Pour contourner le problème du calcul signalé plus haut, dont l’exécution dépasse les capacités de la machine, et aussi par souci de vérification du résultat affiché dans le dernier écran, je propose ceci :

l’instruction « seq((365-n)/365,n,0,49)stoL1 » envoie la liste L1 de tous les nombres (365-n)/365, pour n entier variant de 0 à 49 et l’instruction « 1-prod(L1) » envoie le nombre égal à la différence entre 1 et le produit de tous les nombres de L1 ; on a alors effectué le calcul refusé par la machine en obligeant celle-ci à le faire différemment , le résultat est affiché dans la copie d’écran suivante et est égal à la probabilité cherchée. 

Enoncé :

En tirant successivement, au hasard et avec remise, cinq fois un chiffre parmi $\{0 ;1 ;2 ;3 ;4 ;5 ;6 ;7 ;8 ;9\}$ quelle est la probabilité d’obtenir deux paires ?

Exemple : $\{1 ; 1 ;5 ;3 ;3\}$ est un évènement favorable.

Cet exercice a un contexte : « Le test du poker ».Le lecteur curieux pourra consulter l’article de l’auteur publié dans la revue « MathémaTICE » et intitulé : « Transformer un nombre en la liste de ses chiffres. Deux applications  ». Le « test du poker » y est décrit sans ambigüité.

Je trouve cette probabilité délicate à calculer. C’est mon avis mais peut-être que le lecteur ne le partage pas et fait ce calcul sans y voir de difficulté, néanmoins je pars du postulat que cette probabilité est difficile à calculer, en valeur exacte, et j’en appelle à une simulation pour l’évaluer.

L’instruction « seq(int(10rand),X,1,5) » envoie cinq entiers, éventuellement égaux, entre 0 et 9. Elle simule donc l’expérience aléatoire qui nous intéresse.

Dans l’écran qui suit, on fait trois simulations :

Seule la troisième donne deux paires.

Je propose l’algorithme suivant pour détecter les listes où il y a deux paires :
– Une liste L1 de 5 chiffres est donnée ;
– on ordonne L1 dans l’ordre croissant ;
– on initialise un compteur F à 0 ;
– on « balaye » L1 du premier au dernier et si on trouve deux termes consécutifs égaux mais pas trois termes consécutifs égaux, le compteur F augmente de 1 ;
– si F = 2, dans L1 il y a deux paires, et seulement dans ce cas.

Je propose l’algorithme suivant, algorithme dont la tache est de générer un échantillon de N listes L1 qui modélisent l’expérience aléatoire et qui calcule la fréquence de celles où il y a deux paires.
– On saisit N ;
– on initialise un compteur G à 0, compteur qui va dénombrer les listes où il y a 2 paires ;
– on génère N listes L1 ;
– pour chacune des N listes on applique l’algorithme précédent et si F = 2, G augmente de 1 ;
– on affiche G/N qui est la fréquence cherchée.

Le programme « TYPE3 » donné dans les écrans suivants exécute cet algorithme :

Attention, dans le dernier écran, les deux premières instructions sont sorties deux fois.

Dans les écrans qui suivent on applique ce programme :

Je propose maintenant le calcul de la probabilité :

Il faut calculer : $C_5^2 \times 10 \times C_3^2 \times 9 \times 8 = 21 600$. En effet, j’ai sélectionné 2 places parmi 5 sur lesquelles il y a 10 possibilités de mettre un chiffre, il reste alors $C_3^2$ façons de sélectionner 2 places parmi les 3 restantes sur lesquelles il reste 9 façons de mettre un chiffre et sur la place restante il y a 8 possibilités de mettre un des chiffres restants.

En dénombrant ainsi, on en compte deux fois trop ; par exemple, avec $C_5^2$, je sélectionne les 2 premières places où je mets 1 et 1 puis avec $C_3^2$, je sélectionne les 2 dernières places où je mets 2 et 2 et sur la place restante, pour la cinquième, je mets 5 ; j’obtiens ainsi $\{1 ;1 ;5 ;2 ;2\}$.

Dans les $C_5^2$, je sélectionne aussi les 2 dernières places où je mets 2 et dans les $C_3^2$ restantes, il y a les 2 premières où je mets 1 et dans la restante, la cinquième, je mets 5. J’obtiens ainsi la même liste de 2 paires $\{1 ;1 ;5 ;2 ;2\}$.

Il y a donc $\frac{21 600}{2} = 10 800$ listes de 2 paires et la probabilité cherchée est $\frac{10800}{10^5}=0.108$.

Les fréquences obtenues avec la simulation sont proches de la probabilité calculée. L’algorithme se révèle, malgré tout, faux : en effet, F = 2 ne caractérise pas les listes où il y a deux paires, il compte aussi « les fulls » comme le montre l’exemple qui suit :

« le full » $\{1,2,1,2,1\}$ devient $\{1,1,1,2,2\}$ = L1 après avoir été ordonné. On rajoute le terme L1(5)+1 dans L1(6). Le compteur F est initialisé à 0 et on balaye cette dernière liste de la gauche vers la droite :
– L1(1)=L1(2) et L1(2)=L1(3), donc F=0 encore ;
– L1(2)=L1(3) et L1(3)$\neq$L1(4) donc F=1 ;
– L1(4)=L1(5) et L1(5)$\neq$L1(6) donc F=2.

On peut se demander pourquoi le résultat envoyé par le programme ne suggère pas que l’algorithme est faux ? La raison est que non seulement la probabilité des « fulls » vaut 0,0090, elle est donc pratiquement indécelable à la vue du résultat mais aussi parce que 500 simulations sont insuffisantes pour mettre en évidence une aussi petite différence. (Voir annexe 2.)

– Après avoir ordonné la liste L1, on lui rajoute un premier terme égal à L1(1)-1 et deux derniers termes, respectivement, égaux à L1(5)+1 et L1(5)+2 ;
– on balaye la liste L1 de n=2 à n=5 et si L1(n)=L1(n+1) et L1(n+1)$ ≠$L1(n+2) et L1(n)$ ≠$L1(n-1), F augmente de 1 ;
– F=2 caractérise alors les listes qui sont des doubles paires.

Le programme qui suit, nommé « PAIRES », traduit cet algorithme.

Dans le dernier écran, seule la dernière instruction est à prendre en compte.

Dans l’écran qui suit, on a exécuté deux fois ce programme pour N=500.

On a obtenu 0.108 puis 0.114 ; je rappelle que la probabilité calculée est 0.108.

Dans un précédent article « jouons aux fléchettes avec la TI 83 ! », j’ai voulu explorer la possibilité d’utiliser les générateurs de nombres aléatoires pour calculer, en valeur approchée, une aire ou une intégrale difficiles à calculer (« méthode de Monte-Carlo »). Ici le problème est du même genre, mais appliqué à un calcul de probabilité.

Ces deux problèmes entrent dans le cadre de la définition de « la méthode de Monte-Carlo », c’est pour cette raison que je les associe dans cette conclusion.

Voici la définition donnée dans Wikipédia :

J’ai assouvi ma curiosité mais des questions subsistent sur la pertinence de ces méthodes :
– Dans les deux cas, on constate que la précision ne va pas au-delà de la deuxième décimale et on est incapable d’évaluer l’erreur précisément, disons qu’elle est de l’ordre de « quelques centièmes ». Pour cette raison, dans le cas du calcul d’une probabilité la méthode ne doit pas être employée avant d’avoir épuisé toutes les possibilités de calcul en valeur exacte.
– Pour le calcul d’une intégrale, si la fonction est continue, on dispose de méthodes de calculs numériques très performantes pour en donner une approximation avec une précision donnée, l’emploi de la méthode de l’article ne me paraît pas, alors, approprié. Si la fonction n’est pas continue, je ne vois pas comment appliquer la méthode puisqu’on a un problème de délimitation de l’aire concernée, peut-être y a-t-il ici la justification du « de dimension plus grande que 1 » de la définition de Wikipédia ? 
– Pour le calcul d’une aire, il faut que le domaine dont on veut évaluer l’aire soit délimité de façon exploitable pour faire des simulations ; pour illustrer ceci, je cite cet exemple donné dans Wikipédia :

Le domaine est ici clairement délimité, par l’eau ou la terre, c’est plutôt le simulateur qui pose problème, car j’aimerai bien qu’on m’explique comment tirer « au hasard » dans le terrain carré avec un canon, à moins que les tirs de celui-ci ne soient commandés par un générateur de nombres aléatoires ?

Complément de Bernard Toumache

Pour calculer la probabilité d’obtenir deux paires dans une liste de cinq chiffres, j’ai utilisé l’outil « calculatrice ». Il faut bien reconnaitre que, si on veut que le programme envoie le résultat en un temps acceptable, le nombre d’échantillons est alors limité : de l’ordre de 500, voire 1 000.

De plus, le programme est, à mon avis, plutôt laborieux à élaborer, ceci étant dû au fait que la machine n’est pas équipée d’une fonction qui calcule la fréquence d’une « valeur » dans une liste. Je propose de traiter le même problème avec le tableur « Excel », pour faire la comparaison. En effet, il est, lui, équipé d’une fonction qui calcule les fréquences, comme décrit plus haut ; il s’agit de « nb.si ». J’adapte donc l’algorithme à cette fonction.

Algorithme :
– On génère une plage de cinq cellules qui sont des entiers aléatoires entre 0 et 9 ;
– on calcule la fréquence de chaque cellule de la plage précédente dans cette même plage pour, ainsi, obtenir une nouvelle plage de cinq cellules ;
– dans cette dernière plage, on calcule le « max » et la fréquence du « max », on obtient ainsi une nouvelle plage de deux cellules ;
– les doubles paires, dans la première plage, sont caractérisées par : le « max » est 2 et la fréquence du « max » dans la deuxième plage est 4

La feuille Excel suivante, nommée « deux paires »

, exécute l’algorithme précédent sur des échantillons de taille 10 000 : (Insérer le document en téléchargement)

Dans les deux écrans précédents, la colonne M calcule le « Min », qui n’intervient pas ici, elle n’est donc pas à prendre en compte.

Les six écrans précédents ont été obtenus en appuyant sur la touche « F9 », ce qui a pour effet de faire fluctuer l’échantillon. Chaque écran visualise, dans la barre de calculs, une instruction essentielle de l’algorithme. Outre que l’échantillon est de taille 10 000, le résultat est instantané et on peut faire fluctuer l’échantillon à volonté. De plus, la conception du programme est bien plus aisée ; l’outil « tableur » est nettement plus performant.

Je propose maintenant une autre feuille de calcul « Excel » , conçue selon le principe de la feuille de calcul « deux paires » et qui calcule la fréquence des « deux paires » augmentée de la fréquence des « fulls » dans un même échantillon, ceci pour voir si les résultats affichés suggèrent qu’il y a une erreur. Les « fulls » sont caractérisés par « le « Max » est 3 et le « Min » est 2 (voir l’algorithme de la feuille de calcul « deux paires » pour la signification de « Max » et « Min »).

Dans cette feuille de calcul, les échantillons sont de tailles 10 000, et les copies d’écran suivantes ont été obtenues en appuyant plusieurs fois sur F9 ; je me limite à trois copies d’écran mais le lecteur curieux pourra le faire autant de fois qu’il le veut pour mettre en évidence, peut-être, l’erreur.

La fréquence des « « fulls » et des « doubles paires » » ne descend jamais, au moins avec les échantillons générés par le tableur et je ne me suis pas limité à trois, en dessous de 0,11. L’erreur est bien mise en évidence.

Dans le même esprit, je propose aussi ce graphique :

La droite en rouge est le nuage de points « Y=0,108 » qui est la probabilité des doubles paires et le nuage bleu est le nuage des points $(n,\frac{f(n)}{n})$ pour n variant de 1 à 10 000, $f(n)$ désignant le nombre de réalisations de l’événement « double paire ou full » dans les $n$ premières plages issues de l’échantillon de taille 10 000 engendré par Excel , c’est-à-dire le nuage de points engendré par le premier algorithme faux : on voit bien que ça ne converge pas !

Complément de la rédaction de MathémaTICE et d’Hubert Raymondaud.

Nous avons vu en cours de lecture de cet article que le premier algorithme proposé dans l’exemple 2 était faux. Cette erreur, difficilement décelable, a ensuite été facilement corrigée par Bernard Toumache. Nous revenons ici sur le fait qu’un nombre de simulations aussi faible que 500 ne permet pas de valider l’algorithme sur la simple observation de la « proximité » des fréquences simulées et de la probabilité calculée.

Le tableau ci-dessous montre bien la légère surestimation engendrée par l’algorithme proposé initialement. Le détail des fonctions R

utilisées figure ci-dessous.

Exploration de la distribution simulée des fréquences calculées respectivement avec l’algorithme initial (erroné) et l’algorithme corrigé, proposés par Bernard Toumache.

On effectue 1000 répétitions des 500 simulations faites dans les algorithmes proposés. Concernant le temps d’exécution, on touche aux limites des capacités des types d’ordinateurs utilisés habituellement.

Algorithme initial (erroné) 1000 simulations de 500 répétitions.

Algorithme corrigé 1000 simulations de 500 répétitions.

On observe bien un léger décalage des distributions observées, entre les résultats des deux algorithmes.

Il peut être intéressant de proposer aussi un algorithme qui réinvestisse et donne du sens aux outils de la statistique descriptive vus au collège et au lycée :

Comment dénombrer les doubles paires différentes ?

Répéter N fois les instructions suivantes :

Faire le tableau des effectifs de la série des 5 nombres simulés.

Si le tableau contient 2 fois l’effectif 2 on a une double paire.

L’avantage est aussi que l’on peut alors très facilement passer au dénombrement de carré, de full ….