user
|  |
| --- |
| 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 group before we can expect a *better than 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 than 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...

Suggestions for improvement

* Estimating the error in the estimate to help ensure the estimate is accurate to 4 decimal places.
* Converging to the 

  n
  {\displaystyle {\displaystyle n}}
  th solution using a root finding method, as opposed to using an extensive search.
* Kudos (κῦδος) for finding the solution by proof (in a programming language) rather than by construction and simulation.

See also

* Wolfram entry:   Birthday Problem
assistant
(formerly Perl 6)
Gives correct answers, but more of a proof-of-concept at this point, even with max-trials at 250K it is too slow to be practical.

```
sub simulation ($c) {
    my $max-trials = 250_000;
    my $min-trials =   5_000;
    my $n = floor 47 * ($c-1.5)**1.5; # OEIS/A050256: 16 86 185 307
    my $N = min $max-trials, max $min-trials, 1000 * sqrt $n;

    loop {
        my $p = $N R/ elems grep { .elems > 0 }, ((grep { $_>=$c }, values bag (^365).roll($n)) xx $N);
        return($n, $p) if $p > 0.5;
        $N = min $max-trials, max $min-trials, floor 1000/(0.5-$p);
        $n++;
   }
}

printf "$_ people in a group of %s share a common birthday. (%.3f)\n", simulation($_) for 2..5;

```

Output:

```
2 people in a group of 23 share a common birthday. (0.506)
3 people in a group of 88 share a common birthday. (0.511)
4 people in a group of 187 share a common birthday. (0.500)
5 people in a group of 313 share a common birthday. (0.507)
```