Etendre le paradoxe de l'anniversaire à plus de 2 personnes

29

Dans le paradoxe d'anniversaire traditionnel, la question est "quelles sont les chances que deux personnes ou plus dans un groupe de personnes partagent un anniversaire". Je suis coincé sur un problème qui en est une extension.n

Au lieu de connaître la probabilité que deux personnes partagent un anniversaire, je dois étendre la question pour savoir quelle est la probabilité que ou plusieurs personnes partagent un anniversaire. Avec vous pouvez le faire en calculant la probabilité que deux personnes ne partagent pas un anniversaire et soustraient cela de , mais je ne pense pas pouvoir étendre cette logique à un plus grand nombre de .xx=21x

Pour compliquer davantage cela, j'ai également besoin d'une solution qui fonctionnera pour de très grands nombres pour (millions) et (milliers).nx

Simon Andrews
la source
1
Je suppose que c'est un problème de bioinformatique
csgillespie
3
Il s'agit en fait d'un problème de bioinformatique, mais comme cela se résume au même concept que le paradoxe d'anniversaire, j'ai pensé que je garderais les détails non pertinents!
Simon Andrews
4
Normalement, je serais d'accord avec vous, mais dans ce cas, les détails pourraient être importants car il pourrait déjà y avoir un ensemble de bioconducteurs qui fait ce que vous demandez.
csgillespie
Si vous voulez vraiment savoir, c'est un problème de recherche de modèle où j'essaie d'estimer avec précision la probabilité d'un niveau donné d'enrichissement d'une sous-séquence dans un ensemble de séquences plus grandes. J'ai donc un ensemble de sous-séquences avec des comptages associés et je sais combien de sous-séquences j'ai observées et combien de séquences théoriquement observables sont disponibles. Si j'ai vu une séquence particulière 10 fois sur 10 000 observations, j'ai besoin de savoir dans quelle mesure cela aurait pu se produire par hasard.
Simon Andrews
Près de huit ans plus tard, j'ai publié une réponse à ce problème sur stats.stackexchange.com/questions/333471 . Cependant, le code ne fonctionne pas pour les grands , car cela prend du temps quadratique en . n,n
whuber

Réponses:

17

C'est un problème de comptage: il y a affectations possibles de anniversaires à personnes. Parmi ceux-ci, soit le nombre d'affectations pour lesquelles aucun anniversaire n'est partagé par plus de personnes mais au moins un anniversaire est réellement partagé par personnes. La probabilité que nous recherchons peut être trouvée en additionnant les pour les valeurs appropriées de et en multipliant le résultat par . b n q ( k ; n , b ) k k q ( k ; n , b ) k b - nbnbnq(k;n,b)kkq(k;n,b)kbn

