PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
sections
Encyclopædia
Papers
Books
Expositions

meta
Requests (200)
Orphanage
Unclass'd
Unproven (511)
Corrections (9)
Classification

talkback
Polls
Forums
Feedback
Bug Reports

downloads
Snapshots
PM Book

information
News
Docs
Wiki
ChangeLog
TODO List
Legalese
About
Owner confidence rating: High Entry average rating: No information on entry rating
birthday problem (Definition)

The birthday problem is: What is the probability of two or more people out of a group of $ n$ do have the same birthday?

Solution. Let $ A$ be the event two or more people out of a group of $ n$ to have the same birthday. It is easy to find first the complement of $ A$, $ A^c$, which is that no two people out of a group of $ n$ will have matching birthdays out of $ 365$ (number of days of one year) equally possible birthdays. We start with an arbitrary person's birthday. So the second person's birthday in order to be different from the first one gives us the probability, $ 1-\frac{1}{365}$. Consecutively, the third person's birthday is different from the first two and we have $ (1-\frac{1}{365})(1-\frac{2}{365})$. Finally for the the $ n$th person's birthday we get the probability

$ \displaystyle P[A^c]$ $ \displaystyle =\left(1-\frac{1}{365}\right)\left(1-\frac{2}{365}\right)\dots\left(1-\frac{n-1}{365}\right)$
  $ \displaystyle =\frac{(365-1)}{365}\frac{(365-2)}{365}\dots\frac{(365-(n-1))}{365}$
  $ \displaystyle =\frac{(365-1)}{365}\dots \frac{(365-(n-1))}{365^n}$
  $ \displaystyle =\frac{365!}{(365-n)!365^n}$
  $ \displaystyle ={365\choose n}\frac{n!}{365^n}$
By the last expression of the estimated probability we can see that there exists another easier approach to find the probability which is the following:
  1. We set the possible ways for $ 1\dots n$ birthdays, $ 365^n$ as the denominator.
  2. Using the binomial coefficient $ {365\choose n}$, which represents the number of ways of picking $ n$ unordered birthdays from $ 365$ days multiplied by the factorial $ n!$ used for the number of orders, in that way we determine the numerator.
Therefore we have
$\displaystyle P[A^c]={365\choose n}\frac{n!}{365^n}$
whence
$\displaystyle P[A]=1-P[A^c]=1-{365\choose n}\frac{n!}{365^n}.$

The table below shows the probability $ P[A]$ for some values of $ n$

$ n$ $ P[A]$
$ 10$ $ 0,11695$
$ 20$ $ 0,41144$
$ 23$ $ 0,50730$
$ 30$ $ 0,70632$
$ 40$ $ 0,89123$
$ 50$ $ 0,97037$



"birthday problem" is owned by PrimeFan. [ full author list (2) | owner history (7) ]
(view preamble)

View style:

Other names:  birthday paradox

Attachments:
approximating the birthday problem (Derivation) by Algeboy
Log in to rate this entry.
(view current ratings)

Cross-references: numerator, factorial, represents, binomial coefficient, denominator, expression, order, number, matching, complement, group, event
There are 2 references to this entry.

This is version 13 of birthday problem, born on 2006-08-11, modified 2007-11-18.
Object id is 8242, canonical name is BirthdayProblem.
Accessed 6537 times total.

Classification:
AMS MSC: 60-00 (Probability theory and stochastic processes :: General reference works )
 05A10 (Combinatorics :: Enumerative combinatorics :: Factorials, binomial coefficients, combinatorial functions)
 60C05 (Probability theory and stochastic processes :: Combinatorial probability)
Pending Errata and Addenda
None.
[ View all 10 ]
Discussion
Style: Expand: Order:
forum policy
How many needed by pahio on 2006-08-12 05:51:23
How many people are needed in a group for that it were more probable that at least two have the same birthday than that all have distinct birthdays?
Jussi
[ reply | up ]
Interact
post | correct | update request | add derivation | add example | add (any)