Reverse birthday problem with multiple collisions

Question

Assume you had an alien year with an unknown length N. If you have a random sample of said aliens and some of them share birthdays, can you use this data to estimate the length of the year?

For example, in a sample of 100, you could have two triplets (ie. two birthdays each shared by three aliens) and five pairs and eighty-four singletons. In estimating N, the absolute minimum is 91 and the maximum is unbounded, but how would I find a reasonable expected value?

Assumptions include things like "all birthdays are equally likely".

Unlike another question answered here, there is are known collisions in the room. Any sufficiently long year will have a strong likelihood of no collisions for a room of aliens. But very long years will have low odds of any collisions, and short years will have low odds of few collisions, thus providing a (theoretical) range for most-likely year lengths.

Answer 1

The expectation value of a distribution is calculated as $E(X) = \sum {p_ix_i}$. For this problem, we want to calculate the distribution of $N$ given some collision criteria, or find $E(N) = \sum_{n=0}^{\infty}p_n n$ given some collision criteria, where $p_n=P(N=n).$

Suppose you have some collision criteria as stated above, and let $q_n$ be the probability that the collision criteria is met given the length of the year is $n.$ Then $q_n$ can be found by simply dividing the number of ways the collision criteria can be met by the number of ways birthdays can be arranged in general. Once $q_n$ is found for each possible $n$, then the only piece that is missing is translating $q_n$ to $p_n.$

If we assume that $p_n$ is proportional to $q_n$, then $p_n= \alpha q_n.$ Since $\sum_{n=0}^{\infty} p_n=1$, $\alpha \sum_{n=0}^{\infty} q_n=1$ and $\alpha=\frac{1}{\sum_{n=0}^{\infty} q_n}.$ Therefore, we just need a formula for $q_n$ to solve this problem.

For your example, let us first find the number of ways the collision criteria can happen given $N=n.$ The first alien singleton can land on any day, so there are $n$ possibilities. The next singleton can land on any day but the birthday of the first alien, so there are $n-1$ possibilities. Completing this for the first 84 singletons, we get $n(n-1)(n-2)...(n-83)$ possible ways this can happen. Notice we also have 5 pairs and 2 triplets, so the "first" alien for each group must not land on the singleton pairs either. This leads to a $n(n-1)(n-2)...(n-84-5-2 + 1)$ ways these aliens don't collide (the clumsy syntax is for easier generalization later).

Next, the second alien for a given pair or triplet has 91 choices, the next has 90, etc., the total number of ways this can happen given the birthdays of the first 91 aliens is $91(91-1)(91-2)...(91-7+1)$. The remaining members of the triplets must fall on birthdays of the pairs, and the probability of that happening is $7*6$. We multiply the probabilities for these all together to get a total number of possible ways for the collision criteria to be met as:

$$r_n=n(n-1)...(n-84-5-2+1)(84+5+2)(84+5+2-1)...(84+1)(5+2)(5+1)$$

At this point the pattern is clear, if we have $a$ singletons, $b$ pairs, and $c$ triplets, we replace 84 with $a,$ 5 with $b,$ and 2 with $c$ to get a generalized formula. I think it is also clear that the number of possible ways for the birthdays to be arranged in general is $n^m$, where m is the total number of aliens in the problem. Therefore, the probability of meeting the collision criteria is the number of ways to meet the collision criteria divided by the number of ways the aliens could be born, or $q_n=\frac{r_n}{n^m}$.

Another interesting thing appeared in the formula of $r_n$. Let $y_n=n(n-1)...(n-(a+b+c)+1)=\frac{n!}{(n-(a+b+c))!}$, and let $z_n$ be the remaining portion of $r_n$ so that $r_n=y_nz_n$. Note that $z_n$ is independent of n, so we can simply write $z_n=z$ as a constant! Since $p_n=q_n/\sum_{i=0}^\infty q_i$, and $q_n=\frac{zy_n}{n^m}$, we can actually factor $z$ out of the sum in the denominator. At this point, it cancels out with the portion from the numerator to get $p_n=\frac{y_n}{n^m}/\sum_{i=0}^\infty (\frac{y_i}{i^m})$. We can simplify $y_n$ further if we let $s=a+b+c$ (or this can be thought of as the number of unique birthdays in the group of aliens), so that we get:

$$ p_n=\frac{\frac{n!}{(n-s)!}}{n^m}/\sum_{i=0}^\infty (\frac{\frac{i!}{(i-s)!}}{i^m}) $$

Now we have a (fairly) simple formula for $p_n$, and therefore a (fairly) simple formula for $E(N)$, where the only assumption made was that $P(N=n)$ is proportional to $q_n$ (the probability of meeting the collision criteria given that $N=n$). I think this is a fair assumption to make, and someone smarter than me might even be able to prove that this assumption is associated with $P(N=n)$ following a multinomial distribution. At this point we can calculate $E(N)$ using numerical methods or make some approximation assumptions, as $p_n$ will approach 0 as $n$ approaches $\infty$.

Answer 2

The excellent answer from Cody provides a nice way to express the likelihood function for $N$, the number days in the year (or the posterior distribution based on a flat prior) by factoring out some part of the probability that is independent from $N$.

In this answer I would like to write it down more concisely and also provide a way to compute the maximum of this likelihood function (rather than the expected value which is much more difficult to compute).

---

Likelihood function for N

The number of ways to draw a sequence of $a+2b+3c$ birthdays out of a set of $n$ birthdays, with the restriction that $a$ is the number of single birthdays, $b$ duplicate birthdays, and $c$ triple birthdays is equal to

$$\begin{array}{ccl} r_n &=& \underbrace{{n}\choose{a+b+c}}_{\small\begin{array}{ccc}&\text{number of ways to} &\\ &\text{pick $m$ unique birthdays}& \\ &\text{out of $n$ days}&\end{array}} \underbrace{\frac{(a+b+c)!}{a!b!c!}}_{\small\begin{array}{ccc}&\text{number of ways to} &\\ &\text{distribute $m$ birthdays}& \\ &\text{among groups of size $a$, $b$ and $c$}&\end{array}} \underbrace{\frac{(a+2b+3c)!}{1!^a2!^b3!^c}}_{\small\begin{array}{ccc}&\text{number of ordered ways to} &\\ &\text{arrange specific }& \\&\text{single, duplicate, and triplicates}& \\ &\text{among the aliens }&\end{array}} \\ &=& \frac{n!}{(n-a-b-c)!} \times \frac{(a+2b+3c)}{a!b!c!1!^a2!^b3!^c} \end{array} $$

and only the first term on the righthandside is dependent on $n$, so by factoring out the other terms we end with a simple expression for a likelihood function $$\begin{array}{rcl} \mathcal{L}(n|a,b,c) &=& n^{-(a+2b+3c)} \frac{n!}{(n-a-b-c)!} = n^{-m} \frac{n!}{(n-s)!}\\ & \propto & P(a,b,c|n) \end{array}$$

where we follow the notation from Cody and use $m$ to denote the number of aliens and $s$ the number of unique birthdays.

---

Maximum likelihood estimate for N

We can use this likelihood function to derive the maximum likelihood estimate for $N$.

Note that

$$\mathcal{L}(n) = \mathcal{L}(n-1) \left(\frac{n-1}{n}\right)^m\frac{n}{n-s}$$

and the maximum will occur just before the $n$ for which

$$\left(\frac{n-1}{n}\right)^m\frac{n}{n-s} = 1$$

or

$$s = n \left(1-\left(1-1/n\right)^m \right)$$

which is for large $n$ approximately (using a Laurent series which you can find by substituting $x = 1/n$ and write the Taylor series for $x$ in the point $x=0$)

$$s \approx \sum_{k=0}^l {{m}\choose{k}} (-n)^{-k} + \mathcal{O} \left( n^{-(l+1)} \right) $$

Using only the first order term $s \approx m - \frac{m(m-1)}{2 n}$ you get:

$$n_1 \approx \frac{ {{m}\choose{2}}}{m-s} $$

Using the second order term as well $s \approx m - \frac{m(m-1)}{2 n} + \frac{m(m-1)(m-2)}{6 n^2}$ you get:

$$n_2 \approx \frac{ {{m}\choose{2}} + \sqrt{{{m}\choose{2}}^2- 4 (m-s){{m}\choose{3}} } }{2(m-s)} $$

So in the case of the $m=100$ aliens among which there are $s=91$ unique birthdays you get using the approximation $n_1 \approx 550$ and $n_2 \approx 515.1215$. When you solve the equation numerically you get $n=516.82$ which we round-down to $n=516$ to get the MLE.