Ces comptes peuvent être trouvés exactement pour des valeurs de inférieures à plusieurs centaines. Cependant, ils ne suivront aucune formule simple: nous devons considérer les modèles de manière dont les anniversaires peuvent être attribués . Je vais illustrer cela au lieu de fournir une démonstration générale. Soit (c'est la plus petite situation intéressante). Les possibilités sont:n = 4nn=4

  • Chaque personne a un anniversaire unique; le code est {4}.
  • Exactement deux personnes partagent un anniversaire; le code est {2,1}.
  • Deux personnes ont un anniversaire et les deux autres en ont un autre; le code est {0,2}.
  • Trois personnes partagent un anniversaire; le code est {1,0,1}.
  • Quatre personnes partagent un anniversaire; le code est {0,0,0,1}.

Généralement, le code est un tuple de décomptes dont l' élément stipule combien de dates de naissance distinctes sont partagées par exactement personnes. Ainsi, en particulier,k ème k{a[1],a[2],}kthk

1a[1]+2a[2]+...+ka[k]+=n.

Notez, même dans ce cas simple, qu'il existe deux façons d'atteindre le maximum de deux personnes par anniversaire: une avec le code et une autre avec le code .{ 2 , 1 }{0,2}{2,1}

Nous pouvons compter directement le nombre d'affectations d'anniversaire possibles correspondant à un code donné. Ce nombre est le produit de trois termes. L'un est un coefficient multinomial; il compte le nombre de façons de partitionner personnes en groupes de , groupes de , etc. Parce que la séquence de groupes n'a pas d'importance, nous devons diviser ce coefficient multinomial par ; sa réciproque est le deuxième terme. Enfin, alignez les groupes et attribuez-leur chacun un anniversaire: il y a candidats pour le premier groupe,a [ 1 ] 1 a [ 2 ] 2 a [ 1 ] ! un [ 2 ] ! b b - 1 b ( a [ 1 ] + a [ 2 ] + ) b ( m ) b ( b - 1 ) ( b - m + 1 )na[1]1a[2]2a[1]!a[2]!bb1pour le second, et ainsi de suite. Ces valeurs doivent être multipliées ensemble, formant le troisième terme. Il est égal au "produit factoriel" où signifie .b(a[1]+a[2]+)b(m)b(b1)(bm+1)

Il existe une récursivité évidente et assez simple reliant le nombre pour un modèle au nombre pour le modèle . Cela permet un calcul rapide des comptes pour des valeurs modestes de . Plus précisément, représente dates de naissance partagées par exactement personnes chacune. Une fois que ces groupes de personnes ont été tirés des personnes, ce qui peut être fait de façons distinctes (disons), il reste à compter le nombre de façons de réaliser le modèle{ a [ 1 ] , , a [ k - 1 ] } n a [ k ] a [ k ] k a [ k ] k n x { a [ 1 ] , ... , un [ k - 1 ] } x{a[1],,a[k]}{a[1],,a[k1]}na[k]a[k]ka[k]knx{a[1],,a[k1]}parmi les personnes restantes. La multiplication par donne la récursivité.x

Je doute qu'il existe une formule de forme fermée pour , qui est obtenue en additionnant les comptes pour toutes les partitions de dont le terme maximum est égal à . Permettez-moi de vous donner quelques exemples:q(k;n,b)nk

Avec (cinq anniversaires possibles) et (quatre personnes), on obtientb=5n=4

q(1)=q(1;4,5)=120q(2)=360+60=420q(3)=80q(4)=5.

D'où, par exemple, la chance que trois personnes ou plus sur quatre partagent le même "anniversaire" (sur dates possibles) égale .5(80+5)/625=0.136

Comme autre exemple, prenons et . Voici les valeurs de pour le plus petit (à six figues sig uniquement):b=365n=23q(k;23,365)k

k=1:0.49270k=2:0.494592k=3:0.0125308k=4:0.000172844k=5:1.80449E6k=6:1.48722E8k=7:9.92255E11k=8:5.45195E13.

En utilisant cette technique, nous pouvons facilement calculer qu'il y a environ 50% de chances (au moins) d'une collision anniversaire à trois voies parmi 87 personnes, une chance de 50% d'une collision à quatre voies parmi 187 personnes et une probabilité de 50% de une collision à cinq voies entre 310 personnes. Ce dernier calcul commence à prendre quelques secondes (dans Mathematica, de toute façon) car le nombre de partitions à considérer commence à devenir important. Pour sensiblement plus grand, nous avons besoin d'une approximation.n

Une approximation est obtenue au moyen de la distribution de Poisson avec l'espérance , car nous pouvons voir une affectation d'anniversaire comme découlant de variables de Poisson indépendantes (mais pas tout à fait) chacune avec une espérance : la variable pour tout anniversaire possible donné décrit combien de personnes ont cet anniversaire. La distribution du maximum est donc approximativement où est le CDF de Poisson. Ce n'est pas un argument rigoureux, alors faisons un petit test. L'approximation pour , donnen/bbn/bnF(k)bFn=23b=365

k=1:0.498783k=2:0.496803k=3:0.014187k=4:0.000225115.

En comparant avec ce qui précède, vous pouvez voir que les probabilités relatives peuvent être médiocres quand elles sont petites, mais les probabilités absolues sont raisonnablement bien approchées à environ 0,5%. Les tests avec une large gamme de et suggèrent que l'approximation concerne généralement ce bien.nb

Pour conclure, considérons la question initiale: prendre (le nombre d'observations) et (le nombre de "structures" possibles). La distribution approximative du nombre maximum de "anniversaires partagés" estn=10,000b=1000000

k=1:0k=2:0.8475+k=3:0.1520+k=4:0.0004+k>4:<1E6.

(Il s'agit d'un calcul rapide.) Il est clair qu'observer une structure 10 fois sur 10 000 serait très significatif. Parce que et sont tous deux grands, je m'attends à ce que l'approximation fonctionne assez bien ici.nb

Par ailleurs, comme Shane l'a laissé entendre, les simulations peuvent fournir des vérifications utiles. Une simulation Mathematica est créée avec une fonction comme

simulate[n_, b_] := Max[Last[Transpose[Tally[RandomInteger[{0, b - 1}, n]]]]];

qui est ensuite itéré et résumé, comme dans cet exemple qui exécute 10 000 itérations du cas , :n=10000b=1000000

Tally[Table[simulate[10000, 1000000], {n, 1, 10000}]] // TableForm

Sa sortie est

2 8503

3 1493

4 4

Ces fréquences correspondent étroitement à celles prédites par l'approximation de Poisson.

whuber
la source
Quelle réponse fantastique, merci beaucoup @whuber.
JKnight
"Il y a une récursivité évidente et assez simple" - A savoir?
Kodiologist
1
@ Kodiologist J'ai inséré une brève description de l'idée.
whuber
+1 mais où dans la question d'origine avez-vous vu que n = 10000 et b = 1 mln? L'OP semble demander à propos de n = 1 mln et k = 10000, avec b non spécifié (vraisemblablement b = 365). Ce n'est pas important à ce stade :)
amibe dit Réintégrer Monica
1
@amoeba Après tout ce temps (six ans, 1600 réponses et lire attentivement des dizaines de milliers de messages), je ne me souviens pas, mais j'ai probablement mal interprété la dernière ligne. Pour ma défense, notez que si nous le lisons littéralement, la réponse est immédiate (lors de l'application d'une version du principe du pigeonnier): il est certain que parmi = millions de personnes, il y aura au moins un anniversaire partagé entre au moins = des milliers d'entre eux! nx
whuber
2

Il est toujours possible de résoudre ce problème avec une solution monte-carlo, bien que ce soit loin d'être le plus efficace. Voici un exemple simple du problème de 2 personnes dans R (à partir d' une présentation que j'ai faite l'année dernière ; j'ai utilisé cela comme un exemple de code inefficace), qui pourrait être facilement ajusté pour représenter plus de 2:

birthday.paradox <- function(n.people, n.trials) {
    matches <- 0
    for (trial in 1:n.trials) {
        birthdays <- cbind(as.matrix(1:365), rep(0, 365))
        for (person in 1:n.people) {
            day <- sample(1:365, 1, replace = TRUE)
            if (birthdays[birthdays[, 1] == day, 2] == 1) {
                matches <- matches + 1
                break
            }
            birthdays[birthdays[, 1] == day, 2] <- 1
        }
        birthdays <- NULL
    }
    print(paste("Probability of birthday matches = ", matches/n.trials))
}
Shane
la source
Je ne sais pas si la solution à plusieurs types fonctionnera ici.
Je pense que la généralisation ne fonctionne toujours que pour 2 personnes ou plus partageant un anniversaire - juste que vous pouvez avoir différentes sous-classes de personnes.
Simon Andrews
1

Il s'agit d'une tentative de solution générale. Il peut y avoir des erreurs, alors utilisez-les avec prudence!

Première notation:

P(x,n) soit la probabilité que ou plusieurs personnes partagent un anniversaire entre personnes,xn

P(y|n) est la probabilité que exactement personnes partagent un anniversaire entre personnes.yn

Remarques:

  1. L'abus de notation comme Est utilisé de deux manières différentes.P(.)

  2. Par définition, ne peut pas prendre la valeur 1 car cela n'a aucun sens et = 0 peut être interprété comme signifiant que personne ne partage un anniversaire commun.yy

La probabilité requise est alors donnée par:

P(x,n)=1P(0|n)P(2|n)P(3|n)....P(x1|n)

À présent,

P(y|n)=(ny)(365365)y k=1k=ny(1k365)

Voici la logique: vous avez besoin de la probabilité qu'exactement personnes partagent un anniversaire.y

Étape 1: vous pouvez sélectionner personnes de façons.y(ny)

Étape 2: Puisqu'ils partagent un anniversaire, il peut s'agir de l'un des 365 jours d'une année. Donc, nous avons essentiellement 365 choix qui nous donne .(365365)y

Étape 3: Les personnes restantes ne devraient pas partager d'anniversaire avec les premières personnes ou entre elles. Ce raisonnement nous donne .nyyk=1k=ny(1k365)

Vous pouvez vérifier que pour = 2, ce qui précède se réduit à la solution de paradoxe d'anniversaire standard.x


la source
Cette solution souffrira-t-elle de la malédiction de la dimensionnalité? Si au lieu de n = 365, n = 10 ^ 6, cette solution est-elle toujours réalisable?
csgillespie
Certaines approximations peuvent devoir être utilisées pour traiter des dimensions élevées. Utilisez peut-être l'approximation de Stirling pour les factorielles du coefficient binomial. Pour gérer les conditions du produit, vous pouvez prendre des journaux et calculer les sommes au lieu des produits, puis prendre l'anti-journal de la somme.
Il existe également plusieurs autres formes d'approximations possibles en utilisant par exemple l'expansion de la série Taylor pour la fonction exponentielle. Voir la page wiki pour ces approximations: en.wikipedia.org/wiki/Birthday_problem#Approximations
Supposons que y = 2, n = 4 et qu'il n'y ait que deux anniversaires. Votre formule, adaptée en remplaçant 365 par 2, semble indiquer que la probabilité qu'exactement 2 personnes partagent un anniversaire est Comb (4,2) * (2/2) ^ 2 * (1-1 / 2) * (1-2 / 2) = 0. (En fait, il est facile de voir - par énumération par force brute si vous le souhaitez - que les probabilités que 2, 3 ou 4 personnes partagent un "anniversaire" sont 6/16, 8/16, et 2/16, respectivement.) En effet, chaque fois que ny> = 365, votre formule donne 0, tandis que lorsque n devient grand et y est fixe, la probabilité devrait augmenter jusqu'à un maximum non nul avant que n atteigne 365 * y, puis diminuer, mais jamais à 0.
whuber
Pourquoi vous remplacez 365 par ? La probabilité que 2 personnes partagent un anniversaire est calculée comme suit: 1 - Prob (ils ont un anniversaire unique). Prob (qu'ils ont un anniversaire unique) = (364/365). La logique est la suivante: choisissez une personne. Cette personne peut avoir n'importe quel jour des 365 jours comme anniversaire. La deuxième personne ne peut alors fêter son anniversaire que l'un des 364 jours restants. Ainsi, la probabilité qu'ils aient un anniversaire unique est 364/365. Je ne sais pas comment vous calculez 6/16. n