{"id":2256,"date":"2013-11-18T10:00:08","date_gmt":"2013-11-18T15:00:08","guid":{"rendered":"http:\/\/scientopia.org\/blogs\/goodmath\/?p=2256"},"modified":"2016-07-31T16:02:42","modified_gmt":"2016-07-31T20:02:42","slug":"the-birthday-paradox","status":"publish","type":"post","link":"http:\/\/www.goodmath.org\/blog\/2013\/11\/18\/the-birthday-paradox\/","title":{"rendered":"The Birthday Paradox"},"content":{"rendered":"

To me, the thing that makes probability fun is that the results are frequently surprising. We’ve got very strong instincts about how we expect numbers to work. But when you do anything that involves a lot of computations with big numbers, our intuition goes out the window – nothing works the way we expect it to. A great example of that is something called the birthday paradox.<\/p>\n

Suppose you’ve got a classroom full of people. What’s the probability that there are two people with the same birthday? Intuitively, most people expect that it’s pretty unlikely. It seems like it shouldn’t be likely – 365 possible birthdays, and 20 or 30 people in a classroom? Very little chance, right?<\/p>\n

Let’s look at it, and figure out how to compute the probability.<\/p>\n

Interesting probability problems are all about finding out how to put things together. You’re looking at things where there are huge numbers of possible outcomes, and you want to determine the odds of a specific class<\/em> of outcomes. Finding the solutions is all about figuring out how to structure the problem.<\/p>\n

A great example of this is something called the birthday paradox. This is a problem with a somewhat surprising outcome. It’s also a problem where finding the right way to structure the problem is has a dramatic result.<\/p>\n

Here’s the problem: you’ve got a group of 30 people. What’s the probability that two people out of that group of thirty have the same birthday?<\/p>\n

We’ll look at it with some simplifying assumptions. We’ll ignore leap year – so we’ve got 365 possible birthdays. We’ll assume that all birthdays are equally likely – no variation for weekdays\/weekends, no variation for seasons, and no holidays, etc. Just 365 equally probable days.<\/p>\n

How big is the space? That is, how many different ways are there to assign birthdays to 30 people? It’s 36530<\/sup> or something in the vicinity of 7.4*1076<\/sup>.<\/p>\n

To start off, we’ll reverse the problem. It’s easier to structure the problem if we try to ask “What’s the probability that no two people share a birthday”. If P(B) is the probability that no two people share a birthday, then 1-P(B) is the probability that at least two people share a birthday.<\/p>\n

So let’s look at a couple of easy cases. Suppose we’ve got two people? What’s the odds that they’ve got the same birthday? 1 in 365: there are 3652<\/sup> possible pairs of birthdays; there are 365 possible pairs. So there’s a probability of 365\/3652<\/sup> that the two people have the same birthday. For just two people, it’s pretty easy. In the reverse form, there’s a 364\/365 chance that the two people have different birthdays.<\/p>\n

What about 3 people? It’s the probability of the first two having different birthdays, and<\/em> the probability of the third person having a different birthday that either of those first two. There are 365 possible birthdays for the third person, and 363 possible days that don’t overlay with the first two. So for N people, the probability of having distinct birthdays is 1 \\times (1 - 1\/365) \\times (1 - 2\/365) \\times \\dots (1 - (n\/365)).<\/p>\n

At this point, we’ve got a nice recursive definition. Let’s say that f(N) is the probability of N people having distinct birthdays. Then: <\/p>\n

    \n
  1. For 2 people, the probability of distinct birthdays is 364\/365. (f(2) = \\frac{364}{365})<\/li>\n
  2. For N>2 people, the probability of distinct birthdays is
    \n\\frac{365-(N-1)}{365} times f(n-1). <\/li>\n<\/ol>\n

    Convert that to a closed form, and you get: f(n) = \\frac{365!}{(365-(n-1))!365^n}. For 30 people, that’s
    \n\\frac{365!}{(365-29)!*365^{30}}. Work it out, and that’s
    \n0.29 – so the probability of everyone having distinct
    \nbirthdays is 29% – which means that the probability of at least
    \ntwo people in a group of 30 having the same birthday is 71%!<\/p>\n

    You can see why our intuitions are so bad? We’re talking about something where one factor in the computation is the factorial of 365!<\/p>\n

    Let’s look a bit further: how many people do you need to have, before there’s a 50% chance of 2 people sharing a birthday? Use the formulae we wrote up above, and it turns out to be 23. Here’s the numbers – remember that this is the reverse probability, the probability of all birthdays being distinct. <\/p>\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n
    1<\/td>\n1<\/dt>\n<\/tr>\n
    2<\/td>\n0.997260273973<\/dt>\n<\/tr>\n
    3<\/td>\n0.991795834115<\/dt>\n<\/tr>\n
    4<\/td>\n0.983644087533<\/dt>\n<\/tr>\n
    5<\/td>\n0.9728644263<\/dt>\n<\/tr>\n
    6<\/td>\n0.959537516351<\/dt>\n<\/tr>\n
    7<\/td>\n0.943764296904<\/dt>\n<\/tr>\n
    8<\/td>\n0.925664707648<\/dt>\n<\/tr>\n
    9<\/td>\n0.905376166111<\/dt>\n<\/tr>\n
    10<\/td>\n0.883051822289<\/dt>\n<\/tr>\n
    11<\/td>\n0.858858621678<\/dt>\n<\/tr>\n
    12<\/td>\n0.832975211162<\/dt>\n<\/tr>\n
    13<\/td>\n0.805589724768<\/dt>\n<\/tr>\n
    14<\/td>\n0.776897487995<\/dt>\n<\/tr>\n
    15<\/td>\n0.747098680236<\/dt>\n<\/tr>\n
    16<\/td>\n0.716395994747<\/dt>\n<\/tr>\n
    17<\/td>\n0.684992334703<\/dt>\n<\/tr>\n
    18<\/td>\n0.653088582128<\/dt>\n<\/tr>\n
    19<\/td>\n0.620881473968<\/dt>\n<\/tr>\n
    20<\/td>\n0.588561616419<\/dt>\n<\/tr>\n
    21<\/td>\n0.556311664835<\/dt>\n<\/tr>\n
    22<\/td>\n0.524304692337<\/dt>\n<\/tr>\n
    23<\/td>\n0.492702765676<\/dt>\n<\/tr>\n
    24<\/td>\n0.461655742085<\/dt>\n<\/tr>\n
    25<\/td>\n0.431300296031<\/dt>\n<\/tr>\n
    26<\/td>\n0.401759179864<\/dt>\n<\/tr>\n
    27<\/td>\n0.373140717737<\/dt>\n<\/tr>\n
    28<\/td>\n0.345538527658<\/dt>\n<\/tr>\n
    29<\/td>\n0.319031462522<\/dt>\n<\/tr>\n
    30<\/td>\n0.293683757281<\/dt>\n<\/tr>\n
    31<\/td>\n0.269545366271<\/dt>\n<\/tr>\n
    32<\/td>\n0.24665247215<\/dt>\n<\/tr>\n
    33<\/td>\n0.225028145824<\/dt>\n<\/tr>\n
    34<\/td>\n0.20468313538<\/dt>\n<\/tr>\n
    35<\/td>\n0.185616761125<\/dt>\n<\/tr>\n
    36<\/td>\n0.16781789362<\/dt>\n<\/tr>\n
    37<\/td>\n0.151265991784<\/dt>\n<\/tr>\n
    38<\/td>\n0.135932178918<\/dt>\n<\/tr>\n
    39<\/td>\n0.121780335633<\/dt>\n<\/tr>\n
    40<\/td>\n0.108768190182<\/dt>\n<\/tr>\n
    41<\/td>\n0.0968483885183<\/dt>\n<\/tr>\n
    42<\/td>\n0.0859695284381<\/dt>\n<\/tr>\n
    43<\/td>\n0.0760771443439<\/dt>\n<\/tr>\n
    44<\/td>\n0.0671146314486<\/dt>\n<\/tr>\n
    45<\/td>\n0.0590241005342<\/dt>\n<\/tr>\n
    46<\/td>\n0.0517471566327<\/dt>\n<\/tr>\n
    47<\/td>\n0.0452255971667<\/dt>\n<\/tr>\n
    48<\/td>\n0.0394020271206<\/dt>\n<\/tr>\n
    49<\/td>\n0.0342203906773<\/dt>\n<\/tr>\n
    50<\/td>\n0.029626420422<\/dt>\n<\/tr>\n<\/table>\n

    With just 23 people, there’s a greater than 50% chance that two people will have the same birthday. By the time you get to just 50 people, there’s a greater than 97% chance that two people have the same birthday!<\/p>\n

    As an amusing aside, the first time I saw this problem worked through was in an undergraduate discrete probability theory class, with 37 people in the class, and no<\/em> duplicate birthdays!<\/p>\n

    Now – remember at the beginning, I said that the trick to working probability problems is all about how you formulate the problem. There’s a much, much better way to formulate this.<\/p>\n

    Think of the assignment of birthdays as a function from people to birthdays: f: P \\rightarrow B. The number of ways of assigning birthdays to people is the size of the set of functions from people to birthdays. How many possible functions are there? | B | ^{| P |}. | B | is the number of days in the year – 365, and | P | is the number of people in the group. <\/p>\n

    The set of assignments to unique birthdays is the number of injective<\/em> functions. (An injective function is a function where f(x) = f(y) \\Leftrightarrow x = y.) How many injective functions are there? \\frac{| B |!}{(| B | - | P |)!}. <\/p>\n

    The probability of all birthdays being unique is the size of the set of injective functions divided by the size of the set of all assignments: \\frac{\\frac{| B |!}{(| B | - | P |)!}}{ | B | ^{| P |} } = \\frac{365!}{365^P\\times (365 - P)!}.<\/p>\n

    So we’ve got the exact same result – but it’s a whole lot easier in term of the discrete functions!<\/p>\n","protected":false},"excerpt":{"rendered":"

    To me, the thing that makes probability fun is that the results are frequently surprising. We’ve got very strong instincts about how we expect numbers to work. But when you do anything that involves a lot of computations with big numbers, our intuition goes out the window – nothing works the way we expect it […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[53],"tags":[],"class_list":["post-2256","post","type-post","status-publish","format-standard","hentry","category-probability"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p4lzZS-Ao","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/2256","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/comments?post=2256"}],"version-history":[{"count":2,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/2256\/revisions"}],"predecessor-version":[{"id":3293,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/2256\/revisions\/3293"}],"wp:attachment":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/media?parent=2256"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/categories?post=2256"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/tags?post=2256"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}