Birthday "Paradox" - another, different, version!

745 Views Asked by At

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?

2

There are 2 best solutions below

3
On

The answer is:

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

4
On

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}}$$