# Extending the Classical Birthday Problem

I'm reading through some notes our Probability lecturer has uploaded, and he leaves a rather interesting variation on the classical Birthday Problem as an exercise for 'the adventurous Probabilist - with too much time on their hands'.

We let $B_k$ be the number of groups of $k$ individuals who all have the same birthday. From the phrasing of the first part of the problem, I feel he intends for the exercise to allow groups to overlap, i.e. if we have 3 people with birthday Jan. 1 and no other matches, then $B_3 = 1$, $B_2 = 3$, and $B_k = 0$ for $k > 3$.

The classical problem determines a value for $\mathbb{P} \{B_2>0\}$ and to find the least $n$ such that the probability of two people in a population of size $n$ sharing a birthday is greater that $\frac{1}{2}$. Through a standard combinatorial approach I've identified $n=23$.

Problem

We are asked now to determine $\mathbb{E}[B_2]$, $\text{Var}[B_2]$, $\mathbb{E}[B_3]$, and $\text{Var}[B_3]$. I think this is where a combinatorial approach breaks down, though I'm not sure.

I also wondered (beyond the realms of this exercise, but it seems an interesting problem - one which stumps me entirely), how we'd find the least $n$ such that the probability of three people in a population of size $n$ sharing a birthday is greater that $\frac{1}{2}$. I feel this could be approached using Chebyshev’s inequality though I'm yet to conclude how this could be applied successfully.

The lecturer's exercise also gives rise naturally to the question on how we could determine $\mathbb{E}[B_k]$, $\text{Var}[B_k]$ for general $k$. This seems like it could be quite a cumbersome exercise in combinatorics.

I would be very appreciative of anyone who can help with this exercise. Best, MM.

-

For the expectations $E(B_k)$, consider the probability that the first $k$ share a birthday which is $1/365^{k-1}$ so $$E(B_k) = {n \choose k}/365^{k-1}.$$

If overlaps are not counted, then consider the probability that the first $k$ share a birthday and the other $n-k$ do not share that birthday which is $364^{n-k}/365^{n-1}$ so $$E(B_k) = {n \choose k}\frac{364^{n-k}}{365^{n-1}}.$$

A related result is that the expected number of different birthdays is $$365 (1 - (364/365)^n)$$ while the variance of the expected number of different birthdays is $$365(364/365)^n + 364\times 365(363/365)^n - 365^2(364/365)^{2n}.$$

-

The case $k=2$ is quite simple.

Express the number of pairs $Z=\sum_i Z_i$, where the index runs over all pairs $i=\{i_1,i_2\}$ of distinct indices from $\{1,\dots, n\}$. Here $Z_i$ is the indicator random variable for the event that persons $i_1$ and $i_2$ share a birthday. Surprisingly, if $i\neq j$, then $Z_i$ and $Z_j$ are uncorrelated (though not independent) whether the intersection of $i$ and $j$ is empty or not.

Thus, for $N={n\choose 2}$ and $p=1/365$, the random variable $Z$ has the same mean and variance as if it were binomial: $$\mathbb{E}(Z)=Np,\quad \mathbb{V}(Z)=Np(1-p).$$

Sadly, this no longer works when $k$ is greater than $2$.

Update: Clearly I have too much time on my hands. Here is the general result: $$\mathbb{E}(B_k)={n\choose k}p^{k-1},\quad \mathbb{V}(B_k)={n\choose k}\sum_{j=2}^k{k\choose j}{n-k\choose k-j}\left[p^{2k-j-1}-p^{2(k-1)}\right].$$

-

I will concentrate on the second issue because this was one of the problem I was working on in respect to injective functions that are not balanced (the number of preimages of any element in the image are not necessarily equal).

There are other generalization of Birthday paradox from the point where you are looking. McKinney has an article in JSOTR, titled Generalized Birthday Problem which does the same. Another view of generalization has been looked by an article by Mathis, titled A Generalized Birthday Problem.

If you wish to look for functions that have arbitrary range (let say $n$, where $n$ in classical birthday problem is 365), there is a nice paper by Suziki et al. that gives a bound on the expected number of computation you need to do to find a $k$-way collisions. You can find the paper here. There was a paper by Diaconis and Mosteller Method for Studying coincidences that gives a very complicated theorem without proof that boils down to the result of Suziki et al when looked at asymptotically.

If you have issues with any of the above papers, just let me know. I will help with my understanding of these works. I am sure there are many more, but these are the one that I have gone through the patience of reading through.

-
Wonderful references, especially to the Method for Studying coincidences paper and its discussion of Jung and synchronicity. But are you aware of any generalizations that handle the case where the distribution of birthdays is non-uniform? E.g. I've heard of work by Bloom and by Klamkin? – nealmcb Dec 20 '14 at 23:21
To answer my own question, I found a reference for the non-uniform variation. It seems that it very quickly blows up in complexity. See The Uniformity Assumption in the Birthday Problem Geoffrey C. Berresford Mathematics Magazine, Vol. 53, No. 5 (Nov., 1980), pp. 286-288 stat.ethz.ch/education/semesters/as2013/bio/birthday.pdf – nealmcb Dec 22 '14 at 3:19

Hint: expectation is additive. That is, $E(A+B)$ = $E(A)+E(B)$, even if $A$ and $B$ are dependent somehow. This finishes off everything involving $E(B_k)$ almost instantly.

You can almost do the same trick with variance - and actually, you can do exactly the same trick for $V(B_2)$ - but for $V(B_3)$ and above, you need to put in some covariance terms.

When adding a bunch of random variables, the variance of the sum is equal to the sum of the variances plus twice the sum of pairwise covariances. See http://en.wikipedia.org/wiki/Variance#Properties for more info. You can calculate the covariance pretty easily for $V(B_3)$, since it's only nonzero when the groups of three share two members (i.e. {A,B,C} and {B,C,D}).

For $V(B_k)$ in general, it turns into the nightmare you mention, since groups can share anywhere from $2$ to $k-1$ members. You'll need a heavy dose of PIE (The principle of inclusion-exclusion) to handle this, but it's certainly possible (just hard).

-

Some thougths...

Let n = number of people and d = number of days in year.

Assume n < d

We try to calculate $\mathbb{E}[B_2]$, which is the expected number of pairs having the same birthday. We exclude triples (or more) with same birthday.

$C_{2,1}$=number of combinations with exactly 1 pair with same birthday = $\binom{n}{2}\cdot \frac{d!}{(d-n+1)!}$

$C_{2,2}$=number of combinations with exactly 2 pairs with same birthday = $\binom{n}{4}\cdot 3 \cdot \frac{d!}{(d-n+2)!}$

$C_{2,3}$=number of combinations with exactly 3 pairs with same birthday = $\binom{n}{6}\cdot 5 \cdot 3 \cdot \frac{d!}{(d-n+3)!}$

$C_{2,4}$=number of combinations with exactly 4 pairs with same birthday = $\binom{n}{8}\cdot 7 \cdot 5 \cdot 3 \cdot \frac{d!}{(d-n+4)!}$

$C_{2,k}$=number of combinations with exactly $k=\left \lfloor \frac{n}{2} \right \rfloor$ pairs with same birthday = $\binom{n}{2k}\cdot \left( 2k-1 \right) \cdot \left( 2k-3 \right) \cdot ... \cdot 3 \cdot \frac{d!}{(d-n+k)!}$

Now we should find a way to sum all these combinations.

$\mathbb{E}[B_2]$=$\frac{\sum_{l=1}^{k}{kC_{2,l}}} {d^n}$

-