Birthday problem: Difference between revisions
m ('''See also:''' * {{Wolfram|Birthday|Problem}}) |
|||
Line 6: | Line 6: | ||
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... |
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:''' |
'''See also:''' |
||
* {{Wolfram|Birthday|Problem}} |
* {{Wolfram|Birthday|Problem}} |
||
=={{header|ALGOL 68}}== |
|||
{{works with|ALGOL 68|Revision 1}} |
|||
{{works with|ALGOL 68G|Any - tested with release [http://sourceforge.net/projects/algol68/files/algol68g/algol68g-2.6 algol68g-2.6].}} |
|||
{{wont work with|ELLA ALGOL 68|Any (with appropriate job cards) - tested with release [http://sourceforge.net/projects/algol68/files/algol68toc/algol68toc-1.8.8d/algol68toc-1.8-8d.fc9.i386.rpm/download 1.8-8d] - due to extensive use of '''format'''[ted] ''transput''.}} |
|||
'''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:''' |
|||
<pre> |
|||
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%; |
|||
</pre> |
Revision as of 06:38, 4 June 2013
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:
ALGOL 68
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%;