PDA

View Full Version : Unusual birthday puzzle


pzhon
09-02-2004, 04:53 AM
This was posted on usenet a few years ago. Which of the following is more likely?

A) 365 random people have 365 different birthdays.
B) 365^2 random people don't have all 365 birthadys.

The probabilities are close. Ignore February 29th.

random
09-02-2004, 06:50 AM
Post deleted by random

Duke
09-02-2004, 06:59 AM
--deleted since what was once a question will now look like an unwarranted attack--

random
09-02-2004, 07:03 AM
aradsfa;lsk i'm retarded, 6am, going to sleep

FrankLu99
09-02-2004, 09:32 PM
[ QUOTE ]
This was posted on usenet a few years ago. Which of the following is more likely?

A) 365 random people have 365 different birthdays.
B) 365^2 random people don't have all 365 birthadys.

The probabilities are close. Ignore February 29th.

[/ QUOTE ]

ok i am foolish enough to take a shot ( just like how i bluff the river with 8 high)
P(A) == 1/(365!)
P(B) >= 365*((364/365)^(365^2))

Am i close?
I will guess that B is more likely

random
09-03-2004, 12:21 AM
[ QUOTE ]
..will now look like an unwarranted attack

[/ QUOTE ] Certainly not. I said something stupid and it needed to be pointed out. I appreciate you deleting it, though. See ya.

bigpooch
09-03-2004, 02:57 AM
Well, they are close in order of magnitude. If anyone is
so inclined, they can check that the first probability is
roughly bigger by a factor of sqrt(2xpix365). (For those
who are mathematically inclined, it's almost immediate from
Stirling's approximation).

RiverTheNuts
09-03-2004, 04:34 AM
im just curious, but how the hell did 2 pi get into a formula with 365 days?? /images/graemlins/smile.gif

I should really learn this crap

Duke
09-03-2004, 05:06 AM
[ QUOTE ]
how the hell did 2 pi get into a formula with 365 days?

[/ QUOTE ]

Pi has nothing to do with the day count. Call it N days and then relate the 2 functions/series/whatever. That relation is where the guy is saying that pi comes from.

I don't know if he's right since I didn't investigate further, but that's what he means. I think.

~D

Gordon Scott
09-03-2004, 09:42 AM
Not a math guy but B
My guess would be that A isn't close.

well
09-03-2004, 03:25 PM
[ QUOTE ]

A) 365 random people have 365 different birthdays.

[/ QUOTE ]

365! / (365^365) = 1.45 * 10^-157 (appr.)

[ QUOTE ]

B) 365^2 random people don't have all 365 birthadys.

[/ QUOTE ]

The probability of someone having been born on day n (of the year) given all previous n-1 days are "filled" is:

1-(364/365)^(265^2-(n-1))

So the probability of not all days being "filled" is now

1 - Product[1-(364/365)^(365^2-(n-1)),{n,1,365}] = 1.15 * 10^-156 (appr.)

[ QUOTE ]
Which [...] is more likely?

[/ QUOTE ]

B.

bigpooch
09-04-2004, 12:29 AM
A) The first probability is exactly

P(A) = 365! /( 365^365)

By Stirling's approximation formula, for large n,
n! is roughly sqrt(2 x pi x n) x (n/e)^n where pi is about
3.14159265 and e is about 2.71828183 and so

365! is approximately

sqrt(2 x pi x 365)x(365^365)/(e^365)

and hence,

P(A) is about

sqrt(2 x pi x 365)/(e^365).

By using a better Stirling approximation (asymptotic
expansion of the Gamma function, which is just a function
that extends factorial to all the real numbers), n! is
actually bigger by a factor of

(1 + 1/(12n) + 1/(288 x n^2) - 139/(51840 x n^3) +...)

and so P(A) is really closer to

1.0002283365 x sqrt(2 x pi x 365)/(e^365)

or about

47.9/(e^365)

B) Well, I see where I committed a common error in my
back of the envelope calculation for my previous post!

The second probability p(B) is just

