Talk:Birthday problem

Mathematics B‑class Low‑priority

	Mathematics portal This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics
B	This article has been rated as B-class on Wikipedia's content assessment scale.
Low	This article has been rated as Low-priority on the project's priority scale.

Archives

/Archive 1

"Near matches" - careless comment?

It is very careless to say that

"Thus in a family with six members, it is more likely than not that two members will have a birthday within a week of each other."

While i realise that it's tempting to make the group of six people a family, birthdays within a family are generally far from independent, especially if siblings are included!

Given the article it belongs to, i think the statement is out of place.

—The preceding unsigned comment was added by Rileen (talk • contribs) 12:51, 9 August 2006 (UTC).[reply]

Good point. Fixed. Thanks. --Keeves 18:33, 9 August 2006 (UTC)[reply]

Glad to see that - this was my first (which is why i also forgot to mention my name) teeny-weeny contribution to Wikipedia. Thanks! --Rileen, 11 August 2006

This is a valid statement within the context of the 'uniform birthday distribution' ideal set forth at the start of article. —The preceding unsigned comment was added by Qe2eqe (talk • contribs) 18:17, 17 April 2007 (UTC).[reply]

29 February

It makes the article significantly more complex to take into account 29 February, so most of it doesn't — except for bits of the first paragraph. I think the article should simply state early on that 29 February will be completely ignored, and then it should abide by that.

Does anyone object to this?

Ruakh 17:09, 13 August 2006 (UTC)[reply]

I had thought of that exact idea yesterday, and I'm glad you suggested it. I have now added such a paragraph, and I hope it will be noticable enough to bring this back-and-forth to an end. --Keeves 21:32, 13 August 2006 (UTC)[reply]

Hmm. Your paragraph is very clear, but I worry that it might be a bit much; after all, it's not really the central point of the article, but really just a caveat clarifying that the article is about an abstract mathematical concept and does not necessarily apply perfectly to real life. It seems like a single sentence could conceivably suffice. (Further, it's not true that "it is just as likely that a randomly-chosen person's birthday will be January 21 or October 5 or almost any other day of the calendar"; different times of year actually have fairly different birth rates.) Ruakh 03:12, 14 August 2006 (UTC)[reply]

A footnote should be more then sufficent to account for the leapyear birthdays and just have a further explaination thereof. —The preceding unsigned comment was added by 12.163.97.74 (talk • contribs).

Mystery!

"23"! --nlitement ^[talk] 13:37, 30 September 2006 (UTC)[reply]

Approximation based on Taylor Series expansion

Isn't the expression obtained for p_bar(n) =approx= 1*e^-1/356*e^-2/365*...*e^-(n-1)/365 in the "Approximation" subsection based on the inequality "(1-x) < (e^-x)"? It doesn't seem to be based on the Taylor Series expansion of the exponential function; instead, it directly uses the exponential function. —The preceding unsigned comment was added by Wiki user 618 (talk • contribs) 03:13, 9 November 2006 (UTC).[reply]

But exp(-x) = 1 - x + x^2/2 - ... IS the Taylor expansion of exp(-x). Cut the expansion off after the term in x, and you get exp(-x) = 1-x. You can see that 1-x < exp(-x), by looking at the quadratic term of the Taylor expansion (the Taylor expansion is an alternating series). So you are basically saying the same thing, but the article actually shows why the inequality holds. —The preceding unsigned comment was added by 134.58.253.131 (talk • contribs) 11:30, 12 February 2007 (UTC).[reply]

Near matches?

Can we either cite or insert the math for the "near match" birthdays? The information is stated without proof. arctic 00:28, 27 November 2006 (UTC)[reply]

You're right to be concerned; I just wrote a quick Perl script to investigate this probabilistically, and it seems like the correct values for the table would be:

within k days	# people required
0	23
1	14
2	11
3	9
4	8
5	8 ← not 7, as the page currently has
7	7 ← not 6, as the page currently has

