algorithme anniversaires

Utilisation à l'épreuve de modélisation de l'agrégation de mathématiques

Modérateur : xcasadmin

Denizou
Messages : 61
Inscription : mer. juin 13, 2012 7:23 am

algorithme anniversaires

Message par Denizou » mar. févr. 17, 2015 10:39 am

Bonjour,

je souhaite simuler n fois des assemblées de 2 à 30 personnes et calculer la fréquence de personnes nées le même jour et déterminer combien il faut de personnes pour que la probabilité qu'au moins deux personnes soient nées le même jour dépasse 50% (classique !).

Mon idée était la suivante :

1) écrire une procédure f1(k) créant une liste de k nombres aléatoires entiers entre 1 et 365 et renvoyant 1 dès que deux nombres sont identiques, 0 sinon.

2) écrire une procédure f2(n) qui répète n fois la procédure f1(k) pour k allant de 2 à 30 et renvoie une liste de 29 valeurs avec la fréquence des 1 observées sur les n tirages.

Ces deux procédures fonctionnent mais je trouve des fréquences beaucoup plus élevées que la théorie. Ainsi, selon les résultats de f2, il faudrait 13/14 personnes minimum pour que la probabilité recherchée dépasse 50% alors que l'on doit trouver 23 personnes (et d'ailleurs le graphe simulé ne correspond pas du tout au graphe théorique non plus).

En bidouillant, j'arrive à obtenir les valeurs correctes mais je ne comprends pas ce qui ne va pas dans mon raisonnement et pourquoi j'obtiens des valeurs trop fortes. Soit dit en passant, je ne comprends pas non plus pourquoi les algorithmes modifiés donnent les bonnes réponses !

Merci de votre aide

FD

parisse
Messages : 5734
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: algorithme anniversaires

Message par parisse » mar. févr. 17, 2015 11:12 am

Il faudrait le source des fonctions pour essayer de comprendre.

Denizou
Messages : 61
Inscription : mer. juin 13, 2012 7:23 am

Re: algorithme anniversaires

Message par Denizou » mar. févr. 17, 2015 11:27 am

parisse a écrit :Il faudrait le source des fonctions pour essayer de comprendre.
oui, j'ai oublié de publier les algorithmes !

1er algorithme :

Code : Tout sélectionner

anni(n):={
  local d,t,k,p;
  d:=randmatrix(1,n,alea(365)).+1;
  t:=0;
  for(k:=0;k<n-1;k++){
  
    for(p:=k+1;p<n;p++){
    
        if(d[0,k]==d[0,p]){t:=1; break} //renvoie 1 dès que 2 éléments sont identiques.
    }
  }
  retourne t;
}:;
puis

Code : Tout sélectionner

simul(n):={
  local a,k,m,p,s,t,x;
   m:=[0];
   s:=1.;
   t:=[0];
   
   for(k:=2;k<=30;k++){
     a:=[0];
   
     for(p:=1;p<=n;p++){
       a:=concat(a,anni(k));
     } 
     m:=concat(m,count_eq(1,a)/n); // fréquence observée des 1 sur les n tirages
     s:=s*(366-k)/365; 
     t:=concat(t,1-s)   // valeur théorique
   }
  retourne plotlist(m),plotlist(t,couleur=rouge);
}:;

2nd algorithme

Code : Tout sélectionner

anni(n):={
  local d,t,k,p;
  d:=randmatrix(1,n,alea(365)).+1;
  t:=0;
  for(k:=0;k<n-1;k++){
  
    for(p:=k+1;p<n;p++){
    
        if(d[0,k]==d[0,p]){t:=1+t}
    }
  }
  retourne t; // renvoie le nombre de paires identiques dans la liste
}:;

Code : Tout sélectionner

simul(n):={
  local a,k,m,p,s,t,x;
   m:=[0];
   s:=1.;
   t:=[0];
   
   for(k:=2;k<=30;k++){
     a:=[0];
   
     for(p:=1;p<=n;p++){
       a:=concat(a,anni(k));
     } 
     m:=concat(m,count_sup(1,a)/n); // ne prend en compte que le nombre de paires supérieures ou égales à 2 !?
     s:=s*(366-k)/365;
     t:=concat(t,1-s)   
   }
  retourne plotlist(m),plotlist(t,couleur=rouge); // les courbes obtenues sont cohérentes
}:;
Pour info, j'ai trouvé ces algorithmes sur internet pour Xcas qui posent exactement le même problème :
http://megamaths.free.fr/pdf/algorithme.pdf

parisse
Messages : 5734
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: algorithme anniversaires

Message par parisse » mar. févr. 17, 2015 12:13 pm

C'est le alea(365) qui n'est pas quote, du coup il genere n nombres compris entre 0 et un entier aleatoire plus petit que 365 (d'ou sans doute le facteur 2 observe, puisque cet entier aleatoire a une esperance de moitie de 365).
En fait pour generer n nombres entre 0 et 365-1 il est plus simple de faire randvector(n,365) que de faire randvector(n,'alea(365)'). La seconde forme se justifie si on a une formule plus compliquee.
Ensuite pour tester s'il y a des paires egales, il vaut mieux trier la liste au prealable avec sort puis tester si un nombre est egal au suivant

Code : Tout sélectionner

anni(n):={
  local d,t,k,p;
  d:=sort(ranv(n,365));
  for(k:=0;k<n-1;k++){
    if (d[k]==d[k+1]) return 1;
  }
  retourne 0;
}:;
c'est en O(n*ln(n)) au lieu de O(n^2).
On peut alors faire simul(100) sans problemes.

Denizou
Messages : 61
Inscription : mer. juin 13, 2012 7:23 am

Re: algorithme anniversaires

Message par Denizou » mar. févr. 17, 2015 12:40 pm

parisse a écrit :C'est le alea(365) qui n'est pas quote, du coup il genere n nombres compris entre 0 et un entier aleatoire plus petit que 365 (d'ou sans doute le facteur 2 observe, puisque cet entier aleatoire a une esperance de moitie de 365).
je viens de relire l'aide et je ne comprends pas où se situe le problème. D'ailleurs, on a comme exemple d'utilisation"randvector(3,'rand(3)')" : à quelle simulation cela correspond - il ?
En fait pour generer n nombres entre 0 et 365-1 il est plus simple de faire randvector(n,365) que de faire randvector(n,'alea(365)'). La seconde forme se justifie si on a une formule plus compliquee.
Merci bien : les résultats sont effectivement cohérents
Ensuite pour tester s'il y a des paires egales, il vaut mieux trier la liste au prealable avec sort puis tester si un nombre est egal au suivant

Code : Tout sélectionner

anni(n):={
  local d,t,k,p;
  d:=sort(ranv(n,365));
  for(k:=0;k<n-1;k++){
    if (d[k]==d[k+1]) return 1;
  }
  retourne 0;
}:;
c'est en O(n*ln(n)) au lieu de O(n^2).
On peut alors faire simul(100) sans problemes.
Merci beaucoup

Denizou
Messages : 61
Inscription : mer. juin 13, 2012 7:23 am

Re: algorithme anniversaires

Message par Denizou » mar. févr. 17, 2015 12:52 pm

Je viens de comprendre mon erreur. Merci beaucoup pour votre aide.

Répondre