8
$\begingroup$

Background

Many people are familiar with the so-called Birthday "Paradox" that, in a room of $23$ people, there is a better than $50/50$ chance that two of them will share the same birthday. In its more general form for $n$ people, the probability of no two people sharing the same birthday is $p(n) = \large\frac{365!}{365^n(365-n)!}$. Similar calculations are used for understanding hash-space sizes, cryptographic attacks, etc.

Motivation

The reason for asking the following question is actually related to understanding a specific financial market behavior. However, a variant on the "Birthday Paradox" problem fits perfectly as an analogy and is likely to be of wider interest to more people with different backgrounds. My question is therefore framed along the lines of the familiar "Birthday Paradox", but with a difference, as follows.

Situation

There are a total of $60$ people in a room. Of these, it turns out that there are $11$ pairs of people who share the same birthday, and two triples (i.e. groups of $3$ people) who have the same birthday. The remaining $60 - 11\cdot2 - 2\cdot3 = 32$ people have different birthdays. Assuming a population in which any day is equally likely for a birthday (i.e. ignore Feb 29th & possible seasonal effects) and, given the specified distribution of birthdays mentioned above, the questioner would actually like to understand how likely (or unlikely) it is that these $60$ people were really chosen randomly. However, I am not sure if the question posed in that way is actually answerable at all. When I posed this question on another site (where it was left unanswered), I was at least advised to re-state the question in a slightly different way, as follows below.

Question

If $60$ people are chosen at random from a population in which any day is equally likely to be a person's birthday, what is the probability that there are $11$ days on which exactly $2$ people share a birthday, two days on which exactly $3$ of them share a birthday, and no days on which $4$ or more of them share a birthday?

$\endgroup$
  • 2
    $\begingroup$ I'm new here. Thanks to those of you who assisted me with editing :-) $\endgroup$ – TonyMorland Jul 27 '14 at 16:27
  • 1
    $\begingroup$ You can use bold for emphasis, instead of ALL CAPS. Just put two asterisks on each side, like **this**. With one asterisk you get italic. $\endgroup$ – user147263 Jul 28 '14 at 1:53
5
$\begingroup$

All in terms of binomial coefficients, where $\binom{n}{k}$ is interpreted as the number of combinations of $k$ items from a pool of $n$:

$$\frac{\frac{\binom{60}{3}\binom{365}{1}\binom{57}{3}\binom{364}{1}}{2!}\cdot\frac{\binom{54}{2}\binom{363}{1}\binom{52}{2}\binom{362}{1}\cdots\binom{34}{2}\binom{353}{1}}{11!}\cdot\frac{\binom{32}{1}\binom{352}{1}\binom{31}{1}\binom{351}{1}\cdots\binom{1}{1}\binom{321}{1}}{32!}}{365^{60}}$$

The main numerator counts combinations that lead to the condition that you describe. First decide on three people to have the same birthday and decide what that common birthday is. Then repeat, but divide by $2!$ to account for duplication like where ABC-Jan1-DEF-Feb-1 was counted in addition to DEF-Feb1-ABC-Jan1.

Do a modification of this for the pairs. And then for the singles.

The whole thing can be simplified. It's nice to use multinomial coefficients $\binom{n}{k_1;\;k_2;\;\ldots;\; k_r}=\frac{n!}{(k_1)!(k_2)!\cdots(k_r)!}$ where it is required that $k_1+k_2+\cdots+k_r=n$. I presume that this next line would be the most immediately generalizable form to your actual application.

$$\frac{\binom{60}{\underbrace{3;\;3;}_2\;\underbrace{2;\;\cdots;\;2;}_{11}\;\underbrace{1;\;\cdots;\;1;}_{32}\; }\binom{365}{\underbrace{1;\;1;}_2\;\underbrace{1;\;\cdots;\;1;}_{11}\;\underbrace{1;\;\cdots;\;1;}_{32}\; 320}}{2!\cdot11!\cdot32!\cdot365^{60}}$$

But just in terms of factorials and powers, with low factorials evaluated and one or two other simplifications:

$$\frac{5\cdot59!\cdot364!}{3\cdot2^{12}\cdot320!\cdot(11!)\cdot(32!)\cdot365^{59}}$$

And more simplifications, (just checking how far I can go by hand---there may well be errors below.)

