|
|
#11
09-03-2004, 03:25 PM
|
|||
|
|||
B.
[ 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. 
|
|
#12
09-04-2004, 12:29 AM
|
|||
|
|||
|
Re: Unusual birthday puzzle
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!
|
|
#13
09-04-2004, 03:36 AM
|
|||
|
|||
|
Re: Unusual birthday puzzle (Answer)
[ 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%).
|
|
#15
09-06-2004, 09:19 AM
|
|||
|
|||
|
Re: Unusual birthday puzzle
[ 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
|
 |
|
|
Linear Mode
