Birthday problem

This page uses content from Wikipedia. The current wikipedia article is at Birthday Problem. The original RosettaCode article was extracted from the wikipedia article № 296054030 of 21:44, 12 June 2009 . The list of authors can be seen in the page history. As with Rosetta Code, the pre 5 June 2009 text of Wikipedia is available under the GNU FDL. (See links for details on variance)

In probability theory, the birthday problem, or birthday paradox This is not a paradox in the sense of leading to a logical contradiction, but is called a paradox because the mathematical truth contradicts naïve intuition: most people estimate that the chance is much lower than 50%. pertains to the probability that in a set of randomly chosen people some pair of them will have the same birthday. In a group of at least 23 randomly chosen people, there is more than 50% probability that some pair of them will both have been born on the same day. For 57 or more people, the probability is more than 99%, and it reaches 100% when the number of people reaches 366 (by the pigeon hole principle, ignoring leap years). The mathematics behind this problem leads to a well-known cryptographic attack called the birthday attack.

Task:

Using simulation, estimate the number of independent people required in a groups before we can expect a better then even chance that at least 2 independent people in a group share a common birthday. Furthermore: Simulate and thus estimate when we can expect a better then even chance that at least 3, 4 & 5 independent people of the group share a common birthday. For simplicity assume that all of the people are alive...

Kudos (κῦδος) for estimating the error in the estimate to help ensure the estimate is accurate to 4 decimal places.

See also:

Birthday Problem

ALGOL 68

Works with: ALGOL 68 version Revision 1

Works with: ALGOL 68G version Any - tested with release algol68g-2.6.

File: Birthday_problem.a68<lang algol68>#!/usr/bin/a68g --script #

-*- coding: utf-8 -*- #

REAL desired probability := 0.5; # 50% #

REAL upb year = 365 + 1/4 - 3/400, INT upb sample size = 10000,

   upb repeat = 5 ;

INT required repeat := 2;

FORMAT var int fmt = $g": "g(-0)"; "$;

printf((

 var int fmt,
 "upb year",upb year,
 "upb repeat",upb repeat,
 "upb sample size",upb sample size,
 $l$

));

FOR group size FROM required repeat WHILE required repeat <= upb repeat DO

 INT sample with no required repeat := 0;
 TO upb sample size DO
 # generate sample #
   [group size]INT sample;
   FOR i TO UPB sample DO sample[i] := ENTIER(random * 365) + 1 OD;
   FOR birthday i TO UPB sample DO
     INT birthday = sample[birthday i];
     INT number of celebrants := 1;
     FOR birthday j FROM birthday i + 1 TO UPB sample DO
       IF birthday = sample[birthday j] THEN
         number of celebrants +:= 1;
         IF number of celebrants = required repeat THEN
           found required repeat
         FI
       FI
     OD
   OD  # days in year #;
   sample with no required repeat +:= 1;
   found required repeat: SKIP
 OD # sample size #;
 REAL portion of years with required repeat birthdays = 
   (upb sample size - sample with no required repeat) / upb sample size;
 print(".");
 IF portion of years with required repeat birthdays > desired probability THEN
   printf((
     $l$,
     var int fmt,
     "required repeat",required repeat,
     "group size",group size,
     # "sample with no required repeat",sample with no required repeat, #
     $g": "g(-0,2)"%; "$,
     "%age of years with required repeat birthdays",portion of years with required repeat birthdays*100,
     $l$
   ));
   required repeat +:= 1
 FI

OD # group size #</lang>Output:

upb year: 365; upb repeat: 5; upb sample size: 10000; 
......................
required repeat: 2; group size: 23; %age of years with required repeat birthdays: 51.69%; 
................................................................
required repeat: 3; group size: 87; %age of years with required repeat birthdays: 50.37%; 
...................................................................................................
required repeat: 4; group size: 186; %age of years with required repeat birthdays: 50.70%; 
...............................................................................................................................
required repeat: 5; group size: 313; %age of years with required repeat birthdays: 50.92%;