$$\frac{\left(59\cdot58\cdots34\right)\cdot\left(179\cdot178\cdots161\right)\cdot\overbrace{\left(361\cdot359\cdots323\right)}^{\mbox{odds}}\cdot362\cdot208\cdot121\cdot107}{365^{59}}$$

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Incidentally, not all births are equally likely to happen on any given day of the week. Due to C-sections and induced labors being scheduled on weekdays, as well as different stress patterns for different days of the week, more births happen on Monday through Friday than Saturday or Sunday. And there are further differences between the weekdays and between Saturday and Sunday. Coupled with the fact that any specific date of the year is not actually equally likely to fall on each of the seven days of the week, some assumptions used here are not quite reflective of reality. (But are close.) $\endgroup$ – alex.jordan Jul 28 '14 at 1:49
  • $\begingroup$ Actually any specific birthday is equally likely to fall on each of the seven days of the week, unless you expect to have people who were born before 1901 in your sample. That said, there could be non-uniformities based on certain years being more likely than others... $\endgroup$ – Micah Jul 28 '14 at 3:37
  • 1
    $\begingroup$ @Micah Two things: are you considering the cycle of the Gregorian calendar? In its 400-year cycle, Jan 1 will fall on a Monday 56 times, on Sunday 58 times, etc (so--not equally likely). The other thing: If we start considering that no one from 400 years ago is still around, then we should maybe bring in actuarial tables and weight the last 100 or so years and the dates in those years accordingly :) $\endgroup$ – alex.jordan Jul 28 '14 at 3:44
  • 1
    $\begingroup$ I'm saying that the Gregorian calendar and the Julian calendar have been equivalent (up to a possible shift) since 1901, so the unevenness in the Gregorian calendar isn't an issue for living people. I agree that to really do this right would involve actuarial tables. :) $\endgroup$ – Micah Jul 28 '14 at 4:30
3
$\begingroup$

The answer is:

$$\frac{365!}{320!365^{60}}\frac{60!}{32!3!3!2!^{11}}\frac{1}{2!11!}$$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ not enough for an answer $\endgroup$ – John Fernley Jul 28 '14 at 2:48
  • 3
    $\begingroup$ Follows logic by Theophile but corrects multinomial as he forgot 32 in denominator. Must have 32+3+3+2*11=60. And two triples and 11 doubles can be ordered in 2!11! ways. Done. $\endgroup$ – Mr.Spot Jul 28 '14 at 3:03
  • $\begingroup$ Thanks for the bonus of lively discussion regarding Gregorian vs Julian calendar, C-section births during the week rather than weekends (presumably because doctors are playing golf). No doubt there is also a birthday bias related to higher conception rates during holidays. However these factors aren't relevant to the actual problem which concerns financial market behavior but the Birthday Paradox is an exact analog and more familiar. Anyway, you guys are a lot more interesting than the other group where I asked the question, and they wouldn't deign to answer because I didn't show python code! $\endgroup$ – TonyMorland Jul 28 '14 at 14:29
1
$\begingroup$

I think this should work: let's first calculate the probability that the people enter the room one at a time to form a sequence $T_1, T_2, D_1, D_2, \ldots, D_{11}, S_1, S_2, \ldots, S_{32}$, where $T_i$ is the $i$th triplet of birthdays, $D_i$ is the $i$th double, and $S_i$ is the $i$th singleton.

For $T_1, T_2$, we'll have $(\frac{365}{365} \cdot \frac{1}{365} \cdot \frac{1}{365})(\frac{364}{365} \cdot \frac{1}{365} \cdot \frac{1}{365})$;

Then for $D_1$ to $D_{11}$ we'll have $(\frac{363}{365}\cdot\frac{1}{365})(\frac{362}{365}\cdot\frac{1}{365})\cdots(\frac{353}{365}\cdot\frac{1}{365})$;

And finally for $S_1$ to $S_{32}$, $(\frac{352}{365})(\frac{351}{365})\cdots(\frac{321}{365})$.

Multiplying these produces $\frac{365!}{365^{60}320!}$. But now accounting for the different ways in which the people could have entered the room, namely $\frac{60!}{3!3!\underbrace{2!2!\cdots2!}_{11}}$, and accounting for the fact that we can permute the triples, the doubles, and the singletons, we have a probability of

$$\frac{365!}{365^{60}320!}\frac{60!}{3!^22^{11}}\frac{1}{2!11!32!}.$$

This comes out to around $4.665 \times 10^{-6}$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I think this overcounts. You can permute the two triples, the eleven pairs, and 32 leftovers. So this overcounts by a factor of $2!\cdot11!\cdot32!$. $\endgroup$ – alex.jordan Jul 28 '14 at 1:20
  • $\begingroup$ @alex.jordan I considered that at first, but I don't think that's right. In the usual "birthday paradox" with $23$ people, for instance, there is no multiplication by $23!$. $\endgroup$ – Théophile Jul 28 '14 at 3:16
  • $\begingroup$ @alex.jordan Sorry, I see now what you mean. My way of calculation would have introduced a 23!, and the permutation of these people cancels that out. $\endgroup$ – Théophile Jul 28 '14 at 3:29
  • $\begingroup$ There is a $21!$ if you count in the same manner, looking for the chances of having exactly one pair of people with the same birthday. It is usually just about having some pair of people with the same birthday, so you can get away with simpler counting. For exactly one pair in that setting: $\frac{1}{365^{23}}\binom{23}{2}\binom{365}{1}\binom{364}{21}\cdot 21!$. As evidence your number can't be right, WA says it it is of order $10^{37}$. $\endgroup$ – alex.jordan Jul 28 '14 at 3:30
  • $\begingroup$ @alex.jordan I have edited my answer; I think it should be correct now? $\endgroup$ – Théophile Jul 28 '14 at 3:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.