# Thread: Probability of k pairs of birthdays in a group of n people

1. ## Probability of k pairs of birthdays in a group of n people

Could somebody please tell me the formula for computing the probability that exactly k pairs will have the same birthday out of a group of n people? Happy as usual to ignore leap-years and assume that a person is equally likely to be born on any given day.

I managed to find one answer to precisely this problem on the web, but unfortunately the author's probability of 7 pairs out of 100 turned out to be 3 x 10^254, which seems a bit high for a probability...

Thanks very much indeed for any suggestions!

2. ## Re: Probability of k pairs of birthdays in a group of n people

Can you link to the solution you're referring to?

4. ## Re: Probability of k pairs of birthdays in a group of n people

Originally Posted by Dason
Can you link to the solution you're referring to?

https://amca01.wordpress.com/2011/04...eneralization/

The formula given in this document for exactly i matches from a total of n people is

￼365! * n! / ( i! * ( 365 - n + i )! * 2^i * ( n - 2*i )! )

It's obvious by inspection that this is going to be larger than 1

5. ## Re: Probability of k pairs of birthdays in a group of n people

Originally Posted by ArtK
Thanks for this, Art. This is a helpful reference but only considers the classical problem, and a few variants that aren't helpful for me. Just on the very small offchance that anybody else is interested in this problem, however, it does however contain one reference which gives an answer that seems of the right order of magnitude: the reference is

An Extension of the Birthday Problem to Exactly k Matches
Author(s): Robert L. Hocking and Neil C. Schwertman
Source: The College Mathematics Journal, Vol. 17, No. 4 (Sep., 1986), pp. 315-321

and the formula for exactly k matches from a total of n people

n! * 365! / ( 365^n * k! * 2^k * (n - 2k)! * (365 - n + k)! )

So for example, the probability of exactly 8 matches in a group of 100 people is very close to 0.018.

I mentioned earlier in this thread a reference to an erroneous formula. The error in that document, which is unfortunately much more accessible to the public than the J.College Math article, was the omission of 365^n in the denominator. That's a rather big omission!

6. ## Re: Probability of k pairs of birthdays in a group of n people

https://amca01.wordpress.com/2011/04...eneralization/

The formula quoted in this document for the probability of k matches out of n people is

365! * n! / ( k! * 2^k * ( n - 2i ) ! * ( 365 - n + k )! )

As noted below, the problem with this formula appears to be the omission of 365^n in the denominator.

7. ## Re: Probability of k pairs of birthdays in a group of n people

Originally Posted by Leo Simon
Thanks for this, Art. This is a helpful reference but only considers the classical problem, and a few variants that aren't helpful for me. Just on the very small offchance that anybody else is interested in this problem, however, it does however contain one reference which gives an answer that seems of the right order of magnitude: the reference is

An Extension of the Birthday Problem to Exactly k Matches
Author(s): Robert L. Hocking and Neil C. Schwertman
Source: The College Mathematics Journal, Vol. 17, No. 4 (Sep., 1986), pp. 315-321

and the formula for exactly k matches from a total of n people

n! * 365! / ( 365^n * k! * 2^k * (n - 2k)! * (365 - n + k)! )

So for example, the probability of exactly 8 matches in a group of 100 people is very close to 0.018.
Leo, I thought I should let you know that it appears you made a error someplace. I get 0.03013
for 100,8. The reason I think my result is accurate is that I found an article where a guy was
using that "exactly K" formula and he gave a couple of results that are in agreement with
my calculations. For 37,4 we get p= 0.0513963 For 36,5 we get 0.0099943

It's interesting to plot P results for K = 1 to X using that formula. For example, with N = 170
I get a bell shaped curve that peaks at K = 28 (with a P there of 0.0009007). Sums of "all"
probabilities do not tend to equal one, so this seems to be a example of a non-distribution
(or whatever such things are called). Anyway, my interest in summing was to play with the
idea of summing from some K on upward to find the "at least K" probabilities using this
formula. I haven't attempted the ugly recursive formula given at the Wolfram page

Art

8. ## Re: Probability of k pairs of birthdays in a group of n people

Thanks very much, Art! I also made a dumb typo, what I had actually computed was 100,7 not 100,8, so I'm even further off.

My computation method was simply Wolfram Alpha's freebie web calculator, which Ican is not particularly reliable. I tried to do it in matlab, my engine of
choice, but it couldn't get past go with these big numbers. What did you use?

I'm going to try to compute 100,7 in a way that Matlab can handle, by cancelling everything in sight. Would be curious to learn what you get for 7 pairs.

9. ## Re: Probability of k pairs of birthdays in a group of n people

Hi Art. Ok, I now have nice matlab code that works and matches exactly all three numbers you provided. With n = 100, I also get a bell-shaped curve, which peaks at 10. I maligned Wolfram alpha unfairly, its answer was perfectly accurate, the problem was just that the answer I quoted of 0.18 was for 7 pairs not eight. Very curious indeed, to a non-statistician, that the probabilities follow a bell-shaped curve.

10. ## Re: Probability of k pairs of birthdays in a group of n people

Hello Leo. I get 0.018 for 100,7. I'm a old BASIC hacker so I write programs for
formulas such as these. Factorials > 160! overflow double precision, so I use
logarithms.

Art

11. ## Re: Probability of k pairs of birthdays in a group of n people

Originally Posted by Leo Simon
Very curious indeed, to a non-statistician, that the probabilities follow a bell-shaped curve.
I'm not a statistician either but the bell curve makes perfect sense because of the "exactly K" nature of the formula.
With large enough N, I expect probabilities to be small for both small K and large K, and maximize in some
intermediate region of K.

Art

12. ## Re: Probability of k pairs of birthdays in a group of n people

I have been meaning to practice and start learning LaTex. The following formula is my first
attempt.

The formula is allegedly for the Birthday Problem "trio" ... the probability that there are at
least three people having the same birth day in a crowd of N people.

I say "allegedly" since I find different answers to this same problem when I search. Those
that agree with this formula find N = 88 people for nearly a 50% chance. Recall that the
magic number is N = 23 for the much simpler problem of a pair instead of a trio.

Anyway, please forgive my wandering off Leo's subject. I do hope that at least some here
will find the subject of "at least K" for K > 2 of interest. I've taken a interest in
approximate methods for larger K. Comments here by the experts would be appreciated.

 Tweet