Paradoxe d'anniversaire :Comment estimer par programmation la probabilité que 3 et N personnes partagent un anniversaire

Question

Il existe de nombreuses ressources sur Internet traitant du célèbre Paradoxe d'anniversaire.Il est clair pour moi comment calculer la probabilité que deux personnes partagent le même anniversaire, c'est-à-dire P(same) = 1 - P(different).Cependant si je me pose une question apparemment plus simple, je décroche :tout d'abord, disons que je génère deux anniversaires aléatoires.Obtenir le même anniversaire, c’est comme lancer une pièce de monnaie.Soit les deux personnes partagent un anniversaire (Têtes), soit elles ne partagent pas d'anniversaire (Queue).Exécutez ceci 500 fois et le résultat final (#Heads/500) sera en quelque sorte proche de 0,5

• Q1) Mais que dois-je y penser si je génère trois anniversaires aléatoires ?Comment puis-je alors estimer la probabilité ?Évidemment, mon analogie avec la pièce de monnaie ne sera pas applicable.

• Q2) Une fois que j'aurai compris ce qui précède, je devrai l'augmenter et générer 30 ou 50 anniversaires.Existe-t-il une technique ou un algorithme recommandé pour isoler les anniversaires identiques d’un grand ensemble ?Dois-je les mettre dans des tableaux et les parcourir en boucle ?

Voici ce dont je pense avoir besoin :

Q1)

r = 25 i.e. each trial run generates 25 birthdays

Trial 1 >
3 duplicates: 0

Trial 2 >
3 duplicates: 0

Trial 3 >
3 duplicates: 2

Trial 4 >
3 duplicates: 1

...

T100 >
3 duplicates: 2

estimated probability of 3 persons sharing a birthday in a room of 25 = (0+0+2+1+...+2)/100

Q2)

• Créez un tableau pour 2 doublons, un tableau pour 3 doublons et un pour plus de 3 doublons
• ajoutez chaque anniversaire généré un par un dans le premier tableau.Mais avant de le faire, parcourez le tableau pour voir s'il y est déjà.Si tel est le cas, ajoutez-le au deuxième tableau, mais avant de le faire, répétez le processus ci-dessus et ainsi de suite.
• Cela ne semble pas être un algorithme très efficace cependant :) des suggestions pour améliorer le Big O ici ?

Answer 1

Créez un tableau d'entiers de longueur 365, initialisé à 0.Générez ensuite N (dans votre cas 25) nombres aléatoires compris entre 1 et 365 et augmentez ce nombre dans le tableau (c.-à-d.jours[random_value]++).Puisque vous n'êtes intéressé que par une collision, juste après avoir augmenté le nombre dans le tableau, vérifiez s'il est supérieur à 2 (si c'est le cas, il y a une deuxième collision, ce qui signifie qu'il y a 3 personnes avec le même anniversaire).Gardez une trace des collisions et exécutez-la autant de fois que vous le souhaitez (1000).

Au final, le rapport collisions/1000 sera la valeur demandée.

et aucune analogie avec le lancer de pièces n’est fausse.

Answer 2

Vérifier ce question similaire et ses réponses sur CrossValidated, mais je pense que cela vaut vraiment la peine de repenser au problème classique de l'anniversaire pour avoir les bases.

À la deuxième partie de votre question :cela dépend de la langue que vous utilisez.Je suggère définitivement d'utiliser R. pour résoudre un problème comme celui-là, car la vérification des anniversaires identiques dans une liste/vecteur/bloc de données peut facilement être effectuée avec un simple unique appel.Pour exécuter une simulation MC aussi simple, R est encore une fois très pratique, vérifiez la deuxième réponse sur le lien ci-dessus.

Answer 3

On dirait que votre première tâche sera de créer une méthode qui générera des anniversaires aléatoires.Pour simplifier les choses, vous pouvez utiliser les nombres 1 à 365 pour désigner des anniversaires uniques.

Stockez cependant de nombreux anniversaires aléatoires (2 dans le premier cas plus tard) dans une ArrayList sous forme de chaînes.Vous souhaiterez utiliser une boucle pour appeler la fonction de nombre aléatoire et stocker la valeur dans votre liste.

Créez ensuite une fonction pour rechercher des doublons dans ArrayList.S'il y a des doublons (peu importe leur nombre), c'est un résultat Face.S'il n'y a pas de correspondance, c'est Face.

Vos probabilités seront très différentes de 50/50 jusqu'à ce que vous atteigniez environ 20.