algorithme anniversaires
Modérateur : xcasadmin
algorithme anniversaires
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
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
Re: algorithme anniversaires
Il faudrait le source des fonctions pour essayer de comprendre.
Re: algorithme anniversaires
oui, j'ai oublié de publier les algorithmes !parisse a écrit :Il faudrait le source des fonctions pour essayer de comprendre.
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;
}:;
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
}:;
http://megamaths.free.fr/pdf/algorithme.pdf
Re: algorithme anniversaires
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
c'est en O(n*ln(n)) au lieu de O(n^2).
On peut alors faire simul(100) sans problemes.
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;
}:;
On peut alors faire simul(100) sans problemes.
Re: algorithme anniversaires
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 ?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).
Merci bien : les résultats sont effectivement cohérentsEn 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 beaucoupEnsuite 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 suivantc'est en O(n*ln(n)) au lieu de O(n^2).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; }:;
On peut alors faire simul(100) sans problemes.
Re: algorithme anniversaires
Je viens de comprendre mon erreur. Merci beaucoup pour votre aide.