+ Reply to Thread
Results 1 to 12 of 12

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

  1. #1
    Points: 1,725, Level: 24
    Level completed: 25%, Points required for next Level: 75

    Posts
    10
    Thanks
    0
    Thanked 0 Times in 0 Posts

    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. #2
    Devorador de queso
    Points: 95,819, Level: 100
    Level completed: 0%, Points required for next Level: 0
    Awards:
    Posting AwardCommunity AwardDiscussion EnderFrequent Poster
    Dason's Avatar
    Location
    Tampa, FL
    Posts
    12,935
    Thanks
    307
    Thanked 2,629 Times in 2,245 Posts

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

    Can you link to the solution you're referring to?
    I don't have emotions and sometimes that makes me very sad.

  3. #3
    Points: 1,470, Level: 21
    Level completed: 70%, Points required for next Level: 30

    Posts
    50
    Thanks
    0
    Thanked 5 Times in 4 Posts

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


  4. #4
    Points: 1,725, Level: 24
    Level completed: 25%, Points required for next Level: 75

    Posts
    10
    Thanks
    0
    Thanked 0 Times in 0 Posts

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

    Quote Originally Posted by Dason View Post
    Can you link to the solution you're referring to?
    The link is

    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. #5
    Points: 1,725, Level: 24
    Level completed: 25%, Points required for next Level: 75

    Posts
    10
    Thanks
    0
    Thanked 0 Times in 0 Posts

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

    Quote Originally Posted by ArtK View Post
    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. #6
    Points: 1,725, Level: 24
    Level completed: 25%, Points required for next Level: 75

    Posts
    10
    Thanks
    0
    Thanked 0 Times in 0 Posts

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

    The link is

    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. #7
    Points: 1,470, Level: 21
    Level completed: 70%, Points required for next Level: 30

    Posts
    50
    Thanks
    0
    Thanked 5 Times in 4 Posts

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

    Quote Originally Posted by Leo Simon View Post
    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. #8
    Points: 1,725, Level: 24
    Level completed: 25%, Points required for next Level: 75

    Posts
    10
    Thanks
    0
    Thanked 0 Times in 0 Posts

    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. #9
    Points: 1,725, Level: 24
    Level completed: 25%, Points required for next Level: 75

    Posts
    10
    Thanks
    0
    Thanked 0 Times in 0 Posts

    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. #10
    Points: 1,470, Level: 21
    Level completed: 70%, Points required for next Level: 30

    Posts
    50
    Thanks
    0
    Thanked 5 Times in 4 Posts

    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. #11
    Points: 1,470, Level: 21
    Level completed: 70%, Points required for next Level: 30

    Posts
    50
    Thanks
    0
    Thanked 5 Times in 4 Posts

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

    Quote Originally Posted by Leo Simon View Post
    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. #12
    Points: 1,470, Level: 21
    Level completed: 70%, Points required for next Level: 30

    Posts
    50
    Thanks
    0
    Thanked 5 Times in 4 Posts

    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.

    P (N) = 1 - \sum_{i=0}^{\frac N2} \frac{365! N!}{i!(365-N+i)! 2^{i}(N - 2i)!365^N}
    Last edited by ArtK; 12-02-2014 at 12:36 PM.

+ Reply to Thread

           




Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts






Advertise on Talk Stats