# The probability that 25 people do not have the same birthday

I figure that it would be something like this

$$\frac{365}{365} \times \frac{364}{365} \times \cdots \times \frac{340}{365}$$

But that is a lot of fractions to enter into a calculator, even so I think this is the right answer but I was wondering if there is a shortcut or something? I have a casio CFX-9850GB.

-
How accurate do you want the answer? –  Aryabhata Jul 14 '11 at 7:54
The book says 43,1%. –  Algific Jul 14 '11 at 8:02
You may (or, may not) be interested to know that the exact answer is 4314778256349470854170763414024795540030075259130696695808 / 10004116148447957520459906484225353834116619892120361328125. –  Chris Taylor Jul 14 '11 at 8:21
And they said quantum electrodynamics gives very precise results! That's nothing compared to elementary biology. –  André Nicolas Jul 14 '11 at 12:45
But I think the assumption of equidistribution of birthdates does not really hold; there is plenty of data to this effect.Specifically, the ref. cites a collection of n=480,040 data points, where the Chi-squared for (Actual # of births for a given day) -$\frac{1}{365}$480,040 failed at a 95% confidence. –  gary Jul 14 '11 at 21:29

Yes, you could write the numerator as $365! / (365 - 25)!$ where $n!$ is the factorial function, and the denominator as $365^{25}$, so your probability is

$$365! / ((365-25)! \times 365^{25})$$

You might try entering this into Wolfram Alpha to get a result.

Also, the expression you entered is incorrect. You have a total of 26 terms in your product, whereas you only want 25. Don't worry, this kind of off-by-one error is common even among experienced mathematicians and computer scientists. I make it all the time!

-
I only count 25. :( How? I just assumed 365-25=340 would be correct. Thanks btw. Perfect. I was thinking about factorial. –  Algific Jul 14 '11 at 8:13
For the same reason that 10...15 has 6 numbers, not 5: 10, 11, 12, 13, 14, 15. You started counting from zero instead of from one. –  Chris Taylor Jul 14 '11 at 8:19
Spot on, thanks again! –  Algific Jul 14 '11 at 8:25
But if counting starts on 0 shouldn't you subtract 24 instead? Or would you just remove the term that is equal to 1? –  Algific Jul 14 '11 at 8:44
On the subtraction issue, consider if you only had one term. Then you would calculate $365-365$ and think that you had 0 terms, which you obviously don't. –  gereeter Jul 14 '11 at 14:06

I think that it is

$$\frac{365}{365}\times \frac{364}{365}\times \cdots \times \frac{341}{365},$$

because $365-341+1=25$.

Call $P(n)$ the probability that $n$ people do not have the same birthday. It is given by $$\begin{eqnarray*} P(n) &=&\frac{365}{365}\times \frac{364}{365}\times \cdots \times \frac{% 365-n+1}{365} \\ &=&\frac{\prod_{k=2}^{n}\left( 366-k\right) }{365^{n-1}}=\frac{364!}{% 365^{n-1}\left( 365-n\right) !} \\ &=&\frac{\Gamma (365)}{365^{n-1}\Gamma (366-n)}. \end{eqnarray*}$$

Notation: The $\prod$ symbol stands for a product

$$\prod_{k=2}^{25}\left( 336-k\right) =\left( 336-2\right) \left( 336-3\right) \left( 336-4\right)\times \cdots \times\left( 336-25\right) .$$

and $\Gamma (x)$ is the gamma function with the property $\Gamma (n+1)=n!$.

For $n=25$, we have $$\begin{eqnarray*} P(25) &=&\frac{\prod_{k=2}^{25}\left( 366-k\right) }{365^{25-1}}=\frac{364!}{% 365^{25-1}\left( 365-25\right) !}\approx 0.431\,3 \\ &=&\frac{\Gamma (365)}{365^{25-1}\Gamma (366-25)}\approx 0.431\,3 \end{eqnarray*}$$

Here is a plot of $1-P(x)$ (número de pessoas = number of people $=x$)

-
I started writting this answer before Chris Taylor had posted his answer. I used this post of mine problemasteoremas.wordpress.com/2009/07/15/… –  Américo Tavares Jul 14 '11 at 8:55
What does the II symbol and the cut of T stand for? –  Algific Jul 14 '11 at 9:07
It stands for product. It works in the same manner as the summation notation : you "multiply" things from $k = 2$ up to $k = n$ and write $\prod_{k=2}^n x_k$. –  Patrick Da Silva Jul 14 '11 at 9:10
nevermind got it.. its to cancel out all the remaining terms from the numerator.. –  Tyler Hilton Jul 14 '11 at 15:26
Got it, beautiful solution by the way. –  Tyler Hilton Jul 15 '11 at 20:19

I seem to remember a surprisingly good approximation of your probability $P_{25}$ is obtained using $1-x\le\exp(-x)$ for $x=k/365$ from $k=1$ to $k=25$. Hence $$P_{25}<\exp(-x_1-\cdots-x_{25})=\exp(-25\cdot26/(2\cdot365))<41.05\%.$$ Likewise, if one needs to go from $k=1$ to $k=24$, one gets $$P_{24}<\exp(-24\cdot25/(2\cdot365))<43.96\%.$$ One can even get not-so-crude lower bounds starting from the fact that on a small interval $(0,z)$, the derivative of $u:x\mapsto1/(1-x)$ is $u'(x)=1/(1-x)^2$ hence $u'\le cu$ with $c=1/(1-z)$, which yields $u(x)\le u(0)\exp(cx)$, hence $1-x\ge \exp(-cx)$. One gets $$P_{24}>\exp(-24\cdot25/(2\cdot365\cdot(1-x_{24})))=\exp(-24\cdot25/(2\cdot341))>41.48\%,$$ and $$P_{25}>\exp(-25\cdot26/(2\cdot340))>38.44\%.$$ To sum it up, for every $1\le n<N$, $$\exp\left(-\frac{n(n+1)}{2(N-n)}\right)<\prod_{k=1}^n\left(1-\frac{k}N\right)<\exp\left(-\frac{n(n+1)}{2N}\right).$$ In the Birthday paradox context ($N=365$), the funny thing is that the upper bound for $n=22$ is $<50\%$ and the lower bound for $n=21$ is $>50\%$ hence these crude approximations are enough to be sure that $P_{22}<50\%<P_{21}$ and that the so-called magic number is $22+1=23$.

-
I got $P\approx 0.4313$. –  Américo Tavares Jul 14 '11 at 8:51
@Américo: Which one, $P_{24}$ or $P_{25}$? –  Did Jul 14 '11 at 9:02
$P_25$ (I called it $P(25)$). So that's right $0.43213>0.3844$. –  Américo Tavares Jul 14 '11 at 9:07
@Américo: Your $P(25)$ is my $P_{24}$ so the relevant inqualities are $41.48\% <P_{24}<43.96\%$, which are compatible with your $P(25)=43.13\%$. We happy. –  Did Jul 14 '11 at 9:33
Thanks! +1 for your higher level answer. –  Américo Tavares Jul 14 '11 at 9:36

That's almost the right probability -- there should be 25 factors, so you don't need the $340/365$ at the end. The last factor is $341/365$. You're right that it's going to be quite a bit of work to compute it exactly. And what's really interesting is the numerical value -- is it less than one-half? Less than ten percent? There are lots of approximate methods for figuring out answers to problems like this, and I'll outline one here.

You can rewrite the probability you're looking for in terms of factorials as

$$P = {365! \over 340! 365^{25}}$$

and this is useful because there is a very useful approximation for $n!$, called Stirling's formula:

$$n! \approx \sqrt{2 \pi n} (n/e)^n$$

Now, if you were to plug in $340$ or $365$ to Stirling's formula you would get two very large numbers, which a standard calculator cannot handle; but we know $P$ should be reasonably sized. The trick here is to take logarithms. Stirling's formula can be rewritten as

$$\log n! \approx {1 \over 2} \log {2 \pi} + \left( n + {1 \over 2} \right) \log n - n$$

and the logarithm of your original probability is

$$\log P = \log 365! - \log 340! - 25 \log 365.$$

From Stirling's formula $\log 365! \approx 1792.331$ and $\log 340! \approx 1645.675$; this gives

$$\log P = 1792.331 - 1645.675 - 147.497 = -0.841$$

and so $P \approx e^{-0.841} = 0.432$.

(You might worry if there's an error in Stirling's approximation. It turns out that there is, and that the estimated value of $\log n!$ will always be lower than its true value by about $1/(12n)$. For example $\log 8! = 10.6046$ but Stirling gives ${1 \over 2} \log (2\pi) + 8.5 \log 8 - 8 = 10.5942$; these differ by $0.0104$ or about $1/96$. But the errors in using Stirling to approximate $\log 365!$ and $\log 340!$ are very small and in the same direction; they nearly cancel out.)

-

Nope, no shortcut. The first is 1, and all denominators are the same (so don't keep dividing by 365). And in the grand scheme of things, be thankful that this number of calculations is relatively small. It amounts to only 2 dozen operations, you know?

Keep us posted on your result. This is known as the "Birthday Paradox." And (thanks to Chris Taylor for giving me the exact number) the 'magic number' is 23, meaning that with more than 23 people this becomes (without ruining the question) surprisingly likely.

-
Actually, to prevent overflow, it would make more sense to divide by 365 at each step... –  Zhen Lin Jul 14 '11 at 7:56
I didn't mean to do them all at once, but instead to do them at say, 3 or 4 at a time. –  mixedmath Jul 14 '11 at 7:57
Fwiw the 'magic number' is 23. –  Chris Taylor Jul 14 '11 at 7:57
Ah! Thank you - I'm glad you remembered. Even lower than I had thought, and I knew the paradox! I'm suddenly in grade school again, stunned at little things like multiplication. –  mixedmath Jul 14 '11 at 8:01
3 6 5 OPTN F6 ► F3 PROB F2 nPr 2 5 EXE

÷ 3 6 5 ^ 2 5 EXE