4
$\begingroup$

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.

$\endgroup$
5
  • 1
    $\begingroup$ How accurate do you want the answer? $\endgroup$
    – Aryabhata
    Commented Jul 14, 2011 at 7:54
  • $\begingroup$ The book says 43,1%. $\endgroup$
    – Algific
    Commented Jul 14, 2011 at 8:02
  • 3
    $\begingroup$ You may (or, may not) be interested to know that the exact answer is 4314778256349470854170763414024795540030075259130696695808 / 10004116148447957520459906484225353834116619892120361328125. $\endgroup$ Commented Jul 14, 2011 at 8:21
  • $\begingroup$ And they said quantum electrodynamics gives very precise results! That's nothing compared to elementary biology. $\endgroup$ Commented Jul 14, 2011 at 12:45
  • 1
    $\begingroup$ 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. $\endgroup$
    – gary
    Commented Jul 14, 2011 at 21:29

6 Answers 6

7
$\begingroup$

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$)

enter image description here

$\endgroup$
17
  • $\begingroup$ I started writting this answer before Chris Taylor had posted his answer. I used this post of mine problemasteoremas.wordpress.com/2009/07/15/… $\endgroup$ Commented Jul 14, 2011 at 8:55
  • 2
    $\begingroup$ What does the II symbol and the cut of T stand for? $\endgroup$
    – Algific
    Commented Jul 14, 2011 at 9:07
  • $\begingroup$ 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$. $\endgroup$ Commented Jul 14, 2011 at 9:10
  • 1
    $\begingroup$ nevermind got it.. its to cancel out all the remaining terms from the numerator.. $\endgroup$ Commented Jul 14, 2011 at 15:26
  • 1
    $\begingroup$ Got it, beautiful solution by the way. $\endgroup$ Commented Jul 15, 2011 at 20:19
6
$\begingroup$

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!

$\endgroup$
5
  • $\begingroup$ I only count 25. :( How? I just assumed 365-25=340 would be correct. Thanks btw. Perfect. I was thinking about factorial. $\endgroup$
    – Algific
    Commented Jul 14, 2011 at 8:13
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Jul 14, 2011 at 8:19
  • $\begingroup$ Spot on, thanks again! $\endgroup$
    – Algific
    Commented Jul 14, 2011 at 8:25
  • $\begingroup$ But if counting starts on 0 shouldn't you subtract 24 instead? Or would you just remove the term that is equal to 1? $\endgroup$
    – Algific
    Commented Jul 14, 2011 at 8:44
  • $\begingroup$ 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. $\endgroup$
    – gereeter
    Commented Jul 14, 2011 at 14:06
4
$\begingroup$

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$.

$\endgroup$
5
  • $\begingroup$ I got $P\approx 0.4313$. $\endgroup$ Commented Jul 14, 2011 at 8:51
  • $\begingroup$ @Américo: Which one, $P_{24}$ or $P_{25}$? $\endgroup$
    – Did
    Commented Jul 14, 2011 at 9:02
  • $\begingroup$ $P_25$ (I called it $P(25)$). So that's right $0.43213>0.3844$. $\endgroup$ Commented Jul 14, 2011 at 9:07
  • $\begingroup$ @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. $\endgroup$
    – Did
    Commented Jul 14, 2011 at 9:33
  • $\begingroup$ Thanks! +1 for your higher level answer. $\endgroup$ Commented Jul 14, 2011 at 9:36
1
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ Actually, to prevent overflow, it would make more sense to divide by 365 at each step... $\endgroup$
    – Zhen Lin
    Commented Jul 14, 2011 at 7:56
  • $\begingroup$ I didn't mean to do them all at once, but instead to do them at say, 3 or 4 at a time. $\endgroup$
    – davidlowryduda
    Commented Jul 14, 2011 at 7:57
  • 2
    $\begingroup$ Fwiw the 'magic number' is 23. $\endgroup$ Commented Jul 14, 2011 at 7:57
  • $\begingroup$ 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. $\endgroup$
    – davidlowryduda
    Commented Jul 14, 2011 at 8:01
1
$\begingroup$

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.)

$\endgroup$
1
$\begingroup$

Yes, just press

3 6 5 OPTN F6 ► F3 PROB F2 nPr 2 5 EXE

to calculate the numerator and then divide by the denominator by pressing

÷ 3 6 5 ^ 2 5 EXE
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .