Results 1 to 4 of 4

Math Help - An extension of a birthday problem

  1. #1
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6

    An extension of a birthday problem

    Hi

    A few days ago, we were 3 in my class of 35 people to have the same birthday. That was quite a coincidence
    But the wikipedia page about the birthday problem only deals with 2 people having the same birthday.

    So I'd like to know how to compute the probability that out of n people, 3 (or more) have the same birthday ?

    Thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    Quote Originally Posted by Moo View Post
    Hi

    A few days ago, we were 3 in my class of 35 people to have the same birthday. That was quite a coincidence
    But the wikipedia page about the birthday problem only deals with 2 people having the same birthday.

    So I'd like to know how to compute the probability that out of n people, 3 (or more) have the same birthday ?

    Thanks
    Hello Moo,

    Ross, "A First Course in Probability,7th edition", says the probability that no 3 of n people have the same birthday is "a difficult combinatorial problem", but he gives the following "good approximation".

    Suppose we have a trial for each of the \binom{n}{3} triplets i, j, k where 1 \leq i < j < k \leq n and say we have a success if i, j, and k all have the same birthday. Then the number of successes is approximately a Poisson random variable with

    \lambda = \binom{n}{3} P(\text{i, j, k, have same birthday}) = \binom{n}{3} (1 / 365)^2 = \frac{n(n-1)(n-2)}{6 \times 365^2}

    Hence
    P(\text{no 3 have the same birthday}) \approx \exp \left( \frac{-n(n-1)(n-2)}{6 \times 365^2} \right)

    If you are looking for an exact solution, Julian Havil in "Nonplussed" refers to a 2004 paper by R.J. McGregor and G.P. Shannon, "On the generalized birthday problem", Mathematical Gazette 88(512):242-48, but Havil doesn't give any details and I don't have a copy of the paper handy.

    Havil does say, quoting McGregor and Shannon, that the probability that at least 3 of 88 people will have the same birthday is about 1/2.
    Last edited by awkward; December 19th 2009 at 09:44 AM. Reason: added 3 of 88
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Aug 2008
    From
    Paris, France
    Posts
    1,174
    Quote Originally Posted by Moo View Post
    So I'd like to know how to compute the probability that out of n people, 3 (or more) have the same birthday ?
    Hi,

    If you want an exact formula, this comes from simple combinatorics, but there's no "nice-looking" answer...: I get, for at least 3 simultaneous birthdays (let N=365)

    p=1-\frac{1}{N^n}\sum_{0\leq 2k \leq n}\frac{n!N!}{2^k k!(n-2k)!(N-(n-k))!}.

    I did not check the number 88 with Maple, it would be safer to try...

    How I got the formula: we have to compute the number of n-uplets from \{1,\ldots,N\} where the same value is not taken three times. The index k in the formula stands for the number of pairs of matching birthdays (k=0 gives the usual case). For a given number k, and given the positions of the pairs, we have N(N-1)\cdots(N-(n-k)+1) possibilities (we choose k values for the pairs and n-(2k) values for the others, all different). And for a given k, the number of positions of these k pairs is: {n\choose 2k}(2k-1)(2k-3)\cdots 3\cdot 1 (choice of the subset made by the pairs, and choice of the matchings). This gives a total number:

    \sum_{0\leq 2k\leq n}{n\choose 2k}(2k-1)(2k-3)\cdots5\cdot 3\cdot N(N-1)\cdots(N-(n-k)+1).

    The previous formula follows after a mild rewriting.

    I let you guess how ugly a general formula might look like...

    PS. I forgot to mention: "Happy Birthday, Moo!"
    Last edited by Laurent; December 21st 2009 at 03:29 AM. Reason: PS
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    Oops, I forgot to see look this thread afterwards...
    Well, seems really ugly yeah... but it's not difficult to understand (though difficult to find... - gotta hate combinatorics)

    Thank you awkward for your reference, I hope I'll find it in my university library (which I doubt, but nothing ventured, nothing gained)
    Thank you Laurent for your formula. I guess there's no need to ask for a formula for an arbitrary m Would it have been easier to look for a formula for exactly 3 birthdays ? Yeah I know we can make probability of having > 3 - probability of having > 2, but is there a closer form ?
    Note : I really suck at combinatorics, it's not that I'm too lazy to do it...

    P.S. : thanks
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. birthday problem
    Posted in the Advanced Statistics Forum
    Replies: 3
    Last Post: September 9th 2011, 11:43 AM
  2. Birthday Problem
    Posted in the Statistics Forum
    Replies: 1
    Last Post: July 30th 2010, 10:10 PM
  3. Yet another birthday problem
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: May 27th 2010, 06:02 AM
  4. Advanced Birthday Problem
    Posted in the Advanced Statistics Forum
    Replies: 4
    Last Post: March 20th 2010, 07:49 AM
  5. Birthday Paradox Problem!!
    Posted in the Advanced Statistics Forum
    Replies: 4
    Last Post: December 9th 2008, 12:56 PM

Search Tags


/mathhelpforum @mathhelpforum