365 x p(everyone is not born on Jan. 1)
+C(365,2) x p(everyone is not born on Jan. 1/2)
+C(365,3) x p(everyone is not born on Jan. 1..3)
+...

It will be clear that the second and subsequent terms are
much smaller than the first term.

The first term is just 365 x (364/365)^(365^2)
=365 x ((364/365)^365)^365.

Now, (364/365)^365 is roughly 1/e; actually, it's about
0.99862857x(1/e). Thus, the first term is close to

365 x (0.99862857/e)^365
or about 221.181/(e^365).

Also, the second term is

(365x364/2) x {((363/365)^365)} ^365

where (363/365)^365 is close to 1/(e^2) and so this term is
in the order of e^-(2x365) which is much smaller than the
first term. One can see that each of the following terms
is then roughly smaller by a factor of e^365 (not quite
because of the combinatorial factor) compared with the
previous term.

In any case, P(B)/P(A) is about 4.61756 and P(B) is really
bigger and these probabilities are much closer than I had
originally thought!


LAZY MAN's APPROXIMATION:

This is the idea that gives one an immediate guess as to
which of these probabilities is bigger. Without caring too
much about how closely 1/e approximates (364/365)^365, one
can see that

P(A) looks like sqrt(2 x pi x 365)/(e^365)

and P(B) is (very!) roughly

365/(e^365).

(I had forgotten the numerator when typing my original
post!). So someone who is really careful and astute can
readily deduce that roughly

P(A)/P(B) = sqrt(2 x pi/365) or about 0.1312. (Actually,
you only need to know that 365 > 2 x pi for guessing that
B is more probable!)

Of course, unfortunately, the 1/e approximation is extremely
crude and hence one has to be careful since raising a crude
approximation to the power of 365 really distorts the
result!

pzhon
09-04-2004, 03:36 AM
[ QUOTE ]
This was posted on usenet a few years ago. Which of the following is more likely?

A) 365 random people have 365 different birthdays.
B) 365^2 random people don't have all 365 birthadys.

The probabilities are close. Ignore February 29th.

[/ QUOTE ]
Instead of just giving the answers, I'll give ways to estimate the values by hand.

A) The probability is (365/365)(364/365)(363/365)...(1/365) = 365!/(365^365).

A good way to estimate n! is Stirling's formula: n! ~ sqrt(2 pi n ) (n/e)^n. Stirling's formula is low by a factor of roughly (1+1/(12n))= 1.00023 when n=365. 365!/(365^365) ~ sqrt(2 pi 365)/(e^365) = 1.454623 x 10^-157.

The exact value is 1.454955 x 10^-157.

B) The probability that no one was born on January 1st is (364/365)^(365^2). A good approximation to the probability that 365^2 people don't have all 365 birthdays is 365 times (364/365)^(365^2). The exact value (by inclusion-exclusion) is 365 (364/365)^(365^2) - (365 choose 2) (363/365)^(365^2) + (365 choose 3) (362/365)^(365^2) - ... but the higher order terms are smaller than the first term by a factor of more than 10^100.

How can we estimate 365 (364/365)^(365^2)? (1-1/n)^n ~ 1/e, so one estimate is that this is 365((364/365)^365)^365 = 365(1/e)^365 = 365/(e^365). This estimate is off by a lot, a factor of 1.6. (1-1/n)^n is not close enough to 1/e.

1/e = 1 - 1 + 1/2 - 1/6 + 1/24 - 1/120 + ...

(1-1/n)^n = 1 - n/n + (n choose 2)/n^2 - (n choose 3)/n^3 + ...

Compare the third terms: In 1/e, this is 1/2, but in (1-1/n)^n, the term is ((n^2-n)/2) /n^2 = 1/2 - 1/(2n), lower by 1/(2n). Compare the fourth terms: In 1/e, this is -1/6, but in (1-1/n)^n, the term is -((n^3 - 3n^2 + 2n)/6)/n^3, higher by about 3/(6n). The coefficients of 1/n in the difference are 0 + 0 + 1/2 - 3/6 + 6/24 - 10/120 + 15/720 - ... = 1/(2e).

So, (1-1/n)^n ~ 1/e - 1/(2en) = 1/e (1-1/(2n)).

365 (364/365)^(365^2)
~ 365 (1/e (1 - 1/(2*365)))^365
~ 365/(e^365) * sqrt(1/e)
= 6.724496 x 10^-157

The actual value is 6.718345 x 10^-157.

B is larger, roughly by a factor of sqrt(365/(2 pi e)). Because 365 > 2 pi e, it is more likely that 365^2 people don't have all 365 birthdays than that 365 people have all 365 birthdays. Since 7 < 2 pi e, it is more likely that 7 people were born on different days of the week (.61%) than that 49 people were not born on all 7 days of the week (.37%).

FrankLu99
09-04-2004, 04:06 AM
thx 4 confirming that i still suck at math

BarronVangorToth
09-06-2004, 09:19 AM
[ QUOTE ]
A) The first probability is exactly

P(A) = 365! /( 365^365)

By Stirling's approximation formula, for large n,
n! is roughly sqrt(2 x pi x n) x (n/e)^n where pi is about
3.14159265 and e is about 2.71828183 and so

365! is approximately

sqrt(2 x pi x 365)x(365^365)/(e^365)

and hence,

P(A) is about

sqrt(2 x pi x 365)/(e^365).

By using a better Stirling approximation (asymptotic
expansion of the Gamma function, which is just a function
that extends factorial to all the real numbers), n! is
actually bigger by a factor of

(1 + 1/(12n) + 1/(288 x n^2) - 139/(51840 x n^3) +...)

and so P(A) is really closer to

1.0002283365 x sqrt(2 x pi x 365)/(e^365)

or about

47.9/(e^365)

B) Well, I see where I committed a common error in my
back of the envelope calculation for my previous post!

The second probability p(B) is just

365 x p(everyone is not born on Jan. 1)
+C(365,2) x p(everyone is not born on Jan. 1/2)
+C(365,3) x p(everyone is not born on Jan. 1..3)
+...

It will be clear that the second and subsequent terms are
much smaller than the first term.

The first term is just 365 x (364/365)^(365^2)
=365 x ((364/365)^365)^365.

Now, (364/365)^365 is roughly 1/e; actually, it's about
0.99862857x(1/e). Thus, the first term is close to

365 x (0.99862857/e)^365
or about 221.181/(e^365).

Also, the second term is

(365x364/2) x {((363/365)^365)} ^365

where (363/365)^365 is close to 1/(e^2) and so this term is
in the order of e^-(2x365) which is much smaller than the
first term. One can see that each of the following terms
is then roughly smaller by a factor of e^365 (not quite
because of the combinatorial factor) compared with the
previous term.

In any case, P(B)/P(A) is about 4.61756 and P(B) is really
bigger and these probabilities are much closer than I had
originally thought!


LAZY MAN's APPROXIMATION:

This is the idea that gives one an immediate guess as to
which of these probabilities is bigger. Without caring too
much about how closely 1/e approximates (364/365)^365, one
can see that

P(A) looks like sqrt(2 x pi x 365)/(e^365)

and P(B) is (very!) roughly

365/(e^365).

(I had forgotten the numerator when typing my original
post!). So someone who is really careful and astute can
readily deduce that roughly

P(A)/P(B) = sqrt(2 x pi/365) or about 0.1312. (Actually,
you only need to know that 365 > 2 x pi for guessing that
B is more probable!)

Of course, unfortunately, the 1/e approximation is extremely
crude and hence one has to be careful since raising a crude
approximation to the power of 365 really distorts the
result!


[/ QUOTE ]



I just envisioned a new person to this site going to this thread first to pick up some basic odds for, I don't know, a draw or something and coming to the above post.

Math overload, alert, alert, his brain thinks, as he believes that his two soooooted cards should make him a flush, you know, "most of the time."


Barron Vangor Toth
www.BarronVangorToth.com (http://www.BarronVangorToth.com)

well
09-06-2004, 10:52 AM
Couldn't you at least say if you came up with the same answer?
And what you think of my approach...