(Note: that was only probabilistic, but I used some basic techniques to ensure accurate results, so I'm fairly confident those are the correct values. As you say, though, a source or mathematical justification is quite necessary here. BTW, lest anyone be concerned that my random number generator might be biased — that's a valid concern, and it might well be, but if that were affecting the results, you'd typically expect greater synchronicity, hence lower values for the number of people necessary to ensure a 50% probability of a near match. The only bias that would produce higher values is a bias against synchronicity; that is, if the generator has a greater-than-random tendency against yielding recently-yielded numbers. I'll run some tests to ensure that that's not the case here, then comment back.)

Ruakh 01:49, 27 November 2006 (UTC)[reply]

Okay, I ran some tests, and it doesn't look like my random number generator has any bias against synchronicity. So, I think the table in the article is wrong. Ruakh 02:11, 27 November 2006 (UTC)[reply]

The table was indeed wrong, so I corrected it (and cited a source for the data). It's unfortunate that the error remained so long. --Sopoforic 03:16, 21 February 2007 (UTC)[reply]

Collision counting

This was useful to me testing a password generation programme, and I couldn't find anywhere else in Wikipedia that gave this information. The hash collision article could perhaps link directly to this section.

I suggest that the section's usefulness would be improved by the addition that for 1 << n << d, as is typical, the formula reduces to $n^{2}/2d$ .

Also, knowing the standard deviation would be useful, as I'd like to assess how reasonable my observed number of collisions is. Jlittlenz 05:07, 8 December 2006 (UTC)[reply]

Forward vs. reverse?

Is there any reason for the notion that the "birthday problem" is computing p given n, while the "reverse birthday problem" is computing n given p (as implied in #Reverse problem)? Insofar as the two are separate problems, it seems to me that the ordinary birthday problem is computing the minimal n such that p > ½, so the "reverse birthday problem" would be computing p given n. —Ruakh_TALK 16:23, 8 December 2006 (UTC)[reply]

366 People isn't necessarily 100%

In the article, it claims, although it cannot actually be 100% unless there are at least 366 people.[1] However, the real number should be 367, because there are 366 days in a leap year. Someone could be born on February 29th, and then no one would have the same birthday out of 366 people. Correct me if I'm wrong, Thanks, RAmen, Demosthenes 21:48, 15 February 2007 (UTC)[reply]

Yes, you are correct, but check the footnote. We're assuming 365 days in a year for sake of simplicity in calculations. — Edward Z. Yang^(Talk) 22:48, 15 February 2007 (UTC)[reply]

Featured Article

I think this is an interesting subject, great article i think it's featured article quality comments? I dont know how to tag it for that status myself.. —The preceding unsigned comment was added by 83.49.105.6 (talk) 20:56, 12 March 2007 (UTC).[reply]

There are instructions at WP:FAC. Greeves ^{(talk • contribs)} 15:50, 31 March 2007 (UTC)[reply]

Conundrum, not paradox

Paradox? Don't you mean conundrum. a paradox is something I thought to be impossible!! And this is not. —The preceding unsigned comment was added by 131.111.8.98 (talk • contribs) 00:05, 18 April 2007 (UTC).[reply]

To quote the third sentence of the article:

This is not a paradox in the sense of leading to a logical contradiction; it is called a paradox because mathematical truth contradicts naive intuition: most people estimate that the chance is much lower than 50%.

—Ruakh_TALK 01:49, 18 April 2007 (UTC)[reply]

I have only come across this before referred to as the 'Birthday Surprise' which is a better description since it is not a paradox. You should mention that it is also known as 'Birthday Surprise' (as it has in note 4 and the Klamkin and Newman reference).62.255.240.100 12:18, 15 May 2007 (UTC)[reply]

My IB Math Studies Project

Hi people, I have already contributed in the past to this article, and having done my math studies project on this topic, I would like to contribute with my testings.

By the way why is my name always deleted from the references?? I contributed to this article —The preceding unsigned comment was added by 90.0.168.169 (talk) 19:15, 30 April 2007 (UTC).[reply]

Hi,

Thanks for your contributions!

Please note that the purpose of the "references" section is to show the sources from which Wikipedians take their information, not to show the Wikipedians who took their information from those sources.

Unless you can cite a specific claim in the article that comes from your high school math project and not from the other references, it looks (and is) really awkward to list a contributor's high school math project in the references. And if there is a claim that comes from your high school math project and not from the other references, then we should consider removing that claim until such time as you get your research published in a peer-reviewed journal; verifiability from reputable sources is a fundamental element of Wikipedia. (This is not in any way to criticize your math project; I'm familiar with the IB program, and am sure that your project was very impressive by high school standards. Kudos to you. But that doesn't make it appropriate as a reference here. After all, just because something was an IB project, that doesn't mean that it garnered a good grade, or that it would stand up to professional scrutiny. IB projects are first and foremost a learning experience.)

—Ruakh_TALK 01:23, 1 May 2007 (UTC)[reply]

Hi again As I was doing my math project, ergo in the past year and a half, I periodically updated this article with what I found with my researches. Unfortunately I didn't know that my project would be sent to IB to be verified. This means that they may think I have copied, even though it is the exact contrary :( That's why I would like my name to appear. Anyways thanks for the answer —The preceding unsigned comment was added by 90.0.46.7 (talk • contribs) 12:32, 1 May 2007 (UTC).[reply]

Oh, scary. Best of luck with that. :-/ —Ruakh_TALK 15:02, 1 May 2007 (UTC)[reply]

So is it ok to put me in the references? —The preceding unsigned comment was added by 90.0.46.7 (talk • contribs) 16:08, 1 May 2007 (UTC).[reply]

I'm sorry, but that's still not what references are for. :-/ —Ruakh_TALK 16:41, 1 May 2007 (UTC)[reply]

And In the External link can I put back the test I did with the players? —The preceding unsigned comment was added by 90.0.46.7 (talk • contribs) 20:36, 1 May 2007 (UTC).[reply]

Nonsense.

i didn't believe that these calculations are correct so i made an experiment: i rounded up 3 groups of people. every group constisted of 50 people so there SHOULD be a 97% chance that 2 of them celebrate their birthday on the same day (in each group).

guess what: there weren't 2 guys with the same birthday in none of the groups. in fact there weren't even any guys in these 150 persons who had their birthday on the same day.

mathematically, the chance of that happening is close to 0 (like 0,0x%). so the result of the experiment would be far more than highly unlikely. still, it proves that this calculation (like everything in maths) is just another pathetic attempt of human beings to define the nature of our environment. —The preceding unsigned comment was added by Sonandzon (talk • contribs) 21:26, 5 May 2007 (UTC).[reply]

Re: Nonsense

Unsigned, juvenile, biased, and disparaging commentary will be (and has been, here) deleted. The validity of basic statistical and mathematical methodology is beyond reproach. Lesotho 23:09, 5 May 2007 (UTC)[reply]

Re: who you talking to? —The preceding unsigned comment was added by 90.4.17.239 (talk • contribs) 12:38, 8 May 2007 (UTC).[reply]

Sonandzon, I think this is an interesting study. If what you found is repeatable, it shows that although the mathematics is correct, the assumptions behind it are not. Why don't you do a serious experiment and publish your findings in a peer reviewed conference or journal? -Pgan002 00:26, 22 June 2007 (UTC)[reply]

Wrong

I disagree with the mathematics on which this article is based.

The probability that in a group of two, both share the same birthday = 1/366.

The probablility that in a group of three, one pair share the same birthday (three people make 3 pairs = (1/366) + (365/366)*(1/365) + (365/366)*(364/365)*(1/364) = 3/366

The probability that in a group of four (i.e. 6 pairs) that one pair share the same birthday is (1/366) + (365/366)*(1/365) + (365/366)*(364/365)*(1/364) + (365/366)*(364/365)*(363/364)*(1/363) + (365/366)*(364/365)*(363/364)*(362/363)*(1/362) + (365/366)*(364/365)*(363/364)*(362/363)*(361/362)*(1/361) = 6/366

From this it can be seen that for a group of $n$ people, there will be $n(n-1)/2$ pairs, and that the probability that one pair share the same birthday will thus be $(n(n-1)/2)/366$ .

Hence the probability that a single pair in a group of $n$ people will share the same birthday will be at least 50% when there are 133 pairs, because 133=366/2. This occurs when $n=19$ (approximate to nearest whole).

The probability that a single pair in a group of $n$ people will share the same birthday is 100% when there are 366 or more pairs of people: this occurs when $n=27$ (approximate to nearest whole). --Justificatus 15:47, 6 August 2007 (UTC)[reply]

The article explicitly skips leap years, but it sounds like you're calculating based on one. Mmernex 16:02, 6 August 2007 (UTC)[reply]

You're close, but a bit off. The problem is, it's possible for three people to all share a birthday, and you're counting each case of this as though it were three cases of two people sharing a birthday, when for our purposes it's actually equivalent to just one case of two people sharing a birthday. (And, analogously with larger groups.) In more general terms, remember that P ( A ∨ B ) = P ( A ) + P ( B ) − P ( A ∧ B ); hence, P ( A ∨ B ) ≠ P ( A ) + P ( B ) (except in the special case that A and B are mutually exclusive). —Ruakh_TALK 18:39, 6 August 2007 (UTC)[reply]

365 different birthdays -- what am I missing?

I wish to take issue with the statement, "After having met people with n different birthdays (n < 365), the chance that the next person you meet has a colliding birthday is (365-n)/365."

Suppose I am just getting started. I have met one person, and recorded their birthday. The number of different birthdays n is then 1.

The quoted text asserts that there are 364 chances out of 365 that the second person I meet will have the same birthday as the first one. This seems counter-intuitive. Likewise, if my list of birthdates is long, and I have n = 364, then the equation predicts that there is only one chance in 365 that the next person I meet has a birthday that is already on my list.

In summary, the equation says that at the beginning when n is small, I will have a large number of collisions, and as the size of my list of birthdays grows, the likelihood of a collision will decrease. --Jamesglong 18:14, 13 August 2007 (UTC)[reply]

Heh, good catch. I'm not sure how to fix this, though; in general, that section is assuming some things I'm not sure about. I think for now I'll label it "disputed", and we can work on fixing it up. —Ruakh_TALK 18:49, 13 August 2007 (UTC)[reply]

I think that (365-n)/365 is the probability that the next person you meet will have a non-colliding birthday. After you've collected one birthday, there is a good chance (364 in 365) that the next person will have a different birthday. Once you've collected 365 birthdays, you cannot collect any new birthdays and the probability is zero.--143.215.153.96 19:53, 14 August 2007 (UTC)[reply]

Coupon collector's problem

I didn't find a page for this problem on wikipeida, altough it is related to this article. There are N coupons on a desk, and you have to pick from them randomly (without taking the picked one from the desk). What is the expected amount of picks, until you have picked al of them at least once.

Google found the answer N*(ln N + Euler's constant) here