Wikipedia:Reference desk/Archives/Mathematics/2017 December 5

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

December 5

Matching birthdays

I know that in a room full of people you need very few before you have a pair with a common birthday (something like 23 - I haven't looked it up).

If you have two rooms of people, each with 'N' people, how big does N have to be before you (on average) get a match? How big for 'Y' matches (in particular 'Y=20'? -- SGBailey (talk) 07:30, 5 December 2017 (UTC)

Am I wrong? Sureley if you had a room with (say) 23 people in it, the probability if a match is ‘x’. If you then built a dividing wall in the room, making, in effect, two rooms, the probability of a match would still be 'x’, irrespective of whether the division was 11/12, or 10/13, or 22/1 etc? — Preceding unsigned comment added by 82.38.221.49 (talk) 09:40, 5 December 2017 (UTC)

I am interpreting the question differently. I think the question is how many people need to be in each of 2 rooms (same number in each room) so that there is a greater than 50% probability that a pair in one room or the other (or both) have the same birthday. If there are n people in each room and the probability of a birthday match in one room is P(n) then we want to find n such that (1-P(n))² < 0.5 i.e. probability of no match in either room is less than 0.5. So P(n) > 1 - sqrt(0.5) which is approximately 0.29. To make P(n) greater than 0.29, I get n = 17, which makes P(n) approximately 0.315 and (1-P(n))² approximately 0.469. Gandalf61 (talk) 10:09, 5 December 2017 (UTC)

I obviously phrased the question poorly. N people in each room. How many are needed so someone in room A matches a person in room B? (EG mixed sex couples arrive at a party - how long before a man has the same birthday as a woman?) How many people in each room before 20 matches are likely? It is possible for there to be 1 million in each room and not have a match (if room A is filled with Jan to Jun and Room B with Jul to Dec). -- SGBailey (talk)

Just a quick note, you need to be a little more careful what you're looking for. Something like "how many people have to be in the room before there's a match?" doesn't make sense. You need to ask something like "how many people have to be in the room until there's at least a 50% chance of a match?". –Deacon Vorbis (carbon • videos) 14:06, 5 December 2017 (UTC)

Have you seen Birthday_problem? AlfonsoAnonymous (talk) 19:01, 5 December 2017 (UTC)

Yes, I even refer to it (though not by name) in the first line of my original question.

Also I did mention "on average" and "matches are likely" as an (obviously failed) attempt to indicate that certainty isn't possible and probability is the name of the game. So does anyone know the answer or perhaps how to evaluate it. -- SGBailey (talk) 19:21, 5 December 2017 (UTC)

The probability of no collision can be written as an explicit double sum involving Stirling numbers of the second kind, which is good enough for computation: here are the probabilities of no collision for up to 20 people. {{0, 1.}, {1, 0.99726}, {2, 0.989086}, {3, 0.975611}, {4, 0.957054}, {5, 0.933714}, {6, 0.905959}, {7, 0.874221}, {8, 0.838981}, {9, 0.800759}, {10, 0.760099}, {11, 0.71756}, {12, 0.6737}, {13, 0.629065}, {14, 0.584179}, {15, 0.539533}, {16, 0.49558}, {17, 0.452724}, {18, 0.411317}, {19, 0.371661}, {20, 0.333997}}.

On the other hand, the expected number of matches is extremely straightforward to compute by linearity of expectation: it is $n^{2}/365$ for n people in each group. (Both answers disregard leap years.) --JBL (talk) 21:40, 5 December 2017 (UTC)

Thank you - that was what I was seeking. -- SGBailey (talk) 07:15, 6 December 2017 (UTC)

I know you referred to the one point about needed 23 people before the probability is above 50%, but because you did not refer to it by name I wasn't sure if you had found the relevant Wikipedia article. It has more information than just that one number, and I thought some of that information may be helpful. In fact, the page I linked mentions the double sum involving Stirling numbers of the second kind that I believe JBL refers to. (Though JBL may be referring to a different formula, I am not totally sure. The point is that the article has plenty of relevant information.) AlfonsoAnonymous (talk) 11:30, 7 December 2017 (UTC)

Yes, that's right. (Your first answer was a good one, and would have been even if a section addressing this specific variation hadn't existed.) --JBL (talk) 12:37, 7 December 2017 (UTC)

Successor function paradox loop?

If the successor function is defined for $n\in \mathbb {N}$

${\begin{aligned}(1)\quad &n+0=n\\(2)\quad &S(n)=n+1\\(3)\quad &n+S(m)=S(n)+m=S(m+n)\end{aligned}}$

then how are we trying to prove associativity for addition, while definition (3) requires the proofs of associativity and commutativity below?

$n+(m+1)=(n+1)+m=(n+m)+1$

יהודה שמחה ולדמן (talk) 15:30, 5 December 2017 (UTC)

I don't think I understand your question. How does the definition require the proofs below? What proofs below? What are you actually asking? –Deacon Vorbis (carbon • videos) 15:55, 5 December 2017 (UTC)

What the proof of associativity for addition actually wants to do, is to prove the general associativity n+(m+c) = (n+m)+c, by the special case of associativity - wherein c=1, so where is the loop? Is the loop the (legitimate) desire to prove "general associativity" - by "special associativity" - i.e. by (3)? I don't see here any loop, because (3) - being a part of the definition of the successor function - does not need any proof, because - like all other definitions - (3) is like an axiom. HOTmag (talk) 16:21, 5 December 2017 (UTC)

Also, it sounds like you've got things backwards. Addition is defined in terms of the successor function, not the other way around. Maybe that's where your confusion arises. On a side note, the article you linked with the proofs is kind of a train wreck. I'm not sure whether it should be improved or just submitted to AfD. Does anyone else have any thoughts? –Deacon Vorbis (carbon • videos) 17:20, 5 December 2017 (UTC)

I believe the proof of associativity in the article is correct. However I don't think we should be giving proofs in Wikipedia unless they're fairly trivial or of particular note - we should point people at citations for the proofs. Dmcq (talk) 18:30, 5 December 2017 (UTC)

Let me ask: You are saying all 3 properties are actually defined to already have both associativity and commutativity? יהודה שמחה ולדמן (talk) 19:26, 5 December 2017 (UTC)

Your statement seems to have a category error. What does it mean for one of the listed properties to be "defined to already have associativity and commutativity" ? The properties are as you have listed them. Nothing more.--129.74.112.165 (talk) 21:14, 5 December 2017 (UTC)

According to the linked article, the successor function isn't actually defined but is subject to the Peano axioms. You can then prove addition is associative based on those axioms and the definition of addition in terms of the successor function. You might want to read 'Foundations of Analysis' by Edmund Landau for a good, if slightly dated, exposition of this; it's available for free on the internet. --RDBury (talk) 21:27, 5 December 2017 (UTC)

PS. I see that Landau is already used as a reference in the second linked article. To respond to Dmcq, a few years back there was a long discussion on Wikipedia talk:WikiProject Mathematics about the policy for proof on WP. The proofs in the article do seem unencyclopedic and imo should be moved to WikiBooks. A major problem with proofs in an encyclopedia is there needs to be some context for a proof to be valid; what is being assumed for the proof and what is the theorem to be used for. In this case there is a flaw in that the so-called inductive definition (A1 and A2) in the article does not define anything; it's just a pair of functional equations. In order for these to become a definition there has to be a theorem which states that this pair of functional equations has a unique solution, and this theorem isn't in the article. Since the + operation hasn't been properly defined it makes no sense to even ask whether it's associative. Landau goes to some lengths to address this issue and to do the job properly you really need to view the book as a whole, not just pull out bits and pieces. --RDBury (talk) 22:19, 5 December 2017 (UTC)

PPS. Wikipedia:WikiProject Mathematics/Proofs has some material on when and how to include proofs in WP. Not saying it's binding or even that I agree with everything in there though. --RDBury (talk) 22:32, 5 December 2017 (